senshi nakamora senshi nakamora - 1 month ago 11
Java Question

big O notation for removing an element from a linked list

I was reading about linked lists. I found that : Removing an desired element from a linked list takes O(n) running time, where n is the number of
elements in the list.
http://www.cs.mcgill.ca/~dprecup/courses/IntroCS/Exams/comp250-final-2006-solutions.pdf

But in this webpage I found that deletion an element from a linked list is: O(1).
http://bigocheatsheet.com/

Which one of the above big O notation is the correct one for deletion from a linked list.

Thanks

Answer

The time required to remove the item from the linked list depends on how exactly we a going to do this. Here are possibilities:

  • Remove by value. In this case we need to find an item (O(n)) and remove it (O(1)). The total time is O(n).
  • Remove by index. In this case we need to traverse list (O(index)) and remove item (O(1)). The total time is O(index). For arbitrary index it is O(n).
  • Remove by the reference to the linked list node that contains the item O(1).

In Java the last case is met when you are using Iterator.remove or ListIterator.remove.