Inserting, deleting, and growing

Big idea

An array has no gaps, so changing anything in the middle means shifting everything after it — O(n). The end is different: appending and popping there touch one slot, and a dynamic array that doubles when full keeps appends at O(1) amortized.

Inserting in the middle

Insert 9 at index 1 of [4, 1, 7, 3]:

before:  [4, 1, 7, 3, _]
shift:   [4, 1, 1, 7, 3]   ← move 3, then 7, then 1 one slot right (back to front)
write:   [4, 9, 1, 7, 3]

Shifting starts from the back so nothing is overwritten before it's moved. For an insert at index i in an array of n items, that's n − i moves: up to n at the front, 0 at the end.

def insert_at(arr, i, value):
    arr.append(None)                 # make room at the end
    for j in range(len(arr) - 1, i, -1):
        arr[j] = arr[j - 1]          # shift right, back to front
    arr[i] = value

Watch it

Deleting from the middle

Deleting is the mirror image: shift everything after the gap one slot left, front to back, then shrink.

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

Python's list.insert(i, x) and list.pop(i) do exactly this — so they're O(n), even though they're one line. pop() with no argument removes the last item: O(1).

Growing: the dynamic array

A plain array has a fixed size. Python lists, Java ArrayList, and C++ vector are dynamic arrays: an array with spare capacity, plus a count of how many slots are used.

• Append with spare room: write into the next slot — O(1).
• Append when full: allocate a block twice the size, copy everything, then write — O(n), but rare.

Across n appends, the copies add up to less than 2n, so each append is O(1) amortized. The amortized analysis lesson walks through the arithmetic.

Choosing where to put things

If your algorithm keeps inserting at the front, an array is the wrong tool:

Often the cleanest fix is to build the result backwards and reverse once — n appends plus one O(n) reverse, instead of n front-inserts costing O(n²).

Practice

• Insert Delete GetRandom O(1) — the swap-with-last trick plus a hash map.
• Pascal's Triangle — build each row by appending from the previous one.

Quick check