Think Data Structures: Algorithms and Information Retrieval in Java

Think Data Structures connects the Java Collections Framework with implementation, performance analysis, and a working information-retrieval project. This guide follows Allen B. Downey's version 1.1.0 through all seventeen chapters. Readers should already be comfortable with Java classes and methods; the book develops interfaces, lists, maps, trees, hashing, persistence, crawling, Boolean search, and sorting. Its software and service examples belong to the source edition. The lasting task is to justify a structure's behavior and cost under a specified workload, then test those expectations through controlled measurements and a clearly defined application.

Chapter-by-chapter summaries

Chapter 1: Interfaces

The distinction between an interface and an implementation explains why ArrayList and LinkedList can satisfy the same List contract while behaving differently internally. A caller can depend on promised operations without choosing a storage strategy at every use. The opening exercise establishes the source repository, build process, and automated tests that support the later implementations. Using a structure correctly comes before replacing its internals. This top-down perspective keeps the application visible while introducing abstraction, and it makes clear that passing interface-level tests is a functional requirement rather than evidence of good asymptotic performance.

Study task. Use two implementations through one List reference and identify which behavior is guaranteed by the interface rather than by either class.

Chapter 2: Analysis of Algorithms

Selection sort provides a small example for counting operations and classifying growth with Big O notation. The goal is to predict how cost changes with input size under a stated computational model. Constants and lower-order terms can matter in practice even when they disappear from an asymptotic classification. A result also depends on what counts as the input and which operation is being measured. The chapter connects a concrete loop structure with a mathematical growth claim, preparing readers to compare implementations before profiling. Analysis should explain a mechanism, not simply attach a memorized complexity label to a method name.

Study task. Count the comparisons in selection sort on several sizes and connect the pattern with a derived growth expression.

Chapter 3: ArrayList

An array-backed list supports efficient indexed access, but insertion and removal can require shifting existing elements. Growing the backing storage introduces occasional expensive operations whose cost should be distinguished from ordinary appends and amortized behavior. Downey analyzes methods of MyArrayList and emphasizes that problem size must be defined consistently. The chapter also introduces linked structures as an alternative representation. A good performance claim identifies both an operation and its position in the collection; adding at the front and at the end are different workloads. Functional correctness remains a separate requirement from those cost predictions.

Study task. Classify each list operation, then trace the elements moved by front insertion, middle removal, and an append that triggers resizing.

Chapter 4: LinkedList

A singly linked representation stores values in nodes joined by references. Accessing an indexed position requires traversal, and a change that is cheap once a node is known may still be expensive when finding that node is part of the operation. Comparing linked and array-backed lists therefore requires a precise workload. Profiling introduces empirical measurement and interpretation, including the need to distinguish startup effects from sustained growth. The chapter develops a useful discipline: predict a performance curve from the implementation, gather measurements across increasing sizes, and investigate discrepancies rather than accepting the fastest-looking isolated timing.

Study task. Trace a linked-list removal and profile one operation at several input sizes, explaining which part of the implementation determines its growth.

Chapter 5: Doubly-linked list

Additional links and endpoint references can change which list operations are efficient. A doubly linked list makes backward traversal and some endpoint updates possible, at the cost of extra storage and more relationships to maintain during mutation. The chapter revisits profiling results to explain why apparently similar methods can have different behavior. Choosing a structure means matching its strengths to the application's actual access and modification patterns. An interface alone does not promise a particular complexity. Correct mutation must preserve the connection between neighboring nodes as well as the head, tail, size, and empty-list cases.

Study task. Draw before-and-after node diagrams for insertion and removal at both ends, then choose a list representation for a stated workload.

Chapter 6: Tree traversal

HTML is represented as a document tree, giving traversal an immediate application in a search engine. Parsing with jsoup creates objects whose parent-child relationships can be explored through recursive or iterative depth-first search. An explicit stack can replace the call stack while preserving the intended traversal order. A tree's structure should be distinguished from the sequence in which nodes are visited. The chapter connects abstract data structures with real documents, while also exposing the assumptions involved in finding useful links or text among navigation, markup, and other page elements.

