On Wed, 30 Mar 2011 14:21:35 -0400, spir <denis.s...@gmail.com> wrote:
On 03/30/2011 05:01 PM, Steven Schveighoffer wrote:
On Wed, 30 Mar 2011 10:45:19 -0400, KennyTM~ <kenn...@gmail.com> wrote:
On Mar 30, 11 21:09, Steven Schveighoffer wrote:
On Wed, 30 Mar 2011 04:55:52 -0400, KennyTM~ <kenn...@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?
Because it's O(1) insertion/removal at front (not only of elements, also
of sublists).
I have O(1) insertion/removal at the end of an array. Just call the end
the "front" and you have the same thing.
BTW, deque supports O(1) insertion and removal at both ends.
And yes, you can, if you have a pointer to the element right before the
insertion/removal point.
Sure, but what kind of programming sorcery provides this pointer without
O(n) traversal? (See my other post).
You are not getting it.
SList's implementation to remove the element containing 5:
auto r = find(mySList[], 5); // O(n) operation
mySList.linearRemove(take(r, 1)); // O(n) operation, even though I just
searched for the element.
Expected implementation:
auto r = find(mySList[], 5); // O(n) operation
mySList.remove(take(r, 1)); // O(1) operation
If the second operation is O(n), *EVEN THOUGH YOU JUST GOT A POINTER TO
IT*, then the list is a failure. An SList range should retain enough info
to be able to remove its front element, it's not that hard.
From en.wikipedia.org:
"The principal benefit of a linked list over a conventional array is that
the list elements can easily be added or removed without reallocation or
reorganization of the entire structure because the data items need not be
stored contiguously in memory or on disk. Linked lists allow insertion and
removal of nodes at any point in the list, and can do so with a constant
number of operations if the link previous to the link being added or
removed is maintained during list traversal."
-Steve
