sdlc.dev

Data structures and algorithms path · Cost and memory · Topic 2 of 13

Arrays and dynamic arrays

Not started

An array stores its elements in one contiguous block of memory, so the address of element i is simply the start address plus i times the element size. That makes indexing O(1) and scanning very fast, because the processor reads memory in cache lines and prefetches the next ones. The catch is that a block has a fixed size. Dynamic arrays (a JavaScript Array, a Python list, a Java ArrayList, a C++ std::vector) hide that by over-allocating and moving to a bigger block when they run out of room.

Why it matters: The array is the default data structure in every language for good reason; knowing its costs tells you when push is free and when unshift is a disaster.

  1. 1Contiguous memory

    Elements sit side by side, so element i is at start + i × size. Reading any index is O(1), and scanning is cache-friendly.

  2. 2Fixed capacity underneath

    A dynamic array (JS Array, Python list, Java ArrayList) keeps a block with spare room and tracks how much of it is used.

  3. 3Grow by a factor

    When full it allocates a bigger block, copies everything, and frees the old one. Growing by a multiple keeps the average cost of push O(1).

  4. 4The front is expensive

    Inserting or removing at the start shifts every element, which is O(n) per operation.

1

How it works

The explanation, with examples you can run.

Amortised growth

A dynamic array keeps two numbers: its length (elements in use) and its capacity (slots allocated). push writes into the next free slot, which is O(1). When length reaches capacity, it allocates a larger block, copies every element across, and frees the old one, which is O(n) for that one push. The trick is to grow by a factor, not a fixed amount:

⌘/Ctrl + Enter
OutputNot run yet

Press Run to see what your code prints, in order.

Runs in this browser, in an isolated frame with no access to this page. console.log, info, warn and error are shown; code runs as a classic script, so use an async function for await.

A million pushes cause 1,048,575 element copies in total, about one per push. The expensive pushes happen at sizes 1, 2, 4, 8 … and their costs add up to less than twice the final size. That is what amortised O(1) means: any one push may be slow, but n pushes cost O(n) altogether.

Real implementations choose different factors to trade memory for copying. CPython's list grows by roughly one eighth plus a little, about 1.125x; Java's ArrayList documentation promises only that adding an element "has constant amortized time cost". Any factor above 1 gives the same Big-O. If you know the final size, pre-size the array (new Array(n) then fill it, ArrayList(capacity), [None] * n) to skip the copies entirely.

The cost of the front

Inserting at index 0 means moving every existing element one slot to the right. Removing from the front means moving them all left. Each is O(n), so doing it n times is O(n²):

⌘/Ctrl + Enter
OutputNot run yet

Press Run to see what your code prints, in order.

Runs in this browser, in an isolated frame with no access to this page. console.log, info, warn and error are shown; code runs as a classic script, so use an async function for await.

In Node 22 on a laptop this took about 2 ms for the pushes and between 650 and 950 ms for the unshifts, depending on the run. Inserting in the middle (splice) has the same cost. When you need cheap operations at both ends, use a ring buffer: a fixed block with a head and tail index that wrap around, which is how Python's collections.deque and Java's ArrayDeque avoid shifting.

Why arrays usually win

Even for operations where another structure has a better Big-O, arrays often win in practice: no per-element allocation, no pointers to follow, and the hardware is built to stream through consecutive memory. Reach for something else when you need cheap insertion in the middle, cheap removal at the front, or lookups by key rather than by position.

2

Check yourself

3 questions. Get them all right to finish this topic.

  1. 1.A dynamic array doubles its capacity when it is full. What is the total copying cost of n pushes, starting empty?
  2. 2.What if the array grew by a fixed 10 slots each time instead of doubling?
  3. 3.Why is `arr.unshift(x)` on a large array much slower than `arr.push(x)`?

0 of 3 right so far. Get all three to finish this topic.

Go deeper