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?
SLLdel is O(1) and DLLdel is O(n)
Both SLLdel and DLLdel are O(log(n))
Both SLLdel and DLLdel are O(1)
SLLdel is O(n) and DLLdel is O(1)
Given two functions SLLdel for singly linked list and DLLdel for doubly linked list.
In a singly linked list, nodes have only reference to the next node, not to the previous one. So, we have to traverse to the previous node of the target node to keep the list linked after deletion. In the worst-case scenario, we have to traverse to the (n-1) nodes, so the time complexity of deleting an element from the Singly Linked List is O(n).
In a doubly linked list, nodes have references to the both next and previous nodes. So we can delete the given node in constant time in any case. So the time complexity of deleting an element from the Doubly Linked List is O(1).
