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=-1.9 required=5.0 tests=BAYES_00 autolearn=ham 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 18:27:23 PST Path: archiver1.google.com!news1.google.com!sn-xit-02!supernews.com!newsfeed.direct.ca!look.ca!newsfeed1.earthlink.net!newsfeed.earthlink.net!newsmaster1.prod.itd.earthlink.net!newsread1.prod.itd.earthlink.net.POSTED!not-for-mail Message-ID: <3BF08501.50C83D22@acm.org> From: Jeffrey Carter X-Mailer: Mozilla 4.7 [en] (Win98; U) X-Accept-Language: en MIME-Version: 1.0 Newsgroups: comp.lang.ada Subject: Re: List container: Insert and Delete 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> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Date: Tue, 13 Nov 2001 02:27:20 GMT NNTP-Posting-Host: 209.86.209.203 X-Complaints-To: abuse@earthlink.net X-Trace: newsread1.prod.itd.earthlink.net 1005618440 209.86.209.203 (Mon, 12 Nov 2001 18:27:20 PST) NNTP-Posting-Date: Mon, 12 Nov 2001 18:27:20 PST Organization: EarthLink Inc. -- http://www.EarthLink.net X-Received-Date: Mon, 12 Nov 2001 18:23:16 PST (newsmaster1.prod.itd.earthlink.net) Xref: archiver1.google.com comp.lang.ada:16394 Date: 2001-11-13T02:27:20+00:00 List-Id: Ted Dennison wrote: > > 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! I'm not sure what you're saying here; perhaps that initial "O(N)" should be O(1)? Actually, for a bounded list you have 2 lists in the same array: the real list and a free list. Because of the free list, there is no searching for a hole. Insertions and deletions are O(1) for all positions. I think I have a skeleton for a bounded list somewhere. If I can get 2 votes for posting the basics of the implementation I'll dig it out (or make it up again) and post it. -- Jeff Carter "If you think you got a nasty taunting this time, you ain't heard nothing yet!" Monty Python and the Holy Grail