The GATE Grind

GATE 2023 CS – Question 13

Programming and Data Structures · Linked Lists · 1 mark · Multiple choice

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?

  1. SLLdel is O(1) and DLLdel is O(n)
  2. Both SLLdel and DLLdel are O(log(n))
  3. Both SLLdel and DLLdel are O(1)
  4. SLLdel is O(n) and DLLdel is O(1)

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) SLLdel is O(n) and DLLdel is O(1)

Explanation

In a singly linked list the predecessor must be found by traversal from the head, which is O(n). A doubly linked list has a prev pointer, so deletion is O(1).