GSoC-2011 project:: Containers

[Steven Schveighoffer]

On Wed, 30 Mar 2011 11:52:15 -0400, Daniel Gibson <metalcaedes at gmail.com>  
wrote:

> Am 30.03.2011 17:31, schrieb Steven Schveighoffer:
>> On Wed, 30 Mar 2011 11:27:19 -0400, Daniel Gibson
>> <metalcaedes at gmail.com> wrote:

>>> Deleting within the list is different, yes, at least if you want to
>>> support something else than "delete next element" - in that case you
>>> only have to care about the additional pointers.
>>> Inserting (at least "insert after this element") is pretty similar,
>>> apart from some additional prev-pointers.
>>> I mostly thought about the other stuff (insert/remove at front/back)
>>> because that were my usecases in my single/double linked queue
>>
>> Insert at back for a singly-linked list is O(n).
>>
>> -Steve
>
> Not if you keep a pointer to the last element.
> Then it's just  last.next = newElem; last = newElem; or similar.
> But deleting the last element is O(n) (So I only supported that for the  
> doubly-linked queue).

This is equivalent to keeping a separate insertion point for  
back-insertion (i.e. can be implemented via insertAfter(node)).  But I  
agree, as long as you don't remove from the end, you can maintain that  
pointer and abstract the insertBack method.

-Steve