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-13 06:21:08 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!canoe.uoregon.edu!logbridge.uoregon.edu!news.maxwell.syr.edu!news-out.nuthinbutnews.com!propagator2-austin!propagator!feed2.newsfeeds.com!newsfeeds.com!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> <3BF08501.50C83D22@acm.org> 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: Tue, 13 Nov 2001 09:21:05 EST Organization: http://www.newsranger.com Date: Tue, 13 Nov 2001 14:21:05 GMT Xref: archiver1.google.com comp.lang.ada:16406 Date: 2001-11-13T14:21:05+00:00 List-Id: In article <3BF08501.50C83D22@acm.org>, Jeffrey Carter says... > >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. Ahhh. I'd fogotten that you can make a list of the free stuff. That's right, it is O(1). --- 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.