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?

Avi