Chapter 8. Growable Arrays and Linked Lists: The Cost of Growth

Learning objectives

After this chapter you should be able to:

Do unaided:

Draw a growable array (buffer, size, capacity) and a singly linked list after a short sequence of pushes, inserts and deletes.
Compute the elements copied by n appends under growth by one and under doubling, and explain informally why doubling averages fewer than two copies per append.
Write a push that doubles capacity without leaking the old buffer, and list insertion, deletion and freeing that never lose the head or a node.
Compare array and list costs for appending, inserting at the front, indexing and traversal.
Read a log-log timing plot and tell a cost that grows like n² from one that grows like n.

May delegate:

Cost quizzes and insert-and-delete diagram drills from the tutor or drill maker, after you have written your own answer.

Opening case

A composite case, not a real student or course.

Sam has a two-week log from the field station: four sensors, one reading per minute, 80,640 readings. PA2 asks for a growable array of readings, and Sam has written one by hand. Before trusting it, Sam asks a chat agent for a push function to compare against. In the Tutor phase that is allowed: the agent's code is material to analyze, never code to submit.

The chapter continues from here.

The loop in this chapter

Open a step to see what it asks of you and how it plays out in the Tutor phase.

Predictcopy counts, growth counts and final capacity for 1,000 appends under +1 and doubling, and list drawings after three operations, each with a confidence.

Step 1 of 6 · You, no AI

What you hand in: A written prediction: the output, the memory state, the operation count, and how sure you are.

Why this step: A prediction written before the run is the only way to learn whether your model of the machine is right. A miss is the most useful result there is, because it shows exactly where the model is wrong.

The first prediction is never delegated.

Ask yourself: What will this print, what will memory look like when it ends, and how many operations will it take?

Log the prediction in your work log · Predict in every chapter · ← Predict in Chapter 7 · Predict in Chapter 9 →
Writervec_push with doubling and rlist_insert_after by hand, with ownership comments in the header.

Step 2 of 6 · You, no AI

What you hand in: One small piece written by hand, to build the mental model.

Why this step: You can only check what you could have built. Writing a small piece yourself gives you the model you will need to judge the agent's version later.

Ask yourself: Could I write this piece again tomorrow without notes?

Browse the companion code · Write in every chapter · ← Write in Chapter 7 · Write in Chapter 9 →
SpecifyPA2's tests, including head-removal edge cases and the 1,000,000-append scale test with its capacity-change limit, plus the questions for the tutor.

Step 3 of 6 · You

What you hand in: The header or class interface, unit tests, a complexity budget and the ownership rules.

Why this step: The specification is the contract the code will be held to. Tests written first, a cost budget and ownership rules turn "looks right" into something you can check.

Tutor In the Tutor phase you specify a question instead of code: what you want explained, quizzed or drilled.

The ownership and lifetime section of a specification is never delegated.

Ask yourself: Who allocates, who frees, what does it cost, and what input would break it?

Prompt and specification templates · Specify in every chapter · ← Specify in Chapter 7 · Specify in Chapter 9 →
Delegatea tutor quiz on cost and drill-maker sequences to diagram; no submitted code.

Step 4 of 6 · The agent

What you hand in: The implementation from your specification, or an explanation in the Tutor phase, with the prompts and transcript saved.

Why this step: The agent does the typing; you keep the judgment. Saving the prompts and the transcript makes the delegation something you can audit afterward.

Tutor Tutor phase: the agent explains, quizzes and makes practice problems. It writes no code you submit.

Ask yourself: Did I hand over my specification and tests, and did I save what the agent said?

Prompt templates · Delegate in every chapter · ← Delegate in Chapter 7 · Delegate in Chapter 9 →
Audittests, AddressSanitizer and Valgrind, the copy counter, and a timing table and log-log sketch checked against your derivation.

Step 5 of 6 · You and the tools

What you hand in: The Audit Report: tests, sanitizer and Valgrind output, your own cost derivation against a timing plot, the defects found, and a keep-or-rewrite decision.

Why this step: What the agent says is testimony until an instrument confirms it. Tests, sanitizers, Valgrind and a timing plot are evidence.

Tutor In the Tutor phase the audit checks the tutor's claims as well as your own code.

The final judgment that the code is correct is never delegated.

Ask yourself: What did the sanitizer report, does the timing plot match my derivation, and would I keep this code or rewrite it?

The Audit Report template · Audit in every chapter · ← Audit in Chapter 7 · Audit in Chapter 9 →
Defendthe growth policy, the line where the old buffer dies, the line where the head changes.

Step 6 of 6 · You, live

What you hand in: A five-minute oral defense.

Why this step: If you can explain it live, you own it. The oral checks that the understanding is yours and not the agent's.

Ask yourself: Why this bound, what input breaks it, and where is this memory freed?

How the loop works · Defend in every chapter · ← Defend in Chapter 7 · Defend in Chapter 9 →

What agents get wrong here

Patterns observed in agent-written code, to test for, not guarantees. If the agent no longer makes the mistake, your job is to prove it got it right, with the same instrument.

Growth by +1 or by a constant chunk, "because realloc grows in place"

How to catch it Count capacity changes over 10⁶ pushes; time under the sanitizer build

Section 8.3.1 · Timing and log-log plots

A grow step that never frees the old buffer

How to catch it ASan or Valgrind --leak-check=full; leaked-object count equals growth count

Section 8.3.2 · AddressSanitizer, LeakSanitizer, Valgrind

