PadhaikoAll subjects

Past exam question: 2062 Baishakh (Regular / Back), Q1

Data Structure and Algorithms · 8 marks

Open in the Padhaiko app

Topic: Linked List

Question

Write an algorithm to delete a node before a node in singly and doubly linked list.

Solution

1. Delete Node Before a Given Target (targetKey) in Singly Linked List:

Algorithm SLL_DELETE_BEFORE(head, targetKey):
1. If head == NULL or head->next == NULL or head->data == targetKey:
       Print "No node exists before target"; Return head
2. If head->next->data == targetKey:     // target is 2nd node -> delete head
       temp = head; head = head->next
       Free(temp); Return head
3. prev2 = head, prev1 = head->next, curr = prev1->next
4. While curr != NULL and curr->data != targetKey:
       prev2 = prev1; prev1 = curr; curr = curr->next
5. If curr == NULL:
       Print "Target not found"; Return head
6. prev2->next = curr
7. Free(prev1)
8. Return head

2. Delete Node Before a Given Target (targetKey) in Doubly Linked List:

Algorithm DLL_DELETE_BEFORE(head, targetKey):
1. curr = head
2. While curr != NULL and curr->data != targetKey:
       curr = curr->next
3. If curr == NULL or curr->prev == NULL:
       Print "No node exists before target"; Return head
4. del = curr->prev
5. If del == head:                       // node to delete is head
       head = curr
       curr->prev = NULL
   Else:
       del->prev->next = curr
       curr->prev = del->prev
6. Free(del)
7. Return head
Answer:

In a singly linked list, deleting the node before targetKey tracks two trailing pointers (prev2, prev1) and splices prev2->next = curr; in a doubly linked list, curr->prev directly identifies del so del->prev->next = curr and curr->prev = del->prev (updating head if del == head).

All past exam questions for Data Structure and Algorithms