Question

In a singly linked list, what is the time complexity to delete a node given a pointer to that specific node?

• A. $O(1)$
• B. $O(n)$
• C. $O(\log n)$
• D. $O(n^2)$

Hint:

In a Doubly Linked List, this operation would be $O(1)$ because every node has a "prev" pointer, allowing you to identify the predecessor immediately without traversing the list.

Answer 1

The Correct Option is B

Concept: Deletion in a linked list requires updating the "next" pointer of the preceding node so that it bypasses the node to be deleted.
• Singly Linked List: Nodes only point forward. To find a node's predecessor, you must start from the head.
• Pointer given: You have the address of the node to be deleted, but not its predecessor.

Step 1: Finding the predecessor node.
Because nodes only have a "next" pointer, you cannot look "backwards" to find the previous node. The only way to find the predecessor is to start at the head and traverse the list.

Step 2: Quantifying the traversal work.
In the worst case, the node to be deleted is at the very end of the list. You must visit $n-1$ nodes to find the predecessor. This linear traversal takes $O(n)$ time.

Step 3: Special Cases and Tricks.
While a "copy-data-from-next" trick exists to delete in $O(1)$, it fails for the last node. In standard computational theory and for general cases, the complexity is cited as $O(n)$.