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 autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,7ee10ec601726fbf X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2001-11-01 08:07:54 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: why not Date: Thu, 1 Nov 2001 10:08:52 -0500 Organization: Posted on a server owned by Pace Micro Technology plc Message-ID: <9rroi6$9rs$1@nh.pace.co.uk> References: <3BC5D730.DA950CC7@boeing.com> <9q4pa7$1ad$1@nh.pace.co.uk> <3BC6ACC8.23EF21BC@free.fr> <3BC71F54.1FFE78FA@boeing.com> <1KGx7.26476$ev2.35117@www.newsranger.com> <3BC7AD82.2A0CCCD4@acm.org> <9qhiqr$af0$1@nh.pace.co.uk> <1nDC7.180$6S7.92255364@newssvr11.news.prodigy.com> <9rjsak$bp3$1@nh.pace.co.uk> <9rmhb9$o1b$1@nh.pace.co.uk> <3BDEF0FE.B55FED9E@san.rr.com> <9rmuqi$es$1@nh.pace.co.uk> <3BDF1F13.4B99361C@san.rr.com> <9rnbtv$5i4$1@nh.pace.co.uk> <3BE03E54.57E0E6C8@san.rr.com> <3BE0F8AE.3B7E5C70@home.com> NNTP-Posting-Host: dhcp-200-133.miami.pace.co.uk X-Trace: nh.pace.co.uk 1004627334 10108 136.170.200.133 (1 Nov 2001 15:08:54 GMT) X-Complaints-To: newsmaster@news.cam.pace.co.uk NNTP-Posting-Date: 1 Nov 2001 15:08:54 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:15545 Date: 2001-11-01T15:08:54+00:00 List-Id: If by "Dequeue" you mean "Double Ended Queue", then I disagree. A Dequeue is a special case of a double-linked list. Data may only enter/exit from the ends. What if you want to insert data into the middle? Strictly speaking, the only elements that should be visible in a Dequeue would be those at the ends, so how do you scan the entire structure? Relax the definition? By doing so, you just move closer and closer to a doubly-linked list. That's why I would contend that a doubly-linked list would be a good basic starting point. You can get all the behavior of a stack, queue, dequeue and singly-linked list out of it just by ignoring features. You get some small additional penalty of maintaining two links per node where on some structures you'd only need one, but in my experience it is negligable in most applications. A doubly-linked list and a map would cover a huge percentage of the usual data structure usages. Anything more could be discussed and added as a perceived need arose. 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/ "Mark Biggar" wrote in message news:3BE0F8AE.3B7E5C70@home.com... > > I not sure here. I thing that a list type is too low level, the actual > ADT that you want is a Dequeue ADT not Double-linked List ADT. > > Just like we already have bounded and unbounded strings, we should > have bounded and unbounded Dequeues. The fact that the later > can be implemented as a Double-linked list is an implementation > detail.