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.3 required=5.0 tests=BAYES_00, REPLYTO_WITHOUT_TO_CC autolearn=no autolearn_force=no version=3.4.4 Path: border2.nntp.dca1.giganews.com!nntp.giganews.com!newspeer1.nac.net!feeder.erje.net!eu.feeder.erje.net!news2.arglkargh.de!news.mixmin.net!aioe.org!.POSTED!not-for-mail From: "Dmitry A. Kazakov" Newsgroups: comp.lang.ada Subject: Re: Queue implementation in Ada Date: Tue, 28 Oct 2014 21:27:18 +0100 Organization: cbb software GmbH Message-ID: <9sd2vpz1poca$.vxcydglas2sm$.dlg@40tude.net> References: <8456b674-a10d-411f-bcf6-90d9638b7fc9@googlegroups.com> Reply-To: mailbox@dmitry-kazakov.de NNTP-Posting-Host: Xn+ybM2JynFOXdIT5N5zBw.user.speranza.aioe.org Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit X-Complaints-To: abuse@aioe.org User-Agent: 40tude_Dialog/2.0.15.1 X-Notice: Filtered by postfilter v. 0.8.2 Xref: number.nntp.giganews.com comp.lang.ada:190175 Date: 2014-10-28T21:27:18+01:00 List-Id: On Tue, 28 Oct 2014 19:25:20 +0000, Simon Wright wrote: > I've been put off Doubly_Linked_Lists because I would usually have been > quite happy with singly linked lists. But really, what difference does > it make if all you're doing is implementing a Queue! Much. Singly-linked list is LIFO because only one end has O(1) insertion/deletion. For a FIFO it is O(1) at one end and O(n) at another. Thus the overall complexity is O(n), which is catastrophic. Doubly-linked list has O(1) at any of its ends (and at any element in between). However, using doubly-linked lists is an overkill for queues. Furthermore, it requires dynamic memory allocation and maintenance of the list of free elements (to reduce allocate/deallocate penalty). It is also not a very good idea to let the queue grow infinitely. Usually a fixed size ring buffer array is a better choice for a queue. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de