Past exam question: 2065 Shrawan (Regular / Back), Q3
Open in the Padhaiko appQuestion
What are linked list? Write an algorithm for inserting a node before a node and deleting a node after a node in singly linked list.
Solution
Linked List Definition: A linked list is a dynamic linear collection of nodes where each node stores a data field and a pointer next holding the address of the successor node (terminated by NULL), allocated dynamically on demand from the heap.
Algorithm to Insert Before a Given Node (targetKey):
Algorithm INSERT_BEFORE(head, targetKey, val):
1. Allocate newNode; newNode->data = val
2. If head == NULL: Free(newNode); Return NULL
3. If head->data == targetKey:
newNode->next = head; Return newNode
4. prev = NULL, curr = head
5. While curr != NULL and curr->data != targetKey:
prev = curr; curr = curr->next
6. If curr == NULL: Free(newNode); Return head
7. prev->next = newNode; newNode->next = curr
8. Return headAlgorithm to Delete a Node After a Given Node (targetKey):
Algorithm DELETE_AFTER(head, targetKey):
1. curr = head
2. While curr != NULL and curr->data != targetKey:
curr = curr->next
3. If curr == NULL or curr->next == NULL:
Print "No node exists after target"
Return head
4. del = curr->next
5. curr->next = del->next
6. Free(del)
7. Return headAnswer:
A linked list connects dynamically allocated nodes via pointers. INSERT_BEFORE tracks prev while searching for targetKey and splices before curr; DELETE_AFTER locates targetKey, sets curr->next = curr->next->next, and frees the bypassed node.