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?
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).
More Linked Lists questions
GATE 2022 CS Q15– Consider the problem of reversing a singly linked list. To take an example, given the…
GATE 2020 CS Q26– What is the worst case time complexity of inserting n elements into an empty linked list,…
GATE 2017 CS (CS1) Q18– Consider the C code fragment given below. Assuming that `m` and `n` point to valid…
GATE 2016 CS (CS2) Q25– N records are in a sorted doubly linked list. Node pointers are supplied for delete and…
GATE 2017 CS (CS2) Q23– A circular queue uses a singly linked list, with value and next-pointer per node and…
GATE 2010 CS Q46– For a singly linked list with at least two nodes, fill the blank to move its last node to…