PadhaikoAll subjects

Past exam question: 2078 Chaitra (Regular), Q3

Data Structure and Algorithms · 6 marks

Open in the Padhaiko app

Topic: Linked List

Question

Explain 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:

  1. Dynamic Sizing (No Fixed Overflow): A static list (fixed array) reserves a compile-time size MAX and overflows once full; a dynamic list (linked list) allocates nodes on demand from the heap until RAM is exhausted.
  2. No Memory Wastage: Static lists waste unused slots if MAX is overestimated; dynamic lists allocate exact memory per active item.
  3. 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.
  4. 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. Return

b) 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 deleted
Answer:

Dynamic 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.

All past exam questions for Data Structure and Algorithms