PadhaikoAll subjects

Past exam question: 2074 Bhadra (Regular), Q4

Data Structure and Algorithms · 6 marks

Open in the Padhaiko app

Topic: Linked List

Question

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 + 1

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

All past exam questions for Data Structure and Algorithms