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

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download