Linked list removal operation time complexity O(n) vs O(1)

Question

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?

Answer 1

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 :)

Answer 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.