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.4 required=5.0 tests=AC_FROM_MANY_DOTS,BAYES_00, LOTS_OF_MONEY 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 12:56:48 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!newsfeeds.belnet.be!news.belnet.be!psinet-eu-nl!psiuk-p4!psiuk-p3!uknet!psiuk-n!news.pace.co.uk!nh.pace.co.uk!not-for-mail From: "Marin David Condic" Newsgroups: comp.lang.ada Subject: Re: List container: Insert and Delete Date: Tue, 13 Nov 2001 15:18:38 -0500 Organization: Posted on a server owned by Pace Micro Technology plc Message-ID: <9srv70$k0k$1@nh.pace.co.uk> References: <9sn4qm$13g29j$2@ID-25716.news.dfncis.de> <9sok8i$142am0$2@ID-25716.news.dfncis.de> <3BF004F4.F74AE461@boeing.com> <9sp5up$g5o$1@nh.pace.co.uk> <3BF0827A.DCF2213C@acm.org> <9sra40$b8p$1@nh.pace.co.uk> <5DaI7.23016$xS6.35866@www.newsranger.com> <3BF14752.B3F3FBC@boeing.com> NNTP-Posting-Host: dhcp-200-133.miami.pace.co.uk X-Trace: nh.pace.co.uk 1005682720 20500 136.170.200.133 (13 Nov 2001 20:18:40 GMT) X-Complaints-To: newsmaster@news.cam.pace.co.uk NNTP-Posting-Date: 13 Nov 2001 20:18:40 GMT X-Priority: 3 X-MSMail-Priority: Normal X-Newsreader: Microsoft Outlook Express 5.50.4522.1200 X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4522.1200 Xref: archiver1.google.com comp.lang.ada:16448 Date: 2001-11-13T20:18:40+00:00 List-Id: If its any consolation, I have always heard and used the term "Lists" pretty much as you have. Stacks, Queues, Single/Double, etc, were always special cases of a "List". I would consider Trees (binary and otherwise) and Maps outside of this set, but inside some general set called "Linked Data Structures" or "Containers". I'd really hate to have us get hung up on terminology and formalism. I think if we get something that is generally useful - out of which you can get the functionality of a stack or queue or whatever - then for *practical* usage, we've got what we want. If an operation doesn't fit some formal definition, but is useful and easily implemented, then fine. If soneone isn't going to be happy about using the term "List" unless it fits some definition, then lets call them "Gazorenthorpes" and move on. The important thing is having a data structure of some sort that will exhibit the most common and useful behavior in real-world programming situations. Out of all the linked data structures I've ever heard about, the only two that I've ever used with any frequency are Lists and Maps. (The minute you get into trees of any sort, they start becoming so specialized to the application that they always seemed to me to be something that would be difficult to generalize & still be useful. Better to build them as you need them...) MDC -- Marin David Condic Senior Software Engineer Pace Micro Technology Americas www.pacemicro.com Enabling the digital revolution e-Mail: marin.condic@pacemicro.com Web: http://www.mcondic.com/ "Ted Dennison" wrote in message news:aYeI7.23350$xS6.36692@www.newsranger.com... > > That's precisely my experience, which is what makes me wonder if it really needs > to be a full O(1)-insert list. Every time I've needed a bounded list, I've ended > up writing a circular queue. > > >For a list, the only basic operation that is O(N) in time is usually > >Length; it is of course possible to make Length O(1) by keeping a count, > >but that doesn't seem to be necessary. I would want every operation to > >have its time complexity and pre- and post-conditions (where applicable) > >clearly documented. > > I think a lot of us are suffering under a bit of a terminology disconnect here. > I'm used to thinking of "lists" as bascily any linearly linked structure. In a > way, that means it is the union of queues, stacks, and any other nifty concept > that you can come up with using a lineraly linked-list. Thus using our "List" > type, you ought to be able to simulate any of those other aforementioned > structures. But they are all types of lists, and saying a stack isn't a list is > as confusing to me as saying a penny isn't a coin. > > Some people however appear to think of "List"s as a specific type of structure > with specific implementations and algorithms. I'm sure somewhere there's a > language or even perhaps a whole software engineering discipline that uses that > definition for lack of a better name (good terms for different types of lists > must be awfully hard to come by once you get a good half a dozen or more of > them). > > On the off chance that I'm just way obsolete in my knowledge (My last algorithms > course was 5 whole years ago. It could happen.), I went on a web hunt to see if > I could find any general source of computing knowledge that uses List in the > latter way rather than the former. I came up blank. I did find a few supporting > the former though: > > http://hissa.nist.gov/dads/HTML/list.html (Dictionary of Algorithms, Data > Structures, and Problems at NIST) > > http://foldoc.doc.ic.ac.uk/foldoc/foldoc.cgi?query=list&action=Search (Foldoc, > which is always my authoratitive source, but it is user-submitted...) > > There were also numerous online Data Structures texts that used "Lists" as a > heading, with stuff like "Singly Linked Lists" and "Doubly Linked Lists" as > subheadings. > > Anyway, the strawman was presented with the impression that the goal was to > create a simple basic "List" type from which Queues, stacks, and the like can be > implemented by the user. Acutal implementations of course have to be hashed out, > but I don't believe it was anyone's intention to specify a particular > implementation by choosing the word "List". Just the opposite, in fact. > > --- > 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.