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-12 08:51:49 PST
Path: 
 archiver1.google.com!news1.google.com!sn-xit-02!supernews.com!newsfeed.direct.ca!look.ca!upp1.onvoy!onvoy.com!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<dennison@telepath.com>
References: <3BECA3B7.5020702@telepath.com> <9sjf4n$odm$1@news.huji.ac.il>
 <GSWgHtJTqIbl@eisner.encompasserve.org>
 <9sjkc7$145mhb$1@ID-25716.news.dfncis.de> <3BEDACC0.9A314B54@acm.org>
 <9sktgm$134npc$3@ID-25716.news.dfncis.de> <3BEEB766.B50C969@acm.org>
 <9sn4qk$13g29j$1@ID-25716.news.dfncis.de>
Subject: Re: List container: Insert and Delete
Message-ID: <D6TH7.21816$xS6.33411@www.newsranger.com>
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: Mon, 12 Nov 2001 11:51:47 EST
Organization: http://www.newsranger.com
Date: Mon, 12 Nov 2001 16:51:47 GMT
Xref: archiver1.google.com comp.lang.ada:16334
Date: 2001-11-12T16:51:47+00:00
List-Id: <comp.lang.ada>

In article <9sn4qk$13g29j$1@ID-25716.news.dfncis.de>, Nick Roberts says...
>
>It's all very well saying access will be O(N), but that ignores the fact
>that chasing down a linked list of pointers is a fast operation (because

Not if there are 60000 of them to go through. What's worse is that you make
iterating through the entire list an O(N**2) operation, instead of O(N). This
effect compounds the time behavior for other operations the client might want to
do to. For example, if I were to try to use it to make my own custom sort
routine, which would normally be O(NlogN) average and O(N**2) worst case, using
an O(N) indexer changes it to O(N**2) average and O(N**3) worst case!

I wouldn't be horribly pained if some kind of "get me the n'th item" routine
were in there. But it *cannot* be the sole method for iteration in a
linked-list.

---
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.