GSoC-2011 project:: Containers
spir
denis.spir at gmail.com
Wed Mar 30 08:14:20 PDT 2011
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
More information about the Digitalmars-d
mailing list