Past exam question: 2074 Bhadra (Regular), Q4
Open in the Padhaiko appQuestion
Write algorithms of insertion and deletion of data in array implementation of lists.
Solution
Insertion Algorithm in Array List (0-Indexed A[0..MAX-1]):
Algorithm LIST_INSERT(A, 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:
A[i + 1] = A[i]
4. A[pos] = val
5. size = size + 1Deletion Algorithm in Array List:
Algorithm LIST_DELETE(A, size, pos):
1. If size == 0:
Print "List Underflow"
Return -1
2. If pos < 0 or pos >= size:
Print "Invalid Position"
Return -1
3. removed = A[pos]
4. For i = pos to size - 2:
A[i] = A[i + 1]
5. size = size - 1
6. Return removed
Both operations take worst-case time due to shifting.
Answer:
In an array list, LIST_INSERT shifts A[pos..size-1] right by one slot before placing val, and LIST_DELETE saves A[pos] and shifts A[pos+1..size-1] left by one slot, both in worst-case time.