1

As I am reviewing big O notation for data structures and algorithms, I am confused when different sources place a O(n) time complexity for deleting a node from a linked list vs O(1). For example, big O cheat sheet places O(1) when deleting a node where as I believed that removing a node would be O(n) because you must find the node first and then delete it.

So my question is, does the time complexity of O(1) just assume the operation of deletion itself without taking into consideration that the node must be found first? Let us assume that the node to be deleted is anywhere in the list not just at the front or end of the list.

I have reviewed the following questions, but they do not address my question:

big O notation for removing an element from a linked list

Big-O summary for Java Collections Framework implementations

What are the time complexities of various data structures?

Doctor J
  • 27
  • 1
  • 7
  • Yes indeed it depends on the context, really the question should be better stated. Deletion here means you are given the reference of the node and wish to delete it. – Countingstuff Jan 13 '19 at 22:01
  • Better stated in what sense? – Doctor J Jan 13 '19 at 22:02
  • Without a halfway precise description of an operation, any complexity claim is useless. That said, the Big-O complexities assume a pretty simple execution model made up of pretty simple operations. Just read an introduction on the theoretical background of it. – Ulrich Eckhardt Jan 13 '19 at 22:03
  • 1
    Sorry question was the wrong word (I don't mean your question, I think I was assuming you had been asked the question of time complexity...), I mean the statement about time complexity made in whatever you're reading should be made more precisely. It should be 'Given we have the reference to a node in a linked list, what time complexity is the operation of removing it and 'fixing' the linked list'. – Countingstuff Jan 13 '19 at 22:05

2 Answers2

2

The answer to your question is: yes.

Typically, when the O(1) time complexity is stated for insertion or deletion in a linked list, it is assumed that a pointer to the node in question is already known. This isn't totally useless, however. Consider the case where you want to traverse a list and remove elements matching a certain description. With a linked list, this can be done in O(n) time with O(1) additional space. With an array, this would typically require O(n^2) time or O(n) additional space.

Ryan Amos
  • 5,422
  • 4
  • 36
  • 56
2

According to the first thread you reviewed, the time complexity O(1) does refer to deleting a node that's already identified.

If you click the "single-linked list" link on the big-O page you reviewed, you can get more info about the functions involved (including the code) - here. This should answer your question accurately :)

Alexandre FERRERA
  • 328
  • 1
  • 7