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,LOTS_OF_MONEY
	autolearn=ham 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 17:29:25 PST
Path: 
 archiver1.google.com!news1.google.com!newsfeed.stanford.edu!newsfeeds.belnet.be!news.belnet.be!newsfeed00.sul.t-online.de!newsfeed01.sul.t-online.de!t-online.de!fu-berlin.de!uni-berlin.de!ppp-1-18.cvx6.telinco.NET!not-for-mail
From: "Nick Roberts" <nickroberts@adaos.worldonline.co.uk>
Newsgroups: comp.lang.ada
Subject: Re: List container: Insert and Delete
Date: Tue, 13 Nov 2001 00:44:32 -0000
Message-ID: <9spt1i$14snic$2@ID-25716.news.dfncis.de>
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>
 <D6TH7.21816$xS6.33411@www.newsranger.com>
NNTP-Posting-Host: ppp-1-18.cvx6.telinco.net (212.1.156.18)
X-Trace: fu-berlin.de 1005614962 38690380 212.1.156.18 (16 [25716])
X-Priority: 3
X-MSMail-Priority: Normal
X-Newsreader: Microsoft Outlook Express 5.50.4133.2400
X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4133.2400
Xref: archiver1.google.com comp.lang.ada:16381
Date: 2001-11-13T00:44:32+00:00
List-Id: <comp.lang.ada>

"Ted Dennison" <dennison@telepath.com> wrote in message
news:D6TH7.21816$xS6.33411@www.newsranger.com...
> 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.

Okay, I'm convinced. I'm in the process of rewriting my proposal with a
comprehensive set of 'cursor' operations (in addition to the index-based
ones, which are relegated to deprecated relative to the cursor operations).

I'll e-mail this to you (Ted) maybe Wednesday (probably very busy tomorrow).
I'll also produce an implementation as quick as I can (despite the large
number of operations).

Thanks in advance for your forebearance.

--
Best wishes,
Nick Roberts