senshi nakamora senshi nakamora - 1 year ago 89
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.

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

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


Answer Source

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.