Data structures: defend an invariant and an operation cost
A data structure promises observable behavior and a cost under stated operations. This route separates the interface, representation invariant and cost model, using dynamic arrays to show why one slow operation can coexist with a cheap sequence. Choose one spine and use the others for a specific explanation or implementation gap.
Study route and exercise: University Reading List editorial project. How we curate · Sources checked:
On this page
Scope and responsibility
For a second computing course after loops, functions, arrays and references. Morin adds mathematical analysis; Goodrich requires willingness to read Java classes and generics; Wengrow offers a gentler counting approach. All numbers below describe invented algorithms, not timings or guarantees for a language’s built-in list.
Choose your starting point
I want a free rigorous spine
Use Morin’s author-hosted Java or pseudocode edition after reviewing sums, logarithms and elementary probability. Read one implementation beside its bound.
My course implements structures in Java
Use Goodrich for abstract data types, classes and API contracts. Compare its pedagogical interfaces with the actual interface your assignment requires.
I can code but Big O feels detached
Use Wengrow’s counting and diagrams, then ask Morin for the argument behind an amortized claim. Avoid treating one illustrative operation as a proof for every sequence.
Compare the three books
Open Data Structures: An Introduction
Pat Morin · 2013
Free analysis spine
- Choose it when
- You can read loops and follow a sum, and want a representation-to-bound explanation.
- Use another route when
- You still need a first programming course or cannot distinguish an index from a stored value.
- Selected reading
- Author-hosted Java/pseudocode: Array-Based Lists, then Linked Lists and selected Hash Tables. The 2013 print contents place these at 2, 3 and 5.
- Limits and trade-offs
- The online text/code carry the author’s Attribution terms; AU Press’s PDF has a different noncommercial/no-derivatives notice. Select the format actually used rather than assuming one licence covers everything.
Try before choosing
For a growing array, state n≤capacity and count every copied element in twelve appends.
Check your work: Explain both why indexed access remains valid and why a resize changes a single operation’s cost.
Data Structures and Algorithms in Java
Michael T. Goodrich; Roberto Tamassia; Michael H. Goldwasser · Edition: 6 · 2014
Java implementation spine
- Choose it when
- You need to design classes, state preconditions and implement an abstract data type.
- Use another route when
- You want a language-neutral shortcut without learning references, exceptions or generics.
- Selected reading
- Sixth edition, 2014 paperback ISBN 9781118771334: select array/list, stack/queue and algorithm-analysis discussions by title.
- Limits and trade-offs
- Its student code and exercises complement the commercial book; a companion site is not free access to all textbook content. The later e-book has a different identifier.
Try before choosing
Describe a queue API, then trace enqueue/dequeue with an empty-state rule and a circular array representation.
Check your work: The observable FIFO order and internal wraparound are separate; distinguish a full buffer from an empty one without losing an element.
A Common-Sense Guide to Data Structures and Algorithms: Level Up Your Core Programming Skills
Jay Wengrow · Edition: 2 · 2020
Intuitive operations companion
- Choose it when
- You know basic coding and need concrete counts before mathematical notation.
- Use another route when
- You need its diagrams alone to justify every worst-case or probabilistic bound.
- Selected reading
- Second edition, 2020 ISBN 9781680507225: Why Data Structures Matter, Big O, stacks/queues, and Node-Based Data Structures.
- Limits and trade-offs
- Examples use JavaScript, Python and Ruby; do not silently equate their library costs with a hand-built model. The publisher provides extracts and code, while the full book remains commercial.
Try before choosing
Compare removing the first array element with following a stored linked-list head reference.
Check your work: Count shifts separately from link changes, and include the cost of locating a node when no reference is given.
Check your preparation
What is an invariant?
A property that holds before and after each permitted operation, such as 0≤n≤capacity and valid elements occupying indices 0…n−1. It is not the operation’s running time.
What does amortized mean?
A bound on the total cost of a sequence, divided across its operations. It does not assert that every operation is fast or that inputs are random.
What is counted here?
One write for each appended or relocated element. Allocation, reads, deallocation, zero-initialization and clearing a deleted slot are excluded. A different cost model needs a different numerical total.
A six-step study plan
Steps completed: 0 / 6
These are your own study marks, not an assessment. They are not sent to this site.
-
Specify the interface
Selected reading: Your spine’s list or queue introduction.
What to do: Write permitted operations, empty/full behavior and what a caller can observe.
Check your work: An interface says what happens; it does not commit to an array or linked representation.
-
Draw the representation
Selected reading: Morin Array-Based Lists or Goodrich’s corresponding discussion.
What to do: Draw n, capacity, occupied slots and the next insertion index before and after a resize.
Check your work: Every old element occurs once, in order, and the new item follows it.
-
Count a complete sequence
Selected reading: Wengrow’s operation counts, then Morin’s resizing argument.
What to do: Make a twelve-row append ledger with capacity, copy count and total writes.
Check your work: Report a resize’s worst single cost and the whole sequence’s cost separately.
-
Change the growth rule
Selected reading: The same array discussion.
What to do: Replace doubling with capacity+2 and rebuild the ledger.
Check your work: Explain why an arithmetic sum of increasing copy counts changes the sequence bound.
-
Test deletion hysteresis
Selected reading: Selected array resizing discussion and the original follow-up.
What to do: Trace four append/pop pairs under two exact shrink thresholds.
Check your work: A gap between grow and shrink thresholds prevents the demonstrated oscillation; it does not make copying disappear.
-
Defend a choice
Selected reading: Selected list and queue chapters.
What to do: Write a short recommendation for an indexed-access workload and a front-removal workload, including known references and costs.
Check your work: State workload, invariant, costs and excluded overheads; a structure’s name alone is not a justification.
Worked exercise
Original append ledger: cheap on average still permits a spike
An initially empty array has capacity 2. Append twelve items, doubling only when an append finds it full. Count element writes and final capacity. Compare an alternative that grows capacity by 2 instead.
Assumptions
Items occupy 0…n−1. Growth copies exactly n existing items, then writes the new item once. Initial capacity is free in this ledger. Allocation, reads, zeroing and deletion clearing are not counted; no items are removed.
- Doubling grows on appends 3, 5 and 9, copying 2, 4 and 8 elements. Copies total 14, plus twelve new-item writes gives 26 writes. Final size is 12 and capacity 16.
- Append 9 alone costs 8 relocations plus one new write, or 9 writes. The sequence average is 26/12=13/6 writes, so an average does not bound every individual operation by that number.
- Growing by 2 copies 2+4+6+8+10=30 elements; adding twelve insertions gives 42 writes, size/capacity 12/12. A smaller final unused space has cost more relocation.
- For doubling to n items, copied capacities form a geometric sum; for fixed increments they form an arithmetic sum. These support linear versus quadratic total relocation growth under this model, not measured wall-clock rankings.
Answer and interpretation
Doubling: 26 writes and capacity 16; fixed increment: 42 writes and capacity 12. Doubling’s ninth append is still a 9-write spike.
Test the result
List every growth event. During the 8→16 copy, old and new arrays temporarily hold 24 allocated slots; peak allocation differs from final spare capacity.
Change an assumption
Changed threshold: shrinking can undo amortization
Start instead at size 8, capacity 8; construction is uncounted. Perform four pairs: append one item, then pop it. Grow on full by doubling. Rule H shrinks capacity by half after a pop when n≤capacity/2; rule Q instead uses n≤capacity/4. Minimum capacity is 2. Count only append writes and relocation writes.
- Under H, each append grows 8→16 and copies 8; its pop leaves n=8 and immediately shrinks 16→8, copying 8. Four pairs copy 4×16=64 items plus four append writes, totaling 68.
- Under Q, only the first append grows and copies 8. Each pop leaves 8 items in capacity 16, above the inclusive quarter threshold 4, so none shrinks. Total writes are 8+4=12.
- Both finish with size 8, but H ends capacity 8 and Q capacity 16. Q trades retained space for avoiding this resize oscillation; no deletion-slot clearing is counted.
Answer and interpretation
H costs 68 writes; Q costs 12 for the same eight operations. Their different invariants allow different retained capacities.
Test the result
Trace size/capacity after each of the eight operations. Do not add an initial eight-item construction cost or a deleted-slot clearing cost excluded by the packet.
Common mistakes
Confusing worst and amortized
One expensive append refutes a per-operation constant bound, not a constant amortized bound.
Forgetting location cost
A linked-list link update can be constant once the required node is known; finding that node is another operation.
Hiding a cost-model change
Allocator work, memory retention and cache behavior matter in real programs but are not supplied measurements here.
Before moving on
- I can state the representation invariant and restore it after an operation.
- I can reproduce both append ledgers and threshold traces.
- I can justify a structure for a named workload without equating a mathematical cost with elapsed time.
Sources and edition checks
Sources checked:
- Morin: free online editions, source code and licence
The author-hosted free editions support implementation and proof together; the route assumes basic programming and mathematical notation.
- AU Press: selected 2013 print identity and contents
The 2013 print identity and verified contents are distinguished from evolving online editions and their different permission notices.
- Wiley: Java sixth edition and product formats
The selected sixth-edition paperback and Java/API emphasis define the implementation comparison.
- Pragmatic Bookshelf: second-edition contents and practice
The second-edition contents and code languages support an intuitive counting route. The numerical ledgers here are original.
These are proposed study activities, not official course assignments or a claim that every book has been read cover to cover.