Study task. Traverse a small document both recursively and with an explicit stack, recording the visit order and explaining any difference.

Chapter 7: Getting to Philosophy

A Wikipedia-link exercise turns traversal into a small crawler and introduces iterables, iterators, and a fetcher abstraction. The next useful link is a rule to implement, not simply the first anchor anywhere in an HTML file. Pages can change, repeat, fail to load, or form cycles, so the experiment needs explicit stopping conditions. An iterator separates access to a sequence from the code consuming it. Treat external pages as variable input and cached examples as reproducible test fixtures. The educational goal is to connect document structure, control flow, and responsible retrieval with a clearly stated graph-walking task.

Study task. Test the link-selection rule on saved documents containing navigation links, repeated pages, and a cycle before using live requests.

Chapter 8: Indexer

An index reverses the direct document view: a term leads to the pages containing it rather than a page leading to its words. TermCounter records frequencies within a page, and the larger index connects those local counts across documents. Data-structure selection follows the operations the application needs, including recording, looking up, and combining term information. Tokenization choices determine which strings count as the same term, so case handling and punctuation are part of the model. The chapter makes the representation pipeline visible and prepares the reader to reason about both indexing cost and search behavior.

Study task. Build an index for a few controlled documents and explain how tokenization changes the results for a chosen query.

Chapter 9: The Map interface

A map associates keys with values under operations such as put, get, and removal. A simple linear implementation exposes the cost of searching entries and the need to distinguish replacing a key's value from adding a new key. Equality conventions and absent-key behavior belong to the contract. The implementation provides a baseline against which later improvements can be measured. It also illustrates why a correct interface implementation can be unsuitable for a large workload: repeated linear searches may dominate an otherwise simple application. Keep the number of entries separate from the size of the values stored in them.

Study task. Test replacement, missing keys, and removal in a small linear map, then derive the cost of repeated lookups as the map grows.

Chapter 10: Hashing

Hashing uses a key-derived value to choose a smaller region in which to search. Collisions are expected and must be handled rather than treated as evidence that hashing failed. A useful hash distribution spreads entries well for the actual keys, while equality still determines whether keys represent the same map entry. Mutating a key in a way that changes its hash can undermine lookup assumptions. The chapter develops a better map from these ideas and connects representation with expected performance. Hashing does not establish constant time for every input, nor does it remove the need to analyze collision behavior.

Study task. Create colliding keys deliberately, verify correct lookup despite collisions, and explain what goes wrong when a stored key's hash-relevant state changes.

Chapter 11: HashMap

A scalable hash map must manage the relationship between its number of entries and its bucket capacity. Resizing and redistribution can keep typical searches short while introducing occasional expensive updates. Downey analyzes and profiles MyHashMap, then uses unexpected measurements to investigate implementation choices. The trade-offs include space, average operation cost, and assumptions about key distribution. A UML class view helps clarify how related implementations share behavior. This chapter reinforces the distinction between an expected or amortized cost and a worst-case guarantee, and between an algorithmic prediction and the behavior of a particular implementation.

Study task. Profile map growth across a resize and explain both the temporary timing increase and the longer-run trend.

Chapter 12: TreeMap

Ordered keys motivate a binary search tree as an alternative to hashing. The ordering invariant directs a lookup into one subtree at each step, but efficiency depends on the height of the resulting tree. A balanced shape can support logarithmic paths; a poorly shaped tree can reduce the same interface to nearly linear traversal. The chapter connects comparisons, key order, and recursive implementation. It also explains why an ordered map offers operations and iteration behavior that a hash map does not naturally provide. Choosing between them requires the application's ordering needs as well as its expected update and lookup workload.

Study task. Insert the same keys in several orders, draw the resulting trees, and compare the lookup path lengths.

Chapter 13: Binary search tree

