On Wed, 30 Mar 2011 11:14:20 -0400, spir <[email protected]> wrote:
On 03/30/2011 03:09 PM, Steven Schveighoffer wrote:
On Wed, 30 Mar 2011 04:55:52 -0400, KennyTM~ <[email protected]> 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
