PadhaikoAll subjects

Past exam question: 2064 Jestha, Q3

Data Structure and Algorithms · 8 marks

Open in the Padhaiko app

Topic: Linked List

Question

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:

StructureMeritsDemerits
Contiguous List (Array) direct random indexing; zero extra pointer storage; high cache localityFixed size (MAX overflow or wasted memory); element shifting on insert/delete; needs contiguous memory block
Linked ListDynamic 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 head
Answer:

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.

All past exam questions for Data Structure and Algorithms