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-11 09:37:52 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!logbridge.uoregon.edu!paloalto-snh1.gtei.net!lsanca1-snf1!news.gtei.net!newsfeed2.earthlink.net!newsfeed.earthlink.net!newsmaster1.prod.itd.earthlink.net!newsread1.prod.itd.earthlink.net.POSTED!not-for-mail Message-ID: <3BEEB766.B50C969@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> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Date: Sun, 11 Nov 2001 17:37:49 GMT NNTP-Posting-Host: 209.86.209.62 X-Complaints-To: abuse@earthlink.net X-Trace: newsread1.prod.itd.earthlink.net 1005500269 209.86.209.62 (Sun, 11 Nov 2001 09:37:49 PST) NNTP-Posting-Date: Sun, 11 Nov 2001 09:37:49 PST Organization: EarthLink Inc. -- http://www.EarthLink.net X-Received-Date: Sun, 11 Nov 2001 09:33:47 PST (newsmaster1.prod.itd.earthlink.net) Xref: archiver1.google.com comp.lang.ada:16282 Date: 2001-11-11T17:37:49+00:00 List-Id: Nick Roberts wrote: > > We're programmers, Jeff, not mathematicians. We don't have to worry about > what the mathematical definition of a list is. What we do have to worry > about is what is: (a) useful from a user's point of view; (b) practical from > an implementational point of view. I'm a software engineer, but I use lists when I need to insert and delete at arbitrary points in a sequence, just as with the mathematical definition. > > My suggestion that insertions and deletions be positioned by specifying an > integer (starting at 1 for the first item in the list) satisfies (a), I > think, but not necessarily (b), depending on the implementation. Positive integers are generally used to indicate positions in lists in mathematical notation. For a software list implemented using pointers (an unbounded list), using integers to indicate positions becomes an O(N) time operation for every reference to the list. It is better to abstract the concept of a position to something that provides the same behavior but with O(1) time complexity. > > However, I'm pretty sure that trying to do insertions and deletions while > iterating through a list fails both (a) and (b) miserably. That's what I was > trying to get across. I agree that one should not be doing insertions and deletions while iterating over a list. Iterators should not allow this, and positions should generally not be used for iteration. -- Jeff Carter "I blow my nose on you." Monty Python & the Holy Grail