• Post Reply Bookmark Topic Watch Topic
  • New Topic

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

 
Ramakant Biswal
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Eclipse IDE Java VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Could it be referring to removing from the head of the list rather than a random position?
 
Bin Smith
Ranch Hand
Posts: 514
1
Eclipse IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Sheriff
Posts: 22829
43
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Eclipse IDE Java VI Editor
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
    Chrome Java Linux
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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.
     
    • Post Reply Bookmark Topic Watch Topic
    • New Topic
    Boost this thread!