Project ForgeLet 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?
- ASLLdel is O(1) and DLLdel is O(n)
- BBoth SLLdel and DLLdel are O(log(n))
- CBoth SLLdel and DLLdel are O(1)
- SLLdel is O(n) and DLLdel is O(1)
Explanation
To delete a node, you must relink its PREDECESSOR to its successor. In a singly-linked list, a node has no back-pointer, so finding its predecessor requires traversing from the head until the node just before it is found — O(n) worst case, even though you already have a pointer to the node itself. In a doubly-linked list, each node has a 'prev' pointer directly, so the predecessor is found in O(1), and relinking takes O(1) regardless of list size or head pointer.
Source: GATE CS 2023 (2023)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.