Let SLLdel be a function that deletes a node in a singly-linked list given a…
2023
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?
- A.
SLLdel is O(1) and DLLdel is O(n)
- B.
Both SLLdel and DLLdel are O(log(n))
- C.
Both SLLdel and DLLdel are O(1)
- D.
SLLdel is O(n) and DLLdel is O(1)
Attempted by 408 students.
Show answer & explanation
Correct answer: D
Answer: SLLdel is O(n) and DLLdel is O(1).
Why: Consider what pointers are available and what must be updated.
Singly-linked list (SLL): Given the head and the node to delete, you normally must find the node's predecessor by traversing from the head. That traversal can take up to n steps in the worst case, so SLLdel is O(n).
Doubly-linked list (DLL): The node contains a pointer to its previous node, so you can update the adjacent pointers (previous.next and next.prev) directly and adjust head/tail if needed. Those pointer updates are constant-time, so DLLdel is O(1).
Notes: Deleting the head in an SLL is O(1). There is also a common trick to delete a non-tail node in an SLL in O(1) by copying data from the next node and bypassing it, but that does not handle the tail node and does not change the worst-case complexity when the tail or predecessor is required.
A video solution is available for this question — log in and enroll to watch it.