programmingconcepts

§ 2.1 · Data structures

Arrays

Values stored side by side in memory, so any position can be reached directly by its index.

An array stores values side by side in one block of memory, numbered from 0. Because every slot is the same size, the computer can jump straight to any index in constant time, O(1). The trade-off is inserting or deleting in the middle: every value after that point has to shift over, which takes O(n).

Read a[i]
O(1)
Insert or delete
O(n)
Add at end
O(1) on average
Search
O(n), or O(log n) if sorted
Requires
Variables and types
def insert(a, length, index, value):
    # a has room for at least one more value after the first `length`
    for i in range(length, index, -1):
        a[i] = a[i - 1]
    a[index] = value
    return length + 1

The array holds 6 values and has room for one more. Insert 42 at index 2.

step 0 / 0shiftednew valuefree slot

Fig. 2.1. Inserting into the middle means shifting every later value one slot right, starting from the end. Orange marks the value being moved; the dashed slot is free space.

Intuition

Picture a row of numbered lockers. To open locker 500 you walk straight to it: you never open lockers 1 to 499 on the way. That’s an array. Because every slot is the same size and the slots sit side by side, the address of slot i is just start + i × slot size.

The catch is the same row. To fit a new item between lockers 2 and 3, everything from locker 3 on has to move down by one. (A linked list avoids the shifting, at the cost of fast indexing.)

How it works

  • Reading or writing a[i]: one calculation and one memory access, whatever the size. O(1) in Big O terms.
  • Inserting at index i: shift every value from the end down to i one place right, starting at the end so nothing is overwritten, then write the new value. O(n − i).
  • Deleting at index i: shift the later values one place left. O(n − i).
  • Growing: a fixed array can’t. Dynamic arrays (Python lists, JavaScript arrays, Java’s ArrayList, Go slices, Rust’s Vec) allocate a bigger block, usually about double, and copy everything over. Because that happens rarely, adding at the end costs O(1) on average.

Common mistakes

  1. Off-by-one indexes. The last value of an n-item array is at n - 1.
  2. Shifting from the wrong end. Shifting right must start at the end; starting at the insert point copies one value over all the others.
  3. Inserting at the front in a loop. Each insert is O(n), so n of them is O(n²). Append and reverse once, or use a deque (see stacks and queues).
  4. Treating list.insert or splice as free. They hide the same shifting loop.

In other languages

Language Fixed size Growable Insert in the middle
Python array.array (typed) list a.insert(i, x)
JavaScript Typed arrays Array a.splice(i, 0, x)
Java int[] ArrayList list.add(i, x)
C int a[n] Manual realloc Manual memmove
Go [n]int Slices slices.Insert(a, i, x)
Rust [i32; N] Vec v.insert(i, x)

Check yourself

Check yourself

Inserting at index 0 of an array holding 1,000 values moves how many values?

Check yourself

Reading a[500] from an array of 1,000 values takes…

Sources

  • Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, section 17.4, “Dynamic tables” (3rd edition).

Newsletter

One new concept each week, by email.

Signup opens soon.