Time complexity of node deletion in singly- and doubly-linked lists

Question

Why is the time complexity of node deletion in doubly linked lists (O(1)) faster than node deletion in singly linked lists (O(n))?

Answer 1

The problem assumes that the node to be deleted is known and a pointer to that node is available.

In order to delete a node and connect the previous and the next node together, you need to know their pointers. In a doubly-linked list, both pointers are available in the node that is to be deleted. The time complexity is constant in this case, i.e., O(1).

Whereas in a singly-linked list, the pointer to the previous node is unknown and can be found only by traversing the list from head until it reaches the node that has a next node pointer to the node that is to be deleted. The time complexity in this case is O(n).

In cases where the node to be deleted is known only by value, the list has to be searched and the time complexity becomes O(n) in both singly- and doubly-linked lists.

Answer 2

Actually deletion in singly linked lists can also be implemented in O(1).

Given a singly linked list with the following state:

SinglyLinkedList:    Node 1 -> Node 2    Node 2 -> Node 3    Node 3 -> Node 4    Node 4 -> None     Head = Node 1 

We can implement delete Node 2 in such a way:

Node 2 Value <- Node 3 Value Node 2 -> Node 4 

Here we replace the value of Node 2 with the value of its next node (Node 3) and set its next value pointer to the next value pointer of Node 3 (Node 4), skipping over the now effectively "duplicate" Node 3. Thus no traversal needed.