---
title: "Array List"
description: "Contiguous storage with O(1) indexing — append, insert, delete, and the shift cost."
source: https://vizlearn.app/algorithms/data-structures/array-list
---

# Array List

An **array list** (or dynamic array) stores its elements in one contiguous block and tracks two numbers: the `size` it holds and the `capacity` it could hold. Because elements sit back-to-back, reaching any index is one calculation — `address + index × element_size` — so reads and writes by position are O(1). That contiguity is paid for on inserts, deletes, and growth.

Think of it as a row of numbered boxes with a few spare boxes parked on the right. Appending drops a value into the first spare box. When the spare boxes run out, the list does something drastic but rare: it rents a row twice as long, carries every value across, and throws the old row away. That one expensive move is what lets a fixed-size array pretend to be infinitely stretchy.

## How an Array List Works

The backing array never shrinks to fit. It holds `capacity` slots, of which the first `size` are live and the rest are spare. Four ideas cover everything the structure does:

- **Index access** (`get`, `set`) walks to no neighbors. The slot's address is computed directly from the index, so the cost is the same whether you ask for index 0 or index 9,000.
- **Append** writes into slot `size` and bumps `size` by one — as long as a spare slot exists. The check `size == capacity` guards every append.
- **Grow** happens only when that check is true. The list allocates a new array of `2 × capacity`, copies all `size` elements into it one by one, frees the old array, and only then performs the append. Copying is O(n), but because the capacity doubles, grows get geometrically rarer — so across many appends the average cost stays O(1). That averaging-out is called *amortized* O(1).
- **Shift** is the cost of keeping the elements contiguous with no gaps. Inserting at index `i` moves every element from `i` onward one slot to the right to open a hole; removing at `i` moves everything after it one slot left to close the hole. Both touch `size − i` elements, so they are O(n) — worst at the front, free at the very end.

One subtlety the animation makes literal: a shift must run in the right direction or it clobbers data. Inserting copies **right to left** (move the last element into the fresh slot first, then back-fill), so no value is overwritten before it has been moved. Removing copies **left to right** for the same reason.

## Array List Step by Step

The default run starts with an empty list whose backing array has `capacity = 4`, then plays nine operations. Watch `size` and `capacity` in the header.

1. `append(5)` — slot 0 is spare, so 5 is written at index 0. `size` becomes 1.
2. `append(8)` — written at index 1. `size` becomes 2.
3. `append(2)` — written at index 2. `size` becomes 3.
4. `append(9)` — written at index 3. `size` becomes 4. The array is now **full**: `size == capacity == 4`.
5. `append(4)` — the capacity check fires, so the list grows before it can write. It allocates a new array of capacity 8, then copies the four live values across one at a time — `5`, then `8`, then `2`, then `9` — so you can count the four copies that make this one append O(n). The old array is freed, and only now is `4` written at index 4. The list is `[5, 8, 2, 9, 4]`, `size = 5`, `capacity = 8`.
6. `get(2)` — no scanning. The probe lands straight on index 2 and reads `2`. One hop, O(1).
7. `set(2, 6)` — the same direct hop, but writing. Index 2 changes from `2` to `6`. The list is `[5, 8, 6, 9, 4]`.
8. `insert(1, 7)` — index 1 is occupied, so a gap must be opened. The elements at indices 1 through 4 slide right by one, processed last-first: `4` moves to index 5, `9` to index 4, `6` to index 3, `8` to index 2. That leaves index 1 empty, and `7` drops into it. The list is `[5, 7, 8, 6, 9, 4]`, `size = 6`. Four elements moved to insert one — the shift cost in plain sight.
9. `remove(3)` — the value at index 3 is `6`. It lifts out, and the gap is closed by sliding the elements after it left: `9` moves from index 4 to index 3, then `4` from index 5 to index 4. `size` drops to 5 and the freed tail slot becomes spare again. The final list is `[5, 7, 8, 9, 4]`.

By the end the array holds five values inside a capacity-8 backing store — three spare slots waiting for the next cheap appends. On the canvas, the dashed boxes on the right are exactly that spare capacity, and the bracket under the solid boxes tracks `size`; the gap between them is the whole idea of a dynamic array.

## Time and Space Complexity

| Operation | Time | Why |
|---|---|---|
| `get(i)` / `set(i, v)` | O(1) | Address is computed from the index — no traversal. |
| `append(v)` | O(1) amortized, O(n) on a grow | Usually one write; occasionally a full copy into a 2× array. |
| `insert(i, v)` | O(n) | Shifts the `size − i` elements at and after `i` to the right. |
| `remove(i)` | O(n) | Shifts the `size − i − 1` elements after `i` to the left. |

Space is O(n), but the backing array is deliberately larger than `size`: right after a grow it is twice as big, so up to half of the allocated slots can be spare. That slack is what buys the amortized-O(1) append.

The animation doubles the capacity on every grow. Real implementations use the same idea with different growth factors — Java's `ArrayList` grows by 1.5×, C++'s `std::vector` typically by 1.5× to 2×, CPython's `list` by roughly 1.125× — but any constant factor greater than 1 keeps appends amortized O(1).

## Edge Cases

- **Insert or remove at the end.** `insert(size, v)` opens no gap, so it is just an append. `remove(size − 1)` shifts nothing — it only drops `size`. These are the O(1) corners of two O(n) operations.
- **Insert or remove at the front.** `insert(0, v)` shifts *every* live element, and `remove(0)` every remaining one. This is the worst case, and the reason a [linked list](https://vizlearn.app/algorithms/data-structures/linked-lists) exists: its prepend is O(1).
- **Out-of-range index.** `get`, `set`, and `remove` require `0 ≤ i < size`; `insert` allows `0 ≤ i ≤ size` (you may insert right after the last element). Anything else raises an `IndexError`; the Inputs panel disables the buttons for such an index, so the animation never runs one.
- **Operating on an empty list.** `get`, `set`, and `remove` on `size == 0` have no valid index, so they raise. `insert(0, v)` on an empty list is valid and just appends.
- **The view's capacity cap.** The visualization stops doubling at capacity 16 so the row stays legible. A real array list has no such ceiling — it keeps doubling for as long as memory allows.

## Common Mistakes

- **Thinking append is always O(1).** Most appends are, but the one that triggers a grow copies the entire array. The O(1) is *amortized* — averaged over many appends — not a guarantee for any single one.
- **Shifting in the wrong direction.** Inserting by copying left to right overwrites the next element before it has been moved, smearing one value across the tail. Insert must walk from the high index down; remove must walk from `i` up.
- **Forgetting the elements stay contiguous.** An array list has no holes. Removing index `i` does not leave a `null` at `i` — everything after `i` slides down to fill it, which is exactly why removal is O(n).
- **Confusing `size` with `capacity`.** `size` is how many values you stored; `capacity` is how many the backing array could hold. Indexing past `size − 1` is an error even when there are spare slots sitting right there.
- **Expecting an array list to beat a linked list at everything.** It wins decisively on indexed access and cache-friendly scanning, but loses on front insertion and deletion. Pick by which operations dominate your workload.