PadhaikoAll subjects

Past exam question: 2078 Baishakh (Back), Q9

Data Structure and Algorithms · 6 marks

Open in the Padhaiko app

Topic: Linked List

Question

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:

  1. Bidirectional Traversal: Can traverse both forward (next) and backward (prev).
  2. Deletion Given a Node Pointer: A node can be deleted directly using node->prev and node->next without scanning from head to locate its predecessor.
  3. Easy Insertion Before a Given Node: Inserting before any known node p requires 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 head
Answer:

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.

All past exam questions for Data Structure and Algorithms