Darren New <dne### [at] sanrrcom> wrote:
> http://doc.trolltech.com/4.2/containers.html#algorithmic-complexity

  Everybody always says that "inserting in the middle of a linked list is
a constant-time operation". My response to that is: "Ok, if that is so, then
give me a function which takes a linked list and an element as parameters,
and make the function insert the element in the exact middle of the list in
constant time. I'll wait."

  The claim is rather imprecise. You can't just magically insert an element
in the middle of a list in constant time. You have to get there somehow first.
Only if you happen to have, from some previous operation, an iterator pointing
to the place where you want to insert, *then* it will be a constant-time
operation.

  A more precise wording would be: "Inserting an element in a linked list at
the location pointed by any given iterator is a constant-time operation."
Then the complexity of the thing is left to getting said iterator.

-- 
                                                          - Warp

Post a reply to this message