GATE CS 2023 Q3 — Linked Lists

To determine the worst-case time complexity of deleting a node from a singly-linked list ($\textsf{SLLdel}$) and a doubly-linked list ($\textsf{DLLdel}$), let us analyze the steps required for each:

1. Singly-Linked List ($\textsf{SLLdel}$)

• To delete a given node $P$ from a singly-linked list, we must update the next pointer of its predecessor node to point to $P\to\text{next}$.
• Since a singly-linked list only has forward pointers, we cannot directly access the predecessor of $P$.
• We must traverse the list starting from the head to find the predecessor node $Q$ such that $Q\to\text{next} = P$.
• In the worst case (for example, when $P$ is the last node in the list), this traversal requires visiting all $n$ nodes, which takes $O(n)$ time.
• Note: While a trick exists to copy the data of the next node into $P$ and delete the next node in $O(1)$ time, this trick fails if $P$ is the last node of the list. Thus, the worst-case time complexity remains $O(n)$.

2. Doubly-Linked List ($\textsf{DLLdel}$)

• In a doubly-linked list, every node contains pointers to both its successor (next) and its predecessor (prev).
• We can directly access the predecessor of $P$ using $P\to\text{prev}$ and the successor using $P\to\text{next}$.
• The deletion can be performed in constant time by updating the pointers:

  if (P->prev != NULL) P->prev->next = P->next;
  if (P->next != NULL) P->next->prev = P->prev;

• Since no traversal is needed, the worst-case time complexity is $O(1)$.

Thus, $\textsf{SLLdel}$ is $O(n)$ and $\textsf{DLLdel}$ is $O(1)$.