Past exam question: 2078 Baishakh (Back), Q9
Open in the Padhaiko appQuestion
What are the advantages of doubly linked list over singly linked list? Write an algorithm to insert a node before a given node in a singly linked list.
Solution
Advantages of Doubly Linked List over Singly Linked List:
- Bidirectional Traversal: Can traverse both forward (
next) and backward (prev). - Deletion Given a Node Pointer: A node can be deleted directly using
node->prevandnode->nextwithout scanning fromheadto locate its predecessor. - Easy Insertion Before a Given Node: Inserting before any known node
prequires no predecessor search.
Algorithm INSERT_BEFORE(head, targetKey, newVal) in Singly Linked List:
Algorithm INSERT_BEFORE(head, targetKey, newVal):
1. Allocate newNode; newNode->data = newVal
2. If head == NULL:
Print "List is empty"
Return head
3. If head->data == targetKey:
newNode->next = head
head = newNode
Return head
4. prev = NULL, curr = head
5. While curr != NULL and curr->data != targetKey:
prev = curr
curr = curr->next
6. If curr == NULL:
Print "Target node not found"
Free(newNode)
Return head
7. prev->next = newNode
8. newNode->next = curr
9. Return headAnswer:
Doubly linked lists allow two-way traversal, deletion of a given node, and direct insertion before a node. In a singly linked list, INSERT_BEFORE maintains a trailing pointer prev while scanning from head (handling head insertion separately) and splices prev->next = newNode; newNode->next = curr in time.