Past exam question: 2078 Chaitra (Regular), Q3
Open in the Padhaiko appExplain the significance of dynamic list data structures over static list. Write algorithms to implement list structure using array for the operations: a) Insert at given position in the list b) Delete from given position in the list
Solution
Significance of Dynamic List over Static List:
- Dynamic Sizing (No Fixed Overflow): A static list (fixed array) reserves a compile-time size
MAXand overflows once full; a dynamic list (linked list) allocates nodes on demand from the heap until RAM is exhausted. - No Memory Wastage: Static lists waste unused slots if
MAXis overestimated; dynamic lists allocate exact memory per active item. - Efficient Insertion/Deletion: Static lists must shift up to contiguous elements ( data movement) on insert/delete; linked lists only update pointers in once the target position is located.
- Non-Contiguous Memory: Dynamic lists can utilize scattered free memory blocks rather than requiring one large contiguous block.
a) Algorithm to Insert at a Given Position in an Array List: Assume 0-based indexing on array L[0..MAX-1] with current length size:
Algorithm INSERT_AT(L, size, pos, val):
1. If size == MAX:
Print "List Overflow"
Return
2. If pos < 0 or pos > size:
Print "Invalid Position"
Return
3. For i = size - 1 down to pos:
L[i + 1] = L[i]
4. L[pos] = val
5. size = size + 1
6. Returnb) Algorithm to Delete from a Given Position in an Array List:
Algorithm DELETE_AT(L, size, pos):
1. If size == 0:
Print "List Underflow"
Return
2. If pos < 0 or pos >= size:
Print "Invalid Position"
Return
3. deleted = L[pos]
4. For i = pos to size - 2:
L[i] = L[i + 1]
5. size = size - 1
6. Return deletedDynamic lists eliminate fixed-capacity overflow, memory wastage, contiguous-block requirements, and element shifting. For array-based lists, INSERT_AT shifts L[pos..size-1] one slot right before writing L[pos], and DELETE_AT shifts L[pos+1..size-1] one slot left after saving L[pos], both taking worst-case time.