A. Programming Concepts and Skills · Algorithm Design and Analysis

Subprograms to Insert and Delete Array Elements

A3.3 C2.1 C2.2About 70 minutes

Learning goals

I can write subprograms that insert and delete elements in a fixed-capacity array, shifting elements in the correct direction.
I can state the preconditions and postconditions of insert and delete, including full and empty arrays.
I can insert into a sorted array by finding the position with binary search, and explain why it is still O(n).
I can predict the cost of Python list operations such as append, insert, pop and remove.

Words to know

capacity
The number of slots an array has room for.

size (logical length)
The number of slots actually in use; elements are kept in indexes 0 to size − 1.

shift
Moving each element in a section of the array one place left or right to open or close a gap.

partially filled array
An array whose capacity is larger than its size, with a separate variable that tracks the size.

amortized O(1)
Cheap on average over many operations, even if an occasional one is expensive (like Python's append when the list must grow).

A waitlist with a fixed number of seats

A hockey camp's waitlist has room for 8 names. When someone with priority signs up, they go into position 1, and everyone after them moves down one place. When someone drops out, everyone behind them moves up. The list never has gaps, and it never has more than 8 names.

That is exactly how insertion and deletion work in an array with a fixed capacity, the kind of array in languages like Java and C. Python lists hide this work (they grow and shift for you), but it still happens, and it still costs time. In this lesson you will write the subprograms yourself (A3.3) and analyse what they cost.

Remember from Grade 11

In Algorithms to Specification: Inserting and Deleting in a Sorted Array (ICS3U) you slid a new value into a sorted Python list and closed the gap after a deletion. Now you will write general, reusable subprograms with precise contracts, for an array that cannot grow, and compare their cost with Python's built-in list methods.

The partially filled array

Many languages create arrays with a fixed length. To use one as a list that grows and shrinks, programmers keep two things:

the array data (its length is the capacity), and
an integer size: how many slots are in use. Elements live in data[0] to data[size - 1]; the rest is spare room.

We can model this in Python with data = [None] * 8 and size = 0.

def insert_at(data, size, index, value):

"""Insert value at position index, shifting later elements right.

Precondition: 0 <= index <= size < len(data) (there is room).

Postcondition: data[index] == value; the elements that were in

data[index..size-1] are now in data[index+1..size];

returns the new size, size + 1.

"""

assert 0 <= index <= size < len(data), "bad index or array full"

for i in range(size, index, -1): # right to left!

data[i] = data[i - 1]

data[index] = value

return size + 1

def delete_at(data, size, index):

"""Remove the element at index, shifting later elements left.

Precondition: 0 <= index < size.

Postcondition: the elements that were in data[index+1..size-1] are

now in data[index..size-2]; returns the new size, size - 1.

"""

assert 0 <= index < size, "bad index"

for i in range(index, size - 1): # left to right

data[i] = data[i + 1]

data[size - 1] = None # tidy the unused slot

return size - 1

data = [None] * 8

size = 0

for name in ["Ana", "Ben", "Cai", "Dev"]:

size = insert_at(data, size, size, name) # insert at the end

print(data[:size])

size = insert_at(data, size, 1, "Zoe")

print(data[:size], size)

size = delete_at(data, size, 1)

print(data[:size], size)

print(data)

Output, one line each: ['Ana', 'Ben', 'Cai', 'Dev'], ['Ana', 'Zoe', 'Ben', 'Cai', 'Dev'] 5, ['Ana', 'Ben', 'Cai', 'Dev'] 4, ['Ana', 'Ben', 'Cai', 'Dev', None, None, None, None]. Inserting at index size (the end) shifts nothing. The last line shows the whole array, including unused capacity.

Inserting at index 1. The loop runs from the right end towards the gap, so no value is overwritten before it has been copied.

Why the direction of the loop matters

Insert must shift right to left. If you went left to right, data[2] = data[1] would overwrite Cai with Ben before Cai had been copied, and Ben would be smeared across the rest of the array.

Delete must shift left to right: copy data[index + 1] into data[index] first, then the next one, and so on.

A quick check for any shifting loop: the first assignment must write into a slot whose old value you no longer need (an empty slot when inserting; the deleted slot when deleting).

Cost of insert and delete

Count element moves (shifts) in an array of size n:

insert_at at index i moves n − i elements: 0 at the end, n at the front.
delete_at at index i moves n − i − 1 elements: 0 for the last element, n − 1 for the first.
If every position is equally likely, about n ÷ 2 moves on average.

So both are O(n) in the worst and average case, and O(1) at the end of the array. This is why a stack (add and remove at the end only) is so cheap, and why inserting at the front of a large list is slow.

Two ways to delete. A keeps the order and shifts every later element left (O(n)). B moves the last element into the hole (O(1)), which is fine when the order does not matter, such as a bag of raffle tickets.

Worked example

Insert into a sorted array, faster search

A sorted array of ski-race times must stay sorted when a new time arrives. Write insert_sorted(data, size, value) that uses binary search to find the position, then insert_at to put it there. What is its Big-O?

Find the position: a binary search for the insertion point: the first index whose element is greater than value (so equal times keep their arrival order). When low > high, low is that index.
def insertion_point(data, size, value): low, high = 0, size - 1 while low <= high: mid = (low + high) // 2 if data[mid] <= value: low = mid + 1 else: high = mid - 1 return low `def insert_sorted(data, size, value): return insert_at(data, size, insertion_point(data, size, value), value)`
Precondition: data[0..size − 1] is sorted ascending and size < len(data). Postcondition: data[0..size] contains the old elements plus value, still sorted; returns size + 1.
Cost: finding the position is O(log n), but shifting is O(n). The total is O(log n + n) = O(n). Binary search cuts the comparisons to about log₂ n, but not the moves.
The ICS3U version compared and shifted in one loop from the right end: about the same number of moves, and up to n comparisons. Both are O(n) overall.

insert_sorted costs O(log n) comparisons plus O(n) moves: O(n) overall. The bottleneck is the shifting, not the searching.

def insert_at(data, size, index, value):

for i in range(size, index, -1):

data[i] = data[i - 1]

data[index] = value

return size + 1

def insertion_point(data, size, value):

low, high = 0, size - 1

while low <= high:

mid = (low + high) // 2

if data[mid] <= value:

low = mid + 1

else:

high = mid - 1

return low

def insert_sorted(data, size, value):

return insert_at(data, size, insertion_point(data, size, value), value)

times = [None] * 10

size = 0

for t in [58.2, 55.9, 61.0, 55.9, 57.4]:

size = insert_sorted(times, size, t)

print(times[:size])

Output, one line each: [58.2], [55.9, 58.2], [55.9, 58.2, 61.0], [55.9, 55.9, 58.2, 61.0], [55.9, 55.9, 57.4, 58.2, 61.0]. Each new time lands in sorted position. The second 55.9 goes after the first one because the search moves right on <=.

What about Python lists?

A Python list is a partially filled array managed for you: it keeps spare capacity and grows automatically. The costs follow the same rules:

Operation	What it does	Cost
a.append(x)	add at the end	O(1) amortized (occasionally the list is copied into a bigger array)
a.pop()	remove the last element	O(1)
a.insert(i, x)	insert at index i	O(n − i): O(n) at the front
a.pop(i)	remove at index i	O(n − i): O(n) at the front
a.remove(x)	find x, then delete it	O(n): a linear search plus a shift
del a[i]	delete at index i	O(n − i)
a[i] = x	replace an element	O(1)

"Amortized" means averaged over many appends: most are O(1), and the rare expensive growth is spread across them.

import time

for n in [20_000, 40_000, 80_000]:

a = []

start = time.perf_counter()

for k in range(n):

a.insert(0, k) # insert at the front: shifts everything

front = time.perf_counter() - start

b = []

start = time.perf_counter()

for k in range(n):

b.append(k) # add at the end: no shifting

end = time.perf_counter() - start

print(n, round(front * 1000, 1), "ms vs", round(end * 1000, 1), "ms")

Your times will differ. On one computer: 20 000 took 37.3 ms vs 1.1 ms, 40 000 took 147.9 ms vs 1.7 ms, and 80 000 took 685.0 ms vs 3.9 ms. Doubling n roughly quadruples the front-insert time (n inserts × O(n) each = O(n²)) but only doubles the append time (O(n) in total).

Choosing the right end

If your program adds and removes at the front a lot (a queue of customers, for example), a plain list is O(n) per operation. Python's collections.deque is built for adding and removing at both ends in O(1). Knowing the cost of each operation is part of designing an efficient algorithm, not just a detail.

Just for fun

Why did the array go to physiotherapy?

It had been shifting everything one place to the right all week, and its back was out of order. (The front was fine, though: inserting at the end never hurts.)

Hands-on activity

Egg-carton array

You need: an empty egg carton (12 cups, so capacity 12), 10 small numbered slips of paper or coins with numbers written on sticky notes, a pencil, and a computer with Python.

Line the cups up as indexes 0 to 11 (write the numbers on the lid). Put 7 numbered slips in cups 0 to 6 in increasing order. Write size = 7 on a sticky note.
Insert a new number so the carton stays sorted. Move slips one at a time, starting from the right end. Count the moves. Update the size note.
Delete the slip in cup 2, keeping the order. Count the moves. Update size.
Now try deleting the "swap with last" way (strategy B). How many moves?
Try to insert when size = 12. What should the program do? Add the check to your Python insert_at (it is already an assert in the lesson) and make it print a friendly message instead of crashing.
In Python, add a counter of moves to insert_at and delete_at, and check your carton counts match.

What to look for: inserting at index i in an array of size n takes n − i moves; deleting at index i takes n − i − 1. Shifting from the wrong end will "smear" one slip across several cups.

Your turn

An array has size 9. How many elements move when you insert at index 2? When you delete at index 2?

Why does insert_at loop for i in range(size, index, -1) (right to left)?

What are the preconditions of insert_at? Give one call that breaks each part.

Why is inserting into a sorted array O(n) even with binary search?

Which Python list operations are O(1)? append, insert(0, x), pop(), pop(0), a[5] = 7

When is "swap with the last element" a correct way to delete?

More practice: warm-up

What is the difference between capacity and size?

In a partially filled array of size 5, which indexes hold elements?

What does insert_at return?

Inserting at index size moves how many elements?

Big-O of deleting the first element of an array of n elements, keeping order?

More practice: on your own

Show the array after each step: start [4, 9, 12, None, None] with size 3; insert_at(..., 1, 7); then delete_at(..., 0).

Find the bug:

def insert_at(data, size, index, value):

for i in range(index, size):

data[i + 1] = data[i]

data[index] = value

return size + 1

Write delete_value(data, size, value) that deletes the first copy of value (if any) and returns the new size. Use your earlier subprograms.

Predict the output:

a = [10, 20, 30, 40, 50]

a.insert(2, 25)

a.pop(0)

a.remove(40)

print(a, len(a))

A program does 100 000 pop(0) calls on a list that starts with 100 000 elements. Roughly how many element moves in total? What would be better?

Challenge

Write delete_all(data, size, value) that removes every copy of value in a single left-to-right pass (O(n), not O(n²)), keeping the order. Return the new size.

Python lists grow by allocating a bigger array and copying when they are full. Suppose capacity doubles each time (1, 2, 4, 8, …). Show that n appends cause fewer than 2n element copies in total, so append is O(1) amortized.

A sorted array is used for a leaderboard: 1 000 000 scores, 1000 new scores per second, and 10 lookups per second. Is a sorted array a good choice? Estimate the work per second and suggest an alternative idea.

Check your understanding

Quiz

In which direction must insert_at shift elements?

An array has size 10. How many moves does deleting index 3 take (keeping the order)?

What is the Big-O of inserting into a sorted array of n elements when binary search finds the position?

Which precondition must insert_at check in a fixed-capacity array?

Which Python list operation is O(1)?

Deleting by moving the last element into the hole is:

For parents and teachers

Big idea: A3.3 asks students to create subprograms that insert and delete array elements. Writing them for a fixed-capacity array (as in Java or C) shows the shifting that Python lists hide. Contracts (C2.1) and cost analysis (C2.2) are practised throughout.

How to help: The egg-carton activity is very effective: let your teen be "the computer" and narrate each move. Ask, "What happens if the carton is full?" and "Which end should you start from?"

Common difficulties:

Shifting in the wrong direction, which copies one value over and over.
Forgetting to update or return the size, so the caller's size is out of date.
Off-by-one errors in the loop bounds (range(size, index, -1) stops at index + 1, which is the last slot to fill by copying).
Believing binary search makes sorted insertion O(log n): the moves still cost O(n).