Skip to main content

Insertion and deletion in array list

Short answer

Insert: check overflow, shift elements from K to N right, place ITEM at K, increment N. Delete: remove element at K, shift subsequent elements left, decrement N. Example: inserting 25 at position 3 shifts 30,40,50 right, resulting in 10,20,25,30,40,50.

Write algorithms of insertion and deletion of data in array implementation of lists.

In array implementation a list LA of N elements is stored in LA[1..N] (position 1 is the first). The array has capacity MAX.

Insertion of ITEM at position K

INSERT(LA, N, K, ITEM)
1. if N == MAX:  print "Overflow"; exit
2. if K < 1 or K > N + 1:  print "Invalid position"; exit
3. for J = N down to K:          /* shift right to make room */
       LA[J + 1] = LA[J]
4. LA[K] = ITEM
5. N = N + 1

Deletion of the element at position K

DELETE(LA, N, K)
1. if N == 0:  print "Underflow"; exit
2. if K < 1 or K > N:  print "Invalid position"; exit
3. ITEM = LA[K]
4. for J = K to N - 1:           /* shift left to fill the gap */
       LA[J] = LA[J + 1]
5. N = N - 1
6. return ITEM

Example

LA = 10 20 30 40 50, N = 5.

  • Insert 25 at K = 3: elements 30, 40, 50 move one place right → 10 20 25 30 40 50, N = 6.
  • Delete K = 2: element 20 is removed and 25, 30, 40, 50 move left → 10 25 30 40 50, N = 5.

Time: O(N) in the worst case for both (insert/delete at the start); O(1) at the end.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Data Structure and Algorithm chapter 3 questions →