senshi nakamora - 2 months ago 20

Java Question

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`

.