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

[Jesse G. <je...@wi...>]

Nicolas Cannasse wrote:

>> > 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.

:)

I don't have the energy or the desire to argue. Anyone who wants it
can download Dllist from my site. I'll maintain it and develop it
further unless a safer alternative is realized.

In the meantime, if anyone really thinks it belongs in ExtLib, then
please, by all means, argue with Nicolas. I've got other stuff to
code. Have fun!


-- 
Jesse Guardiani, Systems Administrator
WingNET Internet Services,
P.O. Box 2605 // Cleveland, TN 37320-2605
423-559-LINK (v)  423-559-5145 (f)
http://www.wingnet.net