PadhaikoAll subjects

Past exam question: 2063 Baishakh (Regular / Back), Q6

Data Structure and Algorithms · 8 marks

Open in the Padhaiko app

Topic: Linked List

Question

What is doubly linked list and what are its features? Write the algorithms to delete a particular node in singly linked list.

Solution

Doubly Linked List and Its Features: A doubly linked list (DLL) is a linear linked structure where every node contains three fields: (prev, data, next). Features:

  1. Supports bidirectional traversal (both head-to-tail and tail-to-head).
  2. Allows deletion of a given node pointer without searching for its predecessor.
  3. Simplifies insertion before a known node, at the cost of storing one extra prev pointer per node.

Algorithm to Delete a Particular Node (by Key val) in Singly Linked List:

Algorithm DELETE_KEY(head, val):
1. If head == NULL:
       Print "List is empty"; Return NULL
2. If head->data == val:
       temp = head
       head = head->next
       Free(temp)
       Return head
3. prev = head, curr = head->next
4. While curr != NULL and curr->data != val:
       prev = curr
       curr = curr->next
5. If curr == NULL:
       Print "Node not found"; Return head
6. prev->next = curr->next
7. Free(curr)
8. Return head
Answer:

A doubly linked list links nodes with both prev and next pointers for two-way traversal and known-node deletion. Deleting a key in a singly linked list handles head->data == val directly and otherwise unlinks curr via prev->next = curr->next; Free(curr).

All past exam questions for Data Structure and Algorithms