Given a pointer to a node in a doubly linked list, what is the time complexity of deleting that node?
Correct answer D. O(1)
Explanation
A doubly linked node knows its predecessor, so you can link prev.next to node.next and next.prev to node.prev directly, which takes constant time. In a singly linked list the same deletion needs the predecessor, and finding it usually requires an O(n) walk from the head. This is one of the main benefits that justifies the extra pointer per node.
Answer checked How we write and check questions
Discussion