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 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) \)

Hint:

In a singly-linked list, we must traverse the list to delete a node, resulting in a time complexity of \( O(n) \), while in a doubly-linked list, node deletion can be done in constant time \( O(1) \).

Answer 1

The Correct Option is D

To determine the worst-case time complexity of the functions SLLdel and DLLdel, let's analyze the operations involved in deleting a node from a singly-linked list (SLL) and a doubly-linked list (DLL).

Singly-Linked List Deletion (SLLdel):

A singly-linked list node contains a pointer to the next node. To delete a node from an SLL, we need to update the previous node's next pointer to skip the node to be deleted. However, without backward pointers, we must first traverse the list to find the node preceding the node we want to delete. This traversal requires up to \( n-1 \) steps in the worst case.

Therefore, the time complexity of SLLdel in the worst case is \( O(n) \).

Doubly-Linked List Deletion (DLLdel):

A doubly-linked list node contains pointers to both the next and previous nodes. When deleting a node from a DLL, we can access both the previous and next nodes directly, thanks to the backward pointers. Consequently, we can update the pointers of the neighboring nodes in constant time without any need for traversal.

Thus, the time complexity of DLLdel in the worst case is \( O(1) \).

After considering these operations, we conclude that the correct statement is: SLLdel is \( O(n) \) and DLLdel is \( O(1) \).

SLLdel is \( O(n) \) and DLLdel is \( O(1) \).