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,e382b50ddc696050 X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2001-12-09 13:21:23 PST Path: archiver1.google.com!news1.google.com!sn-xit-02!supernews.com!newsfeed.direct.ca!look.ca!feed2.news.rcn.net!rcn!newsfeed1.earthlink.net!newsfeed.earthlink.net!newsmaster1.prod.itd.earthlink.net!newsread2.prod.itd.earthlink.net.POSTED!not-for-mail Message-ID: <3C13D5C8.D02EC087@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: Basic Properties of Lists References: <3C0DB9D0.7184868A@acm.org> <3C0EB851.77E7172A@boeing.com> <3C0FAF78.6F006DF7@boeing.com> <3C110606.A37E9D10@boeing.com> <8%8Q7.53294$xS6.88020@www.newsranger.com> <3C114702.98662A90@boeing.com> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Date: Sun, 09 Dec 2001 21:21:31 GMT NNTP-Posting-Host: 209.86.209.200 X-Complaints-To: abuse@earthlink.net X-Trace: newsread2.prod.itd.earthlink.net 1007932891 209.86.209.200 (Sun, 09 Dec 2001 13:21:31 PST) NNTP-Posting-Date: Sun, 09 Dec 2001 13:21:31 PST Organization: EarthLink Inc. -- http://www.EarthLink.net X-Received-Date: Sun, 09 Dec 2001 13:21:22 PST (newsmaster1.prod.itd.earthlink.net) Xref: archiver1.google.com comp.lang.ada:17653 Date: 2001-12-09T21:21:31+00:00 List-Id: Mark Lundquist wrote: > > Look, you guys both know what a doubly-linked list is; you don't need some > double-dome to weigh in with a ruling on it! I'm not talking about a doubly linked list; that's an implementation. I'm talking about the abstract concept of a list. The abstraction is completely random access and may be traversed in either direction, yet still has a default ordering from first to last. The statement "This list is sorted into ascending order" is meaningful for the abstraction, without having to say in which direction. A doubly linked implementation of a list allows reverse order traversal with O(N) time complexity, but with the penalty of an additional O(N) storage. A singly linked implementation of a list saves this additional storage, but with the penalty that reverse traversal has O(N**2) time complexity. They are both implementations of the same abstraction; they both have a default ordering from first to last. The statement "This list is sorted into ascending order" is meaningful for both of them, without having to specify a direction. An implementation doesn't affect the abstraction being implemented. -- Jeff Carter "Hello! Smelly English K...niggets." Monty Python & the Holy Grail