GSoC-2011 project:: Containers

[spir]

On 03/30/2011 03:09 PM, Steven Schveighoffer wrote:
> On Wed, 30 Mar 2011 04:55:52 -0400, KennyTM~ <kennytm at gmail.com> wrote:
>
>> No, the big difference is you can't move backward in a singly-linked list.
>> So, for instance, SList can only have linearRemove, while (doubly-linked)
>> List can have a constant-time remove.
>
> I hate to point it out, but any linked list implementation, whether it be
> single or double-linked, which does not support O(1) removal is 100% useless.
> Might as well use an array.

Do you mean removal of an already accessed node/value? If yes, then removal can 
effectively be O(1), but to first get the access (here, via a pointer) one 
needs O(n) traversing the list in any case. This, even when the lookup is by 
index, unlike arrays for which access is O(n) only when looking for a given 
value. So, for me O(1) removal is half of the story (same reasoning applies to 
change, insert, slice...). Or do I miss something?

As I understand it, link lists are only for "sequential collections" which 
never change, or only on their front. Thus, I like them for simple lists in the 
common sense, queue-like collections, or... input/forward ranges ;-). Else, 
they're close to useless, especiallly in a language like D with it's powerful 
arrays/slices.

Denis
-- 
_________________
vita es estrany
spir.wikidot.com