Let SLLdel be a function that deletes a node in a singly-linked list given a pointer to the node and

Q: What is GATE-CS?

GATE-CS is a competitive examination conducted in India. This question is from the 2023 GATE-CS Data Structures paper.

Q: How can I prepare for GATE-CS Data Structures?

To prepare for GATE-CS Data Structures, practice previous year questions (PYQs), understand concepts thoroughly, and solve mock tests regularly. This 2023 question covers Linked Lists topic.

Q: What is the difficulty level of this question?

This GATE-CS 2023 Data Structures question has a easy difficulty level and is marked as an important question.

Q: Where can I find more GATE-CS previous year questions?

You can find more GATE-CS previous year questions on AspirantMitraa. Browse by subject, topic, year, and difficulty level to practice effectively.

Question

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 delete a node in a doubly-linked list given a pointer to the node and a pointer to the head. Let n denote the number of nodes. Which one of the following choices is TRUE about the worst-case time complexity of SLLdel and DLLdel?

Accepted Answer

Correct Answer: (D) SLLdel is O(n) and DLLdel is O(1)Concept -- Linked List Deletion Complexity (from Cormen et al., Introduction to Algorithms):SLLdel in singly-linked list: To delete a node, we need to update the 'next' pointer of its predecessor. In a singly-linked list, given only a pointer to the node to be deleted, we cannot directly access the predecessor. We must traverse the list from the head to find the predecessor, which takes O(n) time in the worst case.DLLdel in doubly-linked list: In a doubly-linked list, each node has both 'next' and 'prev' pointers. Given a pointer to the node to be deleted, we can directly access its predecessor via the 'prev' pointer. Deletion simply requires updating the 'next' pointer of the predecessor and the 'prev' pointer of the successor. All operations are O(1).

Master GATE-CS with Our Test Series

More Questions from Linked Lists

Frequently Asked Questions

Master GATE-CS with Our Test Series

More Questions from Linked Lists

Frequently Asked Questions