Insert, Delete, and the Cost Table

The price of the middle

Contiguity gives arrays O(1) indexing, but it also creates their weakness: there are no gaps. To insert into the middle, every item to the right must slide one slot over to make room. To delete from the middle, everything slides back to close the hole.

Insert or delete at index i touches all n − i items after it:

• at the end: 0 shifts, O(1) (this is why append and pop() are cheap)
• at the front: n shifts, O(n) (this is insert(0, x) and pop(0))
• in the middle: about n⁄2 shifts, still O(n)

Watch the shifting happen:

Watching the shifts

insert_at makes room by sliding items right, counting each slide as it goes.

def insert_at(arr, i, value):
    arr.append(None)
    shifts = 0
    j = len(arr) - 1
    while j > i:
        arr[j] = arr[j - 1]
        shifts += 1
        j -= 1
    arr[i] = value
    return shifts

arr = list(range(10))
print("insert at front, shifts:", insert_at(arr, 0, 99))
print(arr)

arr = list(range(10))
print("insert at end, shifts:", insert_at(arr, 10, 99))
print(arr)

Output

insert at front, shifts: 10
[99, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
insert at end, shifts: 0
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 99]

The arr.append(None) opens one slot at the end, then the loop walks backwards from that slot, copying each item one position right until it reaches i.

Inserting at the front shifted all 10 items, and inserting at the end shifted none. The value inserted was identical, and so was the amount of data in the list. Only the position changed.

That is the shape of the cost: shifts equal the number of items to the right of the insertion point, so the cost runs from 0 at the end to n at the front.

Deleting closes the hole

Deletion is the same motion in reverse. Items after the gap slide left to fill it.

def delete_at(arr, i):
    shifts = 0
    for j in range(i, len(arr) - 1):
        arr[j] = arr[j + 1]
        shifts += 1
    arr.pop()
    return shifts

arr = list(range(8))
print("delete front, shifts:", delete_at(arr, 0))
print(arr)

arr = list(range(8))
print("delete last, shifts:", delete_at(arr, 7))
print(arr)

Output

delete front, shifts: 7
[1, 2, 3, 4, 5, 6, 7]
delete last, shifts: 0
[0, 1, 2, 3, 4, 5, 6]

The loop copies arr[j + 1] into arr[j] for each position from i onward, which walks the gap toward the end of the list. After it finishes, the last two slots hold the same value, so arr.pop() drops the leftover duplicate.

Deleting the front shifted 7 of the 8 items. Deleting the last item entered the loop zero times, costing 0 shifts, which is O(1).

Both halves of this lesson point at one conclusion. An array's end is cheap to modify and its front is expensive, and the reason is the same contiguity that made indexing free.

The array cost table

Memorize this. It is the baseline every other structure gets compared against.

Binary search from lesson 1-3 belongs to arrays for a reason: jumping to the middle of the range needs O(1) indexing. Sorted data in a structure with slow indexing loses the trick, as you will see with linked lists in unit 4.

Repeatedly calling tasks.pop(0) is O(n) per pop, which makes the whole loop O(n²).

Each pop(0) closes the hole at the front by shifting every remaining item one slot left, exactly like the delete_at(arr, 0) above. With 100,000 tasks that is around 100,000 pops each shifting around 100,000 items, roughly 10¹⁰ operations.

The trap is that the code looks innocent. There is one loop and one method call, and nothing on the page suggests quadratic work, which is why recognizing pop(0) on a large list is a habit worth building.

Unit 5 introduces the deque, a structure built specifically so that removal from the front is O(1), turning this exact loop from 10¹⁰ operations into 100,000.