programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

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

Ramakant Biswal
Greenhorn
Posts: 4
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
author & internet detective
Marshal
Posts: 37488
539
Could it be referring to removing from the head of the list rather than a random position?

Bin Smith
Ranch Hand
Posts: 514
1
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).

Paul Clapham
Sheriff
Posts: 22829
43
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
Bartender
Posts: 10575
66
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
lowercase baba
Bartender
Posts: 12563
49
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
author & internet detective
Marshal
Posts: 37488
539
• 1
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
lowercase baba
Bartender
Posts: 12563
49
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.