On 03/30/2011 05:01 PM, Steven Schveighoffer wrote:
On Wed, 30 Mar 2011 10:45:19 -0400, KennyTM~ <[email protected]> wrote:
On Mar 30, 11 21:09, 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.
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).
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).
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.
Precisely. It's also very well adapted for input/forward ranges, since all
operations happen at front. What do you think? (The kind of ranges that may
hold their contents). Note that the semantics of range iteration is clearly
analogous to list iteration:
while (node) {
element = node.element;
doSomethingWith(element);
node = node.next;
}
while (! r.empty) {
element = f.front;
doSomethingWith(element);
r.popFront();
}
(Only that range vocabulary is imo rather weird:
while (r.hasNext) {
element = r.nextElement;
doSomethingWith(element);
r.moveNext();
}
)
Denis
--
_________________
vita es estrany
spir.wikidot.com
