3

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

senshi nakamora
  • 65
  • 1
  • 1
  • 6
  • 3
    It depends on whether you have to search for the element you wish to remove or already have a reference to that element (for example if you are removing the current element while iterating over the list). – Eran Nov 07 '16 at 12:40
  • 3
    Removing itself is *O(1)* that exam answer does (for some reason?) also includes the search for an element (which is *O(n)*) – UnholySheep Nov 07 '16 at 12:40
  • 1
    https://stackoverflow.com/questions/559839/big-o-summary-for-java-collections-framework-implementations – Charmin Nov 07 '16 at 12:41
  • Depends if you define deleting as 'finding and removing' or just 'removing'. – d.j.brown Nov 07 '16 at 12:41
  • Also see: http://stackoverflow.com/questions/559839/big-o-summary-for-java-collections-framework-implementations – GhostCat Nov 07 '16 at 12:41
  • 2
    So that means that when I remove an item I have to search for it O(n) and then delete it O(1) so totally is O(n)+O(1) = O(n) ... Is it like that? Thanks – senshi nakamora Nov 07 '16 at 12:43
  • 1
    @senshinakamora yes, the time-complexity of removing a node is constant O(1) and not related to the number of nodes in the list. However, finding the node to start with is O(n), dependant upon the number of nodes in the list (linear search). – d.j.brown Nov 07 '16 at 12:48
  • @ d.j.brown @Eran @ UnholySheep Is it correct if I want to add an item to the linked list it takes O(1) without having to go through the elements? – senshi nakamora Nov 07 '16 at 12:48
  • @senshinakamora if you maintain a reference to the last node in the list, yes. – d.j.brown Nov 07 '16 at 12:49
  • @ d.j.brown thank you :) – senshi nakamora Nov 07 '16 at 12:51

3 Answers3

5

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.

kgeorgiy
  • 1,477
  • 7
  • 9
3

The element to remove has to be found. This finding is rather slow, because in the worst case the whole list has to be traversed to find the item. The removal itself is cheap. So finding is O(n) and removing is O(1). Is this just a theoretical problem?

Stimpson Cat
  • 1,444
  • 19
  • 44
1

Linked list have

  1. O(n) for get
  2. O(1) to add
  3. O(n) for contains
  4. O(1) for next
  5. O(1) for remove already found element

see image below:

enter image description here

xenteros
  • 15,586
  • 12
  • 56
  • 91
ΦXocę 웃 Пepeúpa ツ
  • 47,427
  • 17
  • 69
  • 97
  • 1
    What’s `remove(O)`?? `LinkedList()` has `remove()`, `remove(Object)` and `remove(int)`. The no-arg remove removes the first element, and I would expect it to be O(1). The two others should be O(n) since, as you say, the element to be removed is not yet found. – Ole V.V. Nov 07 '16 at 12:59
  • @OleV.V. `remove(0)` is removing a first element of the list. "The no-arg remove removes the first element, and I would expect it to be O(1)" - and in the LinkedList row in the table above it is `O(1)` in . "The two others should be O(n)" - and they are `O(n)`. "since, as you say, the element to be removed is not yet found." - not true, in `ArrayList` you need to shift all the elements, while in `CopyOnWriteArrayList` you have to copy entire array. – Jaroslaw Pawlak Nov 07 '16 at 13:12
  • Oh, it’s the number zero, not the capital letter. Thx for explaining. I was talking about the `LinkedList` implementation of the methods only, meaning that `LinkedList.remove(Object)` and `LinkedList.remove(int)` are both O(n), so I think we agree all the way. – Ole V.V. Nov 07 '16 at 13:31