How the remove operation in LinkedList is of O(1) time complexity?

[Ramakant Biswal]

How the remove operation in LinkedList is of O(1) time complexity where as the contains is of O(n).
We know the contains or remove operation does not give us the index based search, so in both the cases it should iterate the entire LinkedList which is of O(n)
but how remove operation is O(1)?? Am I missing some point here.

[Jeanne Boyarsky]

Could it be referring to removing from the head of the list rather than a random position?

[Bin Smith]

Hello Ramakant !

The remove operation in LinkedList is O(1) only if you remove element which is at any of two ends of linked list.
This is the best case and this is what LinkedList for - to add,remove elements sequentially.

However you may get into very bad situation if you try to use method remove(Object o) tryng to remove element at the tail of linked list.
Don't use this method unless you know what you do!
Instead of it use either method removeLastOccurrence or removeFirstOccurrence depending on the end your element to remove is closer to.
Frankly if you are not aware where your element is you may get into worst possible case which is O(n).

Finally to know more about LinkedList cover my Internal life of LinkedList tutorial.

[Paul Clapham]

Ramakant Biswal wrote:How the remove operation in LinkedList is of O(1) time complexity where as the contains is of O(n).

Who said it was?

Actually it's an O(1) operation to remove a node from a linked list if you have a reference to that node. However the remove() method of Java's LinkedList class does two things: (1) It finds the node and gets a reference to it; (2) it removes that node. The first of those two is O(n) and the second is O(1), so the combination of the two is O(n).

So be careful when you read what somebody says about operations on linked lists. It might not correspond to a similarly-named method on LinkedList.

[Winston Gutkowski]

Ramakant Biswal wrote:How the remove operation in LinkedList is of O(1) time complexity where as the contains is of O(n).

Just to add to the other good information:

There is a remove() that doesn't apply to the head or tail of a LinkedList, and that is O(1): The remove() method in its Iterator or ListIterator.

So if you have some method that goes through elements using an Iterator and then removes them using its method, each removal will work in O(1) time, for the reasons Paul already explained (removal of a Node is an O(1) operation).

HIH

Winston

[fred rosenberger]

I would think the removal of an element would always be O(1).

However, before you can remove it, you have to find/identify it. Finding it may be O(n).

[Jeanne Boyarsky]

fred rosenberger wrote:I would think the removal of an element would always be O(1).

No. This is true about a doubly linked list, but not a singly linked list. (Which is usually what folks are talking about unless specified otherwise.)

Consider a doubly linked list A <--> B <--> C <--> D <--> E. Suppose I have a pointer/reference to D. To remove it, I do:

Find the predecessor (C) - O(1)

Find the successor (D) - O(1)

Change the predecessor's "next" to the successor (E) - O(1)

Change the successor "previous" to the predecessor's (C) - O(1)

Now, consider a linked list A --> B --> C --> D --> E. I still have a pointer/reference to D. To remove it, I do:

Find the predecessor (C) - O(n) - I have to search the list to find the predecessor so it isn't O(1)

Find the successor (E) - O(1)

Change the predecessor's "next" to the successor (E) - O(1)

Change the successor "previous" to the predecessor's (C) - O(1)

[fred rosenberger]

Jeanne Boyarsky wrote:No. This is true about a doubly linked list, but not a singly linked list. (Which is usually what folks are talking about unless specified otherwise.)

point conceded.