Re: [Ocaml-lib-devel] Re: new dllist (yet again)

[Nicolas C. <war...@fr...>]

> > Yeah, I'd be greatly (and pleasantly) surprised if Nicolas wants dllist
> > in ExtLib though.
>
> Huh? Quite a few of us have said we'd like some doubly
> linked list facility in Extlib. Extlib was intended
> to augment the set of fundamental data structures
> (and functions on them) provided by the Ocaml standard library.
>
> I have no doubt some kind of doubly linked list
> belongs in Extlib.  Exactly what is another issue :)

Well I have not yet been correctly answered to my question

"Could someone resume shortly the advantages of using a mutable double
linked
list against other existing ocaml data structures ? ( I guess it has to be
mutable since immutable dllist sounds efficientless)."

Brian said :

"O(1) removal of an element with a known location as opposed to O(log N)."

That means exactly O(1) removal when we have an enumeration pointer. That's
exactly the same complexity as a list using a filter on first matched
element isn't it ? So I don't yet see the advantages.

(BTW Brian it's ok to add IndexedTree to ExtLib if you want).

Nicolas