Past exam question: 2063 Baishakh (Regular / Back), Q6
Open in the Padhaiko appQuestion
What is doubly linked list and what are its features? Write the algorithms to delete a particular node in singly linked list.
Solution
Doubly Linked List and Its Features: A doubly linked list (DLL) is a linear linked structure where every node contains three fields: (prev, data, next). Features:
- Supports bidirectional traversal (both head-to-tail and tail-to-head).
- Allows deletion of a given node pointer without searching for its predecessor.
- Simplifies insertion before a known node, at the cost of storing one extra
prevpointer per node.
Algorithm to Delete a Particular Node (by Key val) in Singly Linked List:
Algorithm DELETE_KEY(head, val):
1. If head == NULL:
Print "List is empty"; Return NULL
2. If head->data == val:
temp = head
head = head->next
Free(temp)
Return head
3. prev = head, curr = head->next
4. While curr != NULL and curr->data != val:
prev = curr
curr = curr->next
5. If curr == NULL:
Print "Node not found"; Return head
6. prev->next = curr->next
7. Free(curr)
8. Return headAnswer:
A doubly linked list links nodes with both prev and next pointers for two-way traversal and known-node deletion. Deleting a key in a singly linked list handles head->data == val directly and otherwise unlinks curr via prev->next = curr->next; Free(curr).