Past exam question: 2064 Jestha, Q3
Open in the Padhaiko appQuestion
Discuss the merits and demerits of contiguous list and linked list. Write algorithms to insert and delete a node after a node in a singly linked list.
Solution
Merits and Demerits of Contiguous (Array) List vs. Linked List:
| Structure | Merits | Demerits |
|---|---|---|
| Contiguous List (Array) | direct random indexing; zero extra pointer storage; high cache locality | Fixed size (MAX overflow or wasted memory); element shifting on insert/delete; needs contiguous memory block |
| Linked List | Dynamic runtime size; insertion/deletion once node is found; uses non-contiguous heap memory | sequential search/access; extra memory per node for pointer; lower cache locality |
Algorithms to Insert and Delete After a Node (targetKey) in Singly Linked List:
Algorithm INSERT_AFTER(head, targetKey, val):
1. curr = head
2. While curr != NULL and curr->data != targetKey:
curr = curr->next
3. If curr == NULL:
Print "Target node not found"; Return head
4. Allocate newNode; newNode->data = val
5. newNode->next = curr->next
6. curr->next = newNode
7. Return head
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 to delete after target"; Return head
4. del = curr->next
5. curr->next = del->next
6. Free(del)
7. Return headAnswer:
Contiguous lists excel at random access with zero pointer overhead but suffer fixed size and shifts; linked lists grow dynamically with pointer splicing after a node but require traversal and pointer storage.