From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=0.6 required=5.0 tests=BAYES_00,TO_NO_BRKTS_FROM_MSSP autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,a644fa9cd1a3869a X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2001-11-12 09:28:44 PST Path: archiver1.google.com!news1.google.com!sn-xit-02!sn-xit-04!supernews.com!telocity-west!TELOCITY!nntp-relay.ihug.net!ihug.co.nz!out.nntp.be!propagator-SanJose!in.nntp.be!newsranger.com!www.newsranger.com!not-for-mail Newsgroups: comp.lang.ada From: Ted Dennison References: <3BECA3B7.5020702@telepath.com> <9sjf4n$odm$1@news.huji.ac.il> <9sjkc7$145mhb$1@ID-25716.news.dfncis.de> <3BEDACC0.9A314B54@acm.org> <9sktgm$134npc$3@ID-25716.news.dfncis.de> <3BEEB766.B50C969@acm.org> <9sn4qk$13g29j$1@ID-25716.news.dfncis.de> <3BEFF9D6.607480D@boeing.com> Subject: Re: List container: Insert and Delete Message-ID: X-Abuse-Info: When contacting newsranger.com regarding abuse please X-Abuse-Info: forward the entire news article including headers or X-Abuse-Info: else we will not be able to process your request X-Complaints-To: abuse@newsranger.com NNTP-Posting-Date: Mon, 12 Nov 2001 12:28:41 EST Organization: http://www.newsranger.com Date: Mon, 12 Nov 2001 17:28:41 GMT Xref: archiver1.google.com comp.lang.ada:16343 Date: 2001-11-12T17:28:41+00:00 List-Id: In article <3BEFF9D6.607480D@boeing.com>, Jeffrey Carter says... >They will be O(N) in both versions, unless you make the extremely poor >implementation decision for the bounded version to implement insertions >and deletions by moving entire slices of the underlying array. I suspect >such an implementation will be universally considered unacceptable. >Making insertions and deletions O(N) so that indexing can be O(1) is a >poor choice, especially considering that both can be O(1). If you make deletions O(N) in a bounded structure, that means you have to deal with the possiblity of "holes" in your bounded storage area. I believe that means that you will have to go searching for a empty hole in which to place new nodes, which means that insertions are actually *not* O(1), even when done to the end of the list! So there *are* trade-offs that have to be taken into consideration here. Just implementing a STL-style "Vector" would actually be a big win for someone who only wants a stack or a queue, or for someone who doesn't mind managing the stuff in the middle themselves. Or we could implement a true unbounded list, but not bother with internal links on the theory that middle insertions and deletions are rare, and prominently documented to be O(N) for this data strucutre. --- T.E.D. homepage - http://www.telepath.com/dennison/Ted/TED.html No trees were killed in the sending of this message. However a large number of electrons were terribly inconvenienced.