In Java, why is insertion or deletion in a Linked List a constant time operation? Isn't it misleading?

Insertion or deletion of an element at a specific point of a list, assuming that we have a pointer to the node already, is a co开发者_开发技巧nstant-time operation. - from the Wikipedia Article on Linked list

Linked list traversal in a single linked list always starts from the head. We have to keep going till we satisfy a given condition.

So that will make any operation worst case O(n) unless we are dealing with the head node.

We CANNOT DIRECTLY go to a given pointer in a linked list. So why is it said that it is a constant time operation?

EDIT: Even if we have a pointer to the node, we have to start from the head only right? So how is it constant time operation

First of: the LinkedList implemented in the Sun JDK effectively has a link to the last element as well as to the first element (there's only a head entry, but head.previous points to the last element). This means that even in the worst case navigating through a list to an element indicated by an index should take n/2 operations. It's also a doubly linked list.

Apart from that: inserting into the beginning or end of a LinkedList is trivially O(1), because you don't need to traverse all elements.

Inserting/removing anywhere else depends on how exactly you do it! If you use an Iterator (of a ListIterator for adding) then the operation can be O(1) as well, as the Iterator will already have a reference to relevant entry.

If, however, you are using add(int, E) or remove(int), then the LinkedList will have to find the relevant entry (O(n)) and then remove the element (O(1)), so the entire operation will be O(n).

You said it yourself: "assuming we have a pointer to the node already". That avoids the traversal you identify as the cause of the linear time.

Admittedly, the Wikipedia text is a bit ambiguous, since there are two nodes involved: the one being inserted, and the one in the list where to insert it.

" assuming that we have a pointer to the node already, is a constant-time operation"

You missed the first assumption, it seems.

You are missing the point I think here. It is just the INSERTION and DELETION that have a constant time not the finding the point of insertion or deletion as well! The time is constant because you simply need to set the references (links) to the previous and next item in the list -- whereas for instance with ArrayList, in the case of insertion you need to allocate memory for (at least) one more item and transfer the existing data into the newly allocated array (or with deletion you have to shift elements in the array around once you deleted the item).