Discussion
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?
Answer: D
SLLdel is \(O(n)\) and DLLdel is \(O(1)\).
To unlink a node from a singly-linked list, the previous node's next pointer must be changed, and a singly-linked node has no pointer back to its predecessor. SLLdel must therefore walk from the head to find it, which takes up to n steps when the node is near the end. (Copying the next node's data into the node does not help in the worst case, because it fails for the last node.)
In a doubly-linked list the node carries a prev pointer, so DLLdel can reset the predecessor's next pointer and the successor's prev pointer directly, a constant number of steps.
So 'SLLdel O(1), DLLdel O(n)' is backwards, 'both O(1)' ignores the search, and no list operation here is logarithmic, which rules out \(O(\log(n))\).
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development