GATE 2023 CS Q.13: solution and answer

GATE 2023 · CSQ.13 · 1 mark · MCQ

Let SLLdel be a function that deletes a node in a singly-linked list given a pointer to the node and a pointer to the head of the list. Similarly, let DLLdel be another function that deletes a node in a doubly-linked list given a pointer to the node and a pointer to the head of the list.

Let $n$ denote the number of nodes in each of the linked lists. Which one of the following choices is TRUE about the worst-case time complexity of SLLdel and DLLdel?

(A)
SLLdel is $O (1)$ and DLLdel is $O (n)$
(B)
Both SLLdel and DLLdel are $O (lo g (n))$
(C)
Both SLLdel and DLLdel are $O (1)$
(D)
SLLdel is $O (n)$ and DLLdel is $O (1)$

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

SLLdel is O(n) and DLLdel is O(1) — option D.

Official answer: DSource: Official answer key, GATE 2023 CS (IIT Kanpur)

Deleting a node requires updating its predecessor's link (in a DLL, also the successor's prev link) to bypass the deleted node — the actual pointer surgery is O(1) once the predecessor is known.
In a singly-linked list, each node stores only a next pointer; there is no way to reach a node's predecessor from the node itself.
Hence SLLdel, given only a pointer to the node and the head, must traverse from the head to locate the predecessor before it can unlink the node. In the worst case (the target node near the tail), this traversal visits Θ(n) nodes, so SLLdel is $O (n)$ .
In a doubly-linked list, each node stores a prev pointer in addition to next, so the predecessor is available directly from the given node pointer — no traversal is needed.
DLLdel can therefore immediately update prev->next and next->prev to unlink the node, doing constant work regardless of $n$ , so DLLdel is $O (1)$ .
Thus SLLdel is $O (n)$ and DLLdel is $O (1)$ , which is option (D).

KEY IDEA

To unlink a node from a linked list you must update the predecessor's link field. A singly-linked node stores no back-pointer, so given only the node itself, finding its predecessor forces a scan from the head — O(n) worst case. A doubly-linked node already stores prev, so the predecessor is known instantly and unlinking (fixing prev->next and next->prev) is O(1).

WATCH OUT FOR

Assuming that since we're "given a pointer to the node," deletion can always be done in O(1) by copying the next node's data into the given node and deleting the next node (a common trick for other problems) — but here it must actually delete the node given (e.g., if it's the last node in an SLL, that trick fails, and worst case still requires finding the predecessor via head traversal since a plain singly-linked node has no back-link).

From the GATE 2023 CS paper. Every question of this paper · Download the full paper · All 13 Linear structures questions, with notes

GATE 2023 CS Q.13: solution and answer

Answer and solution

More Linear structures questions