Arrays: Static and Dynamic, and the Cost Model You Already Know

Hook #

You've been using arrays since your first program. [1, 2, 3] in Ruby. int arr[10] in C. They feel obvious — a row of values you can index into. But there are two distinct things hiding under the word "array," and Ruby (and Python, and Java's ArrayList, and Go's slice) all use the same word for one of them while running the other underneath. This lesson is about that gap — the difference between the static array the CPU actually understands and the dynamic array every modern language gives you. The cost model you proved in Course 1.2's amortized-analysis lesson is what bridges the two.

What you'll be able to do by the end of this lesson #

• State the difference between a static array (fixed size, contiguous memory) and a dynamic array (grows on demand).
• Predict the Big O of push, pop, shift, unshift, and random access on a Ruby Array — and explain why each is the cost it is.
• Recognize when an algorithm's cost is dominated by the array operations it performs, and when it isn't.
• Name what the "amortised O(1) append" guarantee actually costs you in worst-case memory.

Why this matters here #

This course is called "Linear Data Structures" because it's about the three sequence-shaped structures every program uses: arrays, linked lists, and the abstractions (stacks, queues, deques) built on top. Arrays are first because they're the substrate. Every other structure in Quarter 2 — heaps, BSTs, hash tables — is either backed by an array or compared to one for performance. If the array cost model isn't in your bones, the rest of the quarter's analyses don't land.

The reason we frame this lesson rather than re-teach it: CS61B's Josh Hug spends two lectures and a lab building an AList (their name for a dynamic array) from scratch, motivating the doubling resize, and proving the amortised cost. He does it better than we will. We frame because the canonical resource is canonical.

The engineer's lens #

Here's what CS61B doesn't say out loud, but is the load-bearing realisation: Array in Ruby and list in Python and ArrayList in Java are all the same data structure under three different names. They are dynamic arrays with doubling resize. The same Big O table applies. The same << is amortised O(1). The same unshift (or insert(0, x) in Python) is O(n) because the backing buffer has no slot to the left of index 0.

Once you see that, you stop memorising language-specific cost tables and start deriving them from the structure. Python's list.insert(0, x)? Has to shift every element right by one. O(n). Ruby's Array#unshift? Same shape, same cost. Go's slice prepend with append(slice, x) followed by copy? Still O(n) — the prepend cost is in the language because the data structure doesn't allow cheap prepends.

The other half of the lens: the static array hasn't gone away. C is still the language underneath your Ruby program, and inside the MRI source code, the Ruby Array is a C struct containing a pointer to a malloc'd region of memory of fixed size — a static array. When Ruby "grows" your Array, it allocates a new, larger static array, copies the old contents over, and frees the old buffer. The dynamic array is a managed wrapper around a sequence of static arrays. You proved this cost model in Course 1.2 lesson 5; this lesson is where you watch it run in two languages.

What to focus on in CS61B #

CS61B Spring 2026 covers this material across two lectures and one project. The 4-hour total is well spent. Specifically:

• Lecture "Lists 3: DLLists, Arrays" through to "ALists, Resizing" — these are the canonical teaching. Hug builds an AList from a static array, hits the resize problem, derives doubling. Watch through.
• Project 1B (Deque) — you'll implement an ArrayDeque later in this course; CS61B's version is in Java and worth at least reading the spec, even if you don't do the project in Java.
• What to skip if time is short — Hug's discussion of Java generics. Generics are a Java concern; the cost model doesn't care about types.
• What to come back to later — Hug compares his ALinkedListDeque and ArrayDeque implementations. That comparison is exactly the ADT vs. implementation split we'll teach in lesson 3, so don't worry if it feels abstract on first watch.

Explain it back to me #

A teammate writes Ruby code that builds a list by repeatedly using unshift (prepend) in a loop, then complains it's slow on large inputs. In your own words, explain why it's slow — using the words "buffer," "shift," and "no slot to the left." Then propose a fix that uses the data structure's strengths (hint: build in the natural direction, then reverse).

And one more: why does Array#pop take O(1) but Array#shift take O(n)? Answer in one sentence; the answer should not be "because the standard library is implemented that way."

What to come back with #

After CS61B's lectures, return here with a quick prediction:

If you have a Ruby Array of n items and you call each of these operations once, write down your prediction for the Big O. Don't look anything up.

rubyarr[i]          # random read at index i
arr[i] = x      # random write at index i
arr << x        # append (push)
arr.pop         # remove from end
arr.shift       # remove from start
arr.unshift(x)  # prepend
arr.insert(k, x)  # insert at arbitrary index k
arr.delete_at(k)  # delete at arbitrary index k

Save your predictions. The next exercise lesson opens with the answer key, and the project after that (zc-ruby-array-internals) has you implement the operations from scratch — at which point you'll feel the costs in your fingertips.

Where this connects #

Backward: Course 1.2 lesson 5 (Amortized Analysis) proved the O(1) amortised cost of push from the geometric-series sum of resize costs. This lesson is where that proof becomes muscle memory. Course 1.3 (Systems Programming) gave you the memory model — pointer + length is the static array's full shape; the dynamic array is one more level of indirection.

Forward: Lesson 2 (Linked Lists) gives you the structure that does allow O(1) prepend, at the cost of losing O(1) random access. Lesson 3 (ADTs) generalises the trade-off. Course 2.3 (Hashing) uses the same doubling trick to resize hash tables when load factor exceeds threshold. And the first project in this course, zc-ruby-array-internals, has you implement a dynamic array backed by a fixed buffer — making everything in this lesson concrete.