Arrays

Prerequisites

• Variables and memory addresses: every byte has a number.
• A for loop that counts down as well as up.
• Big-O notation.

The analogy

How it works

Start with a sequence of operations by hand

The array has capacity 5 and holds [3, 8, 5]. Do each operation and guess its cost before opening "Check".

Finish the picture: a growing array

A dynamic array (like C++ vector or Python list) starts with capacity 2 and doubles when full. Append 1, 2, 3.

• Appends 1 and 2. Predict: does anything get copied?
  Check

  No. Both fit in the 2 free slots: one write each.

• Append 3. Predict what happens, since the array is full.
  Check

  A new block of capacity 4 is allocated, 1 and 2 are copied over, then 3 is written. That one append cost 3 writes.

The rule in plain words

To read or write index i, compute its address and go there directly.

To insert at i, shift everything from i onwards one slot right, then write. To delete at i, shift everything after it one slot left.

The code

Read this code after you have done the operations by hand. It will make more sense.

int insert_at(int a[], int n, int idx, int v) {   /* returns the new size */
    for (int i = n; i > idx; i--)
        a[i] = a[i - 1];                           /* shift right, from the end */
    a[idx] = v;
    return n + 1;
}

int delete_at(int a[], int n, int idx) {          /* returns the new size */
    for (int i = idx; i < n - 1; i++)
        a[i] = a[i + 1];                           /* shift left */
    return n - 1;
}

flowchart TD
  A["insert v at index i"] --> B{"Is the array full?"}
  B -->|yes| C["Allocate double capacity, copy all elements"]
  B -->|no| D["Shift a[i..n-1] one slot right"]
  C --> D
  D --> E["a[i] = v, n = n + 1"]
          

How fast is it?

Reading is fast because the address is one formula. With base address $b$ and element size $s$ bytes:

For 4-byte ints starting at address 1000, a[3] lives at $1000 + 3 \cdot 4 = 1012$. No loop is needed, whatever $i$ is.

Common mistakes

• Shifting right starting from index i instead of from the end, which copies the same value over everything.
• Forgetting to update the size after inserting or deleting.
• Growing a dynamic array by +1 each time instead of doubling, which makes $n$ appends cost $O(n^2)$.

Try it yourself

Did you know?

Key points to remember

If you remember one thing from each line, remember the because.

• Access is $O(1)$ because the address of a[i] is computed as $b + i \cdot s$.
• Insert and delete in the middle are $O(n)$ because every later element has to shift by one slot.
• Appending is amortized $O(1)$ because doubling makes the rare big copies add up to less than $2n$.
• Shifting right must start from the end because otherwise you overwrite elements before moving them.
• Arrays are cache-friendly because their elements sit next to each other in memory.

Self-check questions

Answer these in order, out loud. They follow the page, so your answers become the script of your video.

1. How is an array like a row of numbered lockers?
   Sample answer

   You can walk straight to any locker number, but putting something new in the middle means moving everything after it one locker along.

2. Walk through inserting 7 at index 1 in [3, 8, 5].
   Sample answer

   Move 5 from slot 2 to 3, then 8 from slot 1 to 2, then write 7 into slot 1: [3, 7, 8, 5].

3. Why does the insert loop run from n down to idx + 1?

   A good answer says what would be overwritten otherwise.

   Sample answer

   Moving from the end puts each element into a slot that is already free. Going upwards would overwrite a[idx+1] with a[idx] before a[idx+1] had moved.

4. So what is an array, in one sentence?
   Sample answer

   A contiguous block of same-sized elements where element $i$ is found directly by computing its address.

5. Why is reading a[i] $O(1)$ whatever $i$ is?

   A good answer gives the address formula.

   Sample answer

   The address is base + i × element size, a single calculation, so no other element has to be visited.

6. What do read, search, append, insert and delete cost?
   Sample answer

   Read/write $O(1)$, search $O(n)$, append amortized $O(1)$, insert and delete in the middle $O(n)$ because of shifting.

7. Why is appending to a dynamic array still $O(1)$ on average when resizing copies everything?
   Sample answer

   Because capacity doubles, copies happen rarely and add up to less than $2n$ over $n$ appends, so each append costs a constant on average.

8. If you had to teach this to a friend in 2 minutes, what would you leave out, and why?
   Sample answer

   I'd leave out the cache details and the amortized proof. I'd keep the locker analogy, the insert-with-shifting example, and "$O(1)$ access, $O(n)$ insert in the middle".

External resources

• GeeksforGeeks: Introduction to arrays: basics, memory layout and operations.
• Wikipedia: Array (data structure): addressing formulas and multidimensional arrays.
• Wikipedia: Dynamic array: growth factors and amortized analysis.

Videos

• YouTube search: dynamic array amortized analysis: why append is $O(1)$ on average.