Re: List container: Insert and Delete

["Nick Roberts" <nickroberts@adaos.worldonline.co.uk>]

"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