On Wed, 30 Mar 2011 11:52:15 -0400, Daniel Gibson <[email protected]>
wrote:
Am 30.03.2011 17:31, schrieb Steven Schveighoffer:
On Wed, 30 Mar 2011 11:27:19 -0400, Daniel Gibson
<[email protected]> 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