The tree-map implementation develops insertion, searching for values, and in-order traversal. Searching by key can use the ordering invariant, whereas searching by an arbitrary value generally cannot discard a subtree on the same basis. In-order traversal turns the structural invariant into an ordered output sequence. Profiling and adversarial insertion orders expose the limitations of an unbalanced design. Self-balancing trees address that limitation by maintaining additional structure during updates. The chapter links the proof of an invariant with the actual path taken by an algorithm and shows why an interface-level promise of ordering is not itself a performance guarantee.

Study task. Compare key search with value search and construct an insertion order that makes an ordinary binary search tree degenerate.

Chapter 14: Persistence

An in-memory index disappears when the process ends; persistence makes the data available across runs. Redis introduces a client-server boundary and a different collection of available data types. A persistent index needs a deliberate key scheme so terms, URLs, and counts can be reconstructed without ambiguity. The chapter asks readers to adapt earlier abstractions rather than merely replace one constructor. Serialization, network calls, and external service state introduce costs and failure modes absent from the simplest local model. Use a controlled development instance and treat the source's service-specific setup as historical implementation guidance.

Study task. Persist a small index, restart the client, and recover equivalent query results while documenting the key and value representation.

Chapter 15: Crawling Wikipedia

The persistent indexer is combined with graph traversal to discover and process multiple pages. A queue or other frontier structure organizes work that remains, while a visited record prevents uncontrolled repetition. Lookup and indexing costs depend on both the chosen structures and the amount of text being processed. The chapter revisits the relationship between an abstract operation and the underlying work it triggers, including network access and database commands. A crawler also needs limits, caching, and respectful retrieval behavior. The resulting application provides a concrete setting in which correctness, performance, and external-system assumptions interact.

Study task. Crawl a bounded set of saved pages first, recording frontier size, visited URLs, indexed terms, and the stopping rule.

Chapter 16: Boolean search

An information-retrieval query combines sets of matching documents and then orders or scores the candidates according to a defined rule. Intersection, union, and difference express different meanings for multi-term searches. Comparable and Comparator support explicit ordering choices rather than relying on accidental collection order. The chapter's search exercise joins the crawler, index, and retrieval layers into a usable pipeline. A result is only as interpretable as the tokenization, matching, and ranking rules behind it. Testing should therefore include empty results, overlapping term sets, and ties, not just a query that produces one obviously relevant page.

Study task. Construct a tiny document collection with known overlaps and verify AND, OR, and difference queries before testing ranking.

Chapter 17: Sorting

The final chapter compares insertion, merge, radix, and heap-based approaches while keeping algorithm choice connected to the task. A complete sort can be unnecessary when the application only needs a bounded set of top-ranked results. Time complexity, additional space, ordering assumptions, and the size of the desired output all influence the choice. Analysis of merge sort shows how recursive structure yields a growth rate, while bounded heaps illustrate a different way to organize selection. The chapter closes the application with a broader lesson: the best algorithm is determined by a well-specified requirement rather than by a universal league table.

Study task. Compare full sorting with maintaining a bounded heap when selecting a small number of best results from a much larger collection.

Study instructions

1. For every structure, write an interface contract, representation invariant, and operation-cost table.
2. Predict growth before profiling and use multiple input sizes, warm-up, and repeated runs to interpret measurements.
3. Keep deterministic document fixtures so crawler and index tests do not depend entirely on changing live pages.
4. Separate text normalization, storage, matching, and ranking so a result can be traced to each decision.
5. Complete a bounded search-engine project and justify its structures through the actual workload, not only textbook complexity labels.

Questions for reflection

• Which assumptions turn a hashing claim into an expected rather than worst-case result?
• Why does fast mutation after finding a node not imply fast indexed mutation?
• When does selecting a top subset make full sorting unnecessary?

Sources and coverage

This original study guide follows the linked source edition and its complete main chapter sequence. It explains the ideas in new wording and adds reading tasks; it does not replace the textbook, reproduce its exercises, or supply an answer key. Publisher and book source; Complete source PDF.