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=unavailable autolearn_force=no version=3.4.4
Path: 
 border1.nntp.dca1.giganews.com!nntp.giganews.com!usenet.blueworldhosting.com!feeder01.blueworldhosting.com!feeder.erje.net!eu.feeder.erje.net!news.swapon.de!eternal-september.org!feeder.eternal-september.org!mx02.eternal-september.org!.POSTED!not-for-mail
From: Simon Wright <simon@pushface.org>
Newsgroups: comp.lang.ada
Subject: Re: Queue implementation in Ada
Date: Tue, 28 Oct 2014 21:27:41 +0000
Organization: A noiseless patient Spider
Message-ID: <lymw8fx4tu.fsf@pushface.org>
References: <8456b674-a10d-411f-bcf6-90d9638b7fc9@googlegroups.com>
 <m2n2jl$d70$1@dont-email.me> <lyk33k7btz.fsf@pushface.org>
 <m2ona2$tv6$2@dont-email.me> <lyvbn4vvxb.fsf@pushface.org>
 <9sd2vpz1poca$.vxcydglas2sm$.dlg@40tude.net>
Mime-Version: 1.0
Content-Type: text/plain
Injection-Info: mx02.eternal-september.org;
 posting-host="e614caa3bbcdcdac946afd88f128a08d";
 logging-data="10155"; mail-complaints-to="abuse@eternal-september.org";
 posting-account="U2FsdGVkX19cbxwLR/wz5fU/ljP1IZ/HL51alxESgB0="
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3 (darwin)
Cancel-Lock: sha1:VFo/4XV+FJtGQxMVp0oni2+qzoI=
 sha1:u5L0crKLkbwMIMsHTYF6iE6XRJk=
Xref: number.nntp.giganews.com comp.lang.ada:190180
Date: 2014-10-28T21:27:41+00:00
List-Id: <comp.lang.ada>

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:

> Doubly-linked list has O(1) at any of its ends (and at any element in
> between).

The Booch Components are a counter-example to this assertion (I'm not in
any way saying that that's a good thing!); Append is indeed O(n).