GSoC-2011 project:: Containers

[Steven Schveighoffer]

On Wed, 30 Mar 2011 10:45:19 -0400, KennyTM~ <kennytm at gmail.com> wrote:

> On Mar 30, 11 21:09, 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.
>>
>> Andrei, you really need to fix that.
>>
>> -Steve
>
> You can't O(1) remove an arbitrary range from an SList. O(1) removal is  
> possible only if you also know an iterator right before the range.

If you have a linked list of any type, and can't do O(1) insertion or  
removal of a single element, then you have failed.  Linked list's complete  
advantage is arbitrary O(1) insertion and removal.  Arrays have O(n)  
insertion and removal, with random access.  Why would I ever use SList in  
its current form when it has the same complexity as but less features than  
a builtin array?

And yes, you can, if you have a pointer to the element right before the  
insertion/removal point.  This is somewhat ugly, but is the cost of having  
a singly linked list.  I can guarantee anyone who knows what they are  
doing is never going to use SList, unless they are just interested in a  
stack type.

-Steve