GSoC-2011 project:: Containers

Steven Schveighoffer schveiguy at yahoo.com
Wed Mar 30 08:30:43 PDT 2011


On Wed, 30 Mar 2011 11:14:20 -0400, spir <denis.spir at gmail.com> wrote:

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

Of course.  With SList, you need O(n) to get to the element, and then O(n)  
to remove it once you find it ;)

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

insert also requires O(n) even with a reference to the insertion point in  
SList.

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

A deque has (amortized) O(1) removal and insertion at the front and end of  
it, plus has random access.

A list's main bonus is O(1) removal and insertion inside the list.  And if  
you do not keep track of the number of elements, it should also have O(1)  
splicing (inserting another list in the middle of a list, or removing a  
section of a list defined by two end points).

-Steve


More information about the Digitalmars-d mailing list