# What is the complexity of finding the predecessor of a node in a doubly linked list?

This is a question from Cormen 3rd edition(exercise 10.1). I am of the opinion that the complexity should be O(1), as we just have to look into the next pointer of the current node.

But the answers from the web suggest that it should be O(n). Where am I getting it wrong?

• Is the node whose predecessor you want given as input? Jun 27, 2018 at 18:11
• Just pointing out that, while it is true that the time complexity is $O(1)$, saying that it is $O(n)$ is still technically correct since $O(1) \subset O(n)$. Dec 21, 2023 at 22:57

Both answers look wrong. Time is indeed $O(1)$ because you can look into prev (not next) pointer of the node. The answers you found on the web are probably about single-linked lists.

I guess if you include the time it takes you to find a node X and its predecessor, then finding the node would be $O(n)$ and going back once will be $O(1)$, but this sounds unnecessary since we can directly find the predecessor.

I think I can clear this up:

Because you now have the predecessor prev, removal at the tail becomes faster because the time complexity is now 0(1). The logic behind it? The predecessor can now be renamed as the tail, which only needs to be done once for an individual removal. However, that does not mean removal in between the tail and the head is now 0(1). The time complexity for the algorithm for the middle part of the DLL is still 0(n) as you would still need to search for the item to remove.

Do correct me if any of this information is wrong. :)

Given a pointer to a node in a double linked list, getting a pointer to the previous node is constant time. That’s the whole purpose of double linked lists.

“Answers on the web” claiming O(n) will be answering some other question. Like the same question for a single linked list. Or finding a node.