PadhaikoAll subjects

Past exam question: 2065 Shrawan (Regular / Back), Q3

Data Structure and Algorithms · 8 marks

Open in the Padhaiko app

Topic: Linked List

Question

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 head

Algorithm 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 head
Answer:

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.

All past exam questions for Data Structure and Algorithms