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.1 required=5.0 tests=BAYES_00,LOTS_OF_MONEY, PP_MIME_FAKE_ASCII_TEXT autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII X-Google-Thread: 103376,a644fa9cd1a3869a X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2001-11-13 21:05:16 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!newsfeeds.belnet.be!news.belnet.be!news1.ebone.net!news.ebone.net!fu-berlin.de!uni-berlin.de!ppp-1-18.cvx1.telinco.NET!not-for-mail From: "Nick Roberts" Newsgroups: comp.lang.ada Subject: Re: List container: Insert and Delete Date: Wed, 14 Nov 2001 04:16:51 -0000 Message-ID: <9ssu29$150jnq$3@ID-25716.news.dfncis.de> 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> NNTP-Posting-Host: ppp-1-18.cvx1.telinco.net (212.1.136.18) X-Trace: fu-berlin.de 1005714314 38817530 212.1.136.18 (16 [25716]) X-Priority: 3 X-MSMail-Priority: Normal X-Newsreader: Microsoft Outlook Express 5.50.4133.2400 X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4133.2400 Xref: archiver1.google.com comp.lang.ada:16483 Date: 2001-11-14T04:16:51+00:00 List-Id: However, it doesn't solve the question of memory usage. I know the 'classic' implementation of a bounded list is to have (in effect) a linked list within an array (or three arrays), but that was not what I actually intended. I actually intended the 'horrible' choice of an array where the first list item is stored in the first element of the array, the second in the second, etc. You might called this the 'na�ve' implementation. The reason why is because it is the most memory efficient, and I assume that some applications will require memory efficiency about speed concerns; especially considering that appends still can be done very fast. Possibly we need a different nomenclature, e.g. Bounded_List for the classic implementation, and maybe Bounded_Vector for the na�ve? Or Packed_List? -- Best wishes, Nick Roberts "Ted Dennison" wrote in message news:l%9I7.22965$xS6.35437@www.newsranger.com... > 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).