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 11:59:06 PST Path: archiver1.google.com!news1.google.com!sn-xit-02!supernews.com!isdnet!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!feed1.uncensored-news.com!propagator-la!news-in-la.newsfeeds.com!news-in.superfeed.net!newsranger.com!www.newsranger.com!not-for-mail Newsgroups: comp.lang.ada From: Ted Dennison 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> 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 14:59:02 EST Organization: http://www.newsranger.com Date: Tue, 13 Nov 2001 19:59:02 GMT Xref: archiver1.google.com comp.lang.ada:16439 Date: 2001-11-13T19:59:02+00:00 List-Id: In article <3BF14752.B3F3FBC@boeing.com>, Jeffrey Carter says... > >I've never actually encountered a situation that needed a bounded list, >so I really can't comment (not that I'll let that stop me). I have >encountered situations that needed a bounded queue, however. I have 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.