Losing the list head on delete (head passed by value)

How to catch it Tests removing first, only, last and missing nodes under ASan; draw both frames

Section 8.3.3 · AddressSanitizer, Tests, Your own trace

What the chapter covers

8.1 The concept, by hand
- 8.1.1 Size versus capacity
- 8.1.2 What one growth step costs
- 8.1.3 Counting copies: growth by one versus doubling
- 8.1.4 An informal amortized argument
- 8.1.5 Growth with realloc, and the leaked old buffer
- 8.1.6 Singly linked lists: nodes and insertion
- 8.1.7 Deletion, losing the head, and freeing a list
- 8.1.8 Comparing arrays and lists
- 8.1.9 Logarithms and the first log-log plot
8.2 Predict and check
8.3 What agents get wrong here
- 8.3.1 Growth by one (or by a constant)
- 8.3.2 Leaking the old buffer
- 8.3.3 Losing the list head on delete
8.4 Working with the agent
8.5 Lab: PA2, list and vector, under a timing test
8.6 Defend it

Cost thread

The count in this chapter is copies. You derived n(n − 1)/2 for +1 growth and fewer than 2n for doubling, confirmed both with a counter (Listing 8.8), and checked the counter against time with a log-log plot whose slopes came out near 2 and near 1. A count on paper, a count in the program and a timing slope that agree: that chain is the shape of every complexity section in an Audit Report from here on.

Summary

A growable array keeps size and capacity apart; appends into spare capacity are cheap, and the growth policy decides what the others cost.
Growth by one copies n(n − 1)/2 elements over n appends (499,500 for 1,000); doubling copies fewer than 2n (1,023). Growth by any constant is quadratic; growth by any factor above 1 is linear in total.
realloc may grow a block in place, but the standard does not promise it, and under AddressSanitizer every +1 push moved the block. Reason about the worst case, and count capacity changes, which no allocator can hide.
A grow step must end the old buffer's life exactly once; a leak count equal to your growth count points straight at it.
A list operation that can change the first node must change the caller's head, through struct node ** or a list struct. Test removing the first, only and last node under AddressSanitizer.
On a log-log plot a cost like nᵏ is a line of slope k; the measured slopes, about 2 and about 1, agreed with the counts.

Key terms

size: the number of elements a growable array currently holds.
capacity: the number of elements a growable array's buffer can hold before it must grow.
growable array: a struct holding a heap buffer, a size and a capacity, whose buffer is replaced by a larger one when full.
growth policy: the rule that sets the new capacity when a growable array is full, such as +1 or doubling.
doubling: a growth policy that multiplies capacity by two, giving fewer than 2n element copies over n appends.
amortized cost: a bound on the total cost of a sequence of operations divided by their number that holds for every sequence, not a promise about any one call.
node: a heap-allocated struct holding one list element and a pointer to the next node.
singly linked list: a chain of nodes, each pointing to the next, ending in a NULL pointer.
head: the pointer to a list's first node, or NULL for an empty list.
logarithm: the power to which a base (10 or 2) must be raised to give a number; it counts multiplications.
log-log plot: a plot of log time against log n, on which a cost growing like nᵏ is a line of slope k.

Companion code

3 files for this chapter, compiled with the book's flags.

Read the code Download ch08.zip

Connections

Where this chapter and another point to each other most often.

Chapter 6: The Stack and the Heap: Dynamic Memory and Ownership
And failure is reported by returning −1 with nothing changed, the PA2 convention from Chapter 6, because the caller decides what an out-of-memory logger should do.
Chapter 7: Structs, Headers, and Multi-File Programs
And doubling costs space: just after a growth, nearly half the buffer is spare, about 16 MB of empty slots in a buffer sized for a million readings (32 bytes each on the course container, as Chapter 7 measured).
Chapter 9: Files, Bits, and Function Pointers: ADTs Behind a Header
Both headers declare the structs without their fields, which live in the .c files; Chapter 9 explains this opaque-type technique in full.
Chapter 10: Complexity and Sorting: Your First Delegation
Chapter 10 makes slope reading part of every complexity claim. ## 8.2 Predict and check A formula you have not checked against a running program is still a conjecture. > Write your prediction before reading on.
Chapter 11: Specify First: Abstract Data Types
From Chapter 11: For the upload queue, with n readings held: rq_push is O(1) amortized and O(n) on the call that grows (doubling, Chapter 8); rq_pop, rq_size and rq_destroy are O(1); space is O(capacity), with capacity at most the larger of the initial capacity and twice the largest n ever held.
Chapter 12: Moving to C++: Is It Really C++?
From Chapter 12: Figure 12.2 shows the long case. ### 12.1.5 std::vector: an array that owns its memory std::vector<T> is Chapter 8's rvec, generalized and supplied by the library.
Chapter 14: Resource Ownership: RAII, the Rules of Zero, Three, and Five, and Smart Pointers
From Chapter 14: grow is a function template, which Chapter 16 explains; read grow<ThreeOnly> as "run this code with T replaced by ThreeOnly." 1,023 is 1 + 2 + 4 + ... + 512, the relocations as this library's vector doubled its capacity to 1,024 (Chapter 8).
Chapter 16: Templates and the Standard Library
Note also that rvec_get returns a borrowed pointer valid only until the next push, because a push may move the buffer and leave the pointer dangling (Chapter 16 meets this again as iterator invalidation).

See it on the map

08 Growable Arrays and Linked Lists: The Cost of Growth