2007/5/25, Avi Bryant <avi at dabbledb.com>:
> On 5/25/07, nicolas cellier <ncellier at ifrance.com> wrote:
>
> > Yes, it transforms cost from O(N) to O(1).
> > That was some provocation.
> > Though, i tried using them once, they are not generic.
> > Only a specific thing tailored for Process List.
> > I should be ashamed to say that, but C++ std::list are really easier to
> > use than current LinkedList (I mean i cannot replace OrderedCollection
> > with LinkedList transparently).
>
> Either you can have transparency, or you can have O(1)
> insertion/removal, but I don't see how you can have both.  To get
> O(1), you have to have a reference to the link you want to remove or
> insert after, which isn't transparent; if you just had a regular
> object like you would put in an OrderedCollection, you would have to
> do a linear scan through the list to find the right link, and you're
> back to O(n).  No?

I think the LinkedList should create Links when adding elements. And
answer the value in the link when accessing the LinkedList. This
should be transparent.

-- 
Damien Cassou