Think Data Structures: Algorithms and Information Retrieval in Java

BSCS students taking a Data Structures, Algorithms, or Java-based programming elective course can read the complete textbook “Think Data Structures: Algorithms and Information Retrieval in Java” by Allen B. Downey, free from its official source, Green Tea Press. It’s a 17-chapter book that teaches data structures the way a working programmer would learn them — by implementing simplified versions of ArrayList, LinkedList, HashMap, and TreeMap from scratch, using Java’s own Collections Framework interfaces as the target contract.

This edition works through a complete data-structures toolkit — from resizable arrays and linked lists, through tree traversal, hashing, and balanced binary search trees, to a full running project building a persistent Wikipedia crawler and Boolean search engine — making it a practical, hands-on companion for anyone who already knows some Java and wants to understand what really happens inside the data structures used every day.

Book Overview

Chapter List

Chapter 1: Interfaces

Difficulty: Beginner · Data Structures — Week 1 · Key topics: Java interfaces, the Java Collections Framework, List interface, choosing an implementation by interface contract

This opening chapter introduces the book’s central teaching method — implementing core Java Collections Framework classes from scratch to understand how they really work — and starts with the idea of an interface as a contract between what a data structure promises to do and how it actually does it. It reviews the List interface and its two standard implementations, ArrayList and LinkedList, as the running example for the next several chapters.

Key Points:

• An interface in Java specifies a set of methods a class must implement, without saying anything about how those methods work internally — it is a contract, not an implementation.
• The Java Collections Framework’s List interface is implemented by more than one class, most notably ArrayList and LinkedList, which offer the identical set of operations with very different internal performance characteristics.
• Programming to an interface, rather than to a specific implementing class, lets code swap one implementation for another (say, ArrayList for LinkedList) without changing any of the code that uses the list.
• This book’s core exercise is to build simplified versions of well-known Collections Framework classes (MyArrayList, MyLinkedList, MyHashMap, and so on) in order to understand, from first principles, the implementation choices the real Java library makes.
• Understanding interfaces is a prerequisite for the rest of the book: nearly every later chapter implements a standard Java interface (List, Map) with a custom class to expose exactly how a familiar built-in data structure achieves its documented behavior.

Practice Tip: Before reading further, look up the List interface in the official Java documentation and note every method it declares — recognizing this method set will make it obvious, in later chapters, exactly which methods a custom implementation is responsible for providing.

Common Mistake: Assuming that because ArrayList and LinkedList both implement List, they must have similar internal performance — the whole point of separating interface from implementation is that two classes can expose an identical set of operations while having very different costs for individual operations, which the next few chapters examine directly.

Important Questions:

• Q1: What is the difference between a Java interface and a class that implements it? An interface declares a set of method signatures — a contract of what operations are available — without specifying how those operations work internally. A class that implements the interface provides the actual internal logic for each declared method, and different implementing classes can provide very different internal logic for the same interface.
• Q2: Why does this book implement its own versions of standard Java Collections Framework classes instead of just using the built-in ones? Because the goal is to understand how well-known data structures like ArrayList, LinkedList, and HashMap actually work internally — building simplified versions from scratch (MyArrayList, MyLinkedList, and so on) exposes the implementation choices and trade-offs hidden behind the built-in classes’ polished interfaces.

Chapter 2: Analysis of Algorithms

Difficulty: Beginner · Data Structures — Week 1–2 · Key topics: Big-O notation, algorithmic complexity, worst-case analysis, comparing ArrayList and LinkedList operation costs

This chapter introduces algorithmic analysis and Big-O notation as the tool used throughout the book to compare data structure implementations, focusing on how an operation’s running time grows as the size of the input grows, rather than on exact timings. It applies this framework immediately to ArrayList and LinkedList, showing why an operation that is fast on one can be slow on the other, setting up the implementation chapters that follow.

Key Points:

• Big-O notation describes how an algorithm’s running time grows as the input size n grows, focusing on the dominant term and ignoring constant factors — for example O(1) constant time, O(n) linear time, O(n²) quadratic time.
• Algorithmic analysis in this book is generally worst-case analysis: it asks how an operation behaves in the least favorable scenario, which gives a reliable upper bound on performance regardless of the specific input.
• Getting an element by index is O(1) for an ArrayList (direct array indexing) but O(n) for a LinkedList (must walk the list from one end), while adding to the front is O(n) for an ArrayList (must shift every element) but O(1) for a LinkedList.
• No single implementation of the List interface is unconditionally “best”: the right choice depends on which operations (indexed access, insertion at the front, insertion at the end, iteration) actually dominate in a specific program.
• This chapter’s Big-O vocabulary is the shared language used to evaluate every data structure implemented for the rest of the book, including the custom List, Map, and tree implementations built in later chapters.

Memory Tip: Keep a running two-column mental table as you go — “operation” and “cost for ArrayList vs. LinkedList” — and update it with every new chapter; this table becomes the practical basis for choosing the right implementation for a real program.

Common Mistake: Treating Big-O notation as an exact measurement of running time rather than a growth-rate description — two algorithms can both be O(n) while one is consistently faster in practice due to constant factors Big-O deliberately ignores; Big-O tells you how cost scales, not the exact runtime for a given input.

Important Questions:

• Q1: Why is get(i) O(1) for an ArrayList but O(n) for a LinkedList? An ArrayList stores its elements in a contiguous array, so get(i) can jump directly to index i in constant time. A LinkedList stores elements as separate linked nodes with no direct indexing, so reaching the i-th element requires walking node by node from one end, taking time proportional to i (and so, in the worst case, to n).
• Q2: What does “worst-case analysis” mean, and why does this book generally rely on it? Worst-case analysis asks how an algorithm performs under the least favorable possible input, giving a reliable upper bound on running time that holds for every input of a given size. The book relies on it because it gives a dependable guarantee about an implementation’s performance, rather than an average that could hide occasional very slow cases.

Chapter 3: ArrayList

Difficulty: Intermediate · Data Structures — Week 2 · Key topics: Implementing MyArrayList, resizable arrays, amortized analysis, array doubling

This chapter walks through implementing a simplified ArrayList (MyArrayList) backed by a plain Java array, exposing the central challenge of a resizable list built on a fixed-size array: what happens when the array fills up. It introduces the array-doubling strategy used by the real ArrayList and explains, via amortized analysis, why occasional expensive resize operations still average out to O(1) time per add() call.

Key Points:

• MyArrayList stores its elements in a plain Java array plus a separate integer tracking the current logical size, since the backing array’s allocated length and the list’s actual number of elements are not the same thing.
• When add() is called on a full backing array, the implementation must allocate a new, larger array and copy every existing element into it before the new element can be added — an O(n) operation.
• The array-doubling strategy allocates a new array twice the size of the old one each time a resize is needed, rather than growing by a fixed increment, which keeps resizes infrequent as the list grows.
• Amortized analysis spreads the occasional O(n) cost of a resize operation across the many O(1) add() calls that happen between resizes, showing that add() is O(1) on average (amortized) even though a small fraction of individual calls are O(n).
• This chapter’s resizing logic is the actual strategy used internally by java.util.ArrayList, so implementing MyArrayList’s resize behavior directly explains why real ArrayLists occasionally pause briefly during a long sequence of add() calls.

Practice Tip: Trace through adding elements to a MyArrayList that starts with capacity 1, writing down the backing array’s length after each resize (1, 2, 4, 8, …) — seeing how rarely resizes occur relative to the number of add() calls makes the amortized O(1) claim concrete rather than abstract.

Common Mistake: Assuming that because a single add() call can occasionally cost O(n) (when a resize happens), add() is an O(n) operation overall — amortized analysis shows that when resize costs are spread across all the add() calls between resizes, the average cost per call is O(1), which is the practically meaningful guarantee for a long sequence of adds.

Important Questions:

• Q1: Why does MyArrayList need both a backing array and a separate size field, rather than just using the array’s own length? The backing array’s allocated length is usually larger than the number of elements actually stored, to leave room for future add() calls without immediately resizing. The separate size field tracks how many of the array’s slots currently hold real elements, distinguishing “allocated capacity” from “logical number of elements.”
• Q2: Why does doubling the array’s size on each resize (rather than growing by a fixed amount) keep add() amortized O(1)? Doubling means the number of resizes needed to reach n elements grows only logarithmically with n, and each resize’s cost is proportional to the array’s current size at that point. Summing these costs across all adds and dividing by the number of adds shows the average cost per add() stays constant (O(1)), whereas growing by a fixed increment would require far more frequent, and cumulatively far more expensive, resizes.

Chapter 4: LinkedList

Difficulty: Intermediate · Data Structures — Week 3 · Key topics: Implementing MyLinkedList, singly-linked nodes, head-only insertion and traversal, comparing costs to MyArrayList

This chapter implements a simplified singly-linked list (MyLinkedList) built from individual Node objects, each holding a value and a reference to the next node, rather than a single backing array. It walks through implementing add(), get(), and size() on this node-based structure and contrasts the resulting costs directly against the MyArrayList from the previous chapter, reinforcing that the same List interface can be satisfied by structurally very different implementations.

Key Points:

• A singly-linked list stores its elements as a chain of Node objects, each holding a value and a reference (pointer) to the next node in the chain, with the list itself tracking only a reference to the first (head) node.
• Adding a new element at the front of a MyLinkedList is O(1): it only requires creating a new node and pointing it at the current head, with no shifting of existing elements, in sharp contrast to MyArrayList’s O(n) front-insertion.
• Getting an element by index in a MyLinkedList is O(n): since there is no direct indexing into a chain of nodes, reaching the i-th element requires walking the chain one node at a time from the head.
• size() can be implemented either by walking the entire chain and counting nodes (O(n)) or, more efficiently, by maintaining a separate size field updated on every add and remove (O(1)) — the same design trade-off the real java.util.LinkedList makes.
• This chapter completes the direct head-to-head comparison begun in Chapter 2: MyArrayList and MyLinkedList satisfy the identical List interface, but their opposite cost profiles (fast indexed access vs. fast front insertion) make each the better choice for different usage patterns.

Memory Tip: Picture a MyLinkedList as a chain of index cards, each with a value written on it and an arrow drawn to the next card — adding a card at the very front only means drawing one new arrow, while finding the 50th card means following 50 arrows one at a time from the start.

Common Mistake: Implementing get(i) on a linked list by assuming any kind of direct-access shortcut exists — unlike an array, a linked list has no way to jump directly to the i-th node; reaching it always requires following node references one at a time from the head, which is exactly why get(i) is O(n) for a linked list but O(1) for an array-backed list.

Important Questions:

• Q1: Why is inserting at the front of a MyLinkedList O(1), while inserting at the front of a MyArrayList is O(n)? Inserting at the front of a linked list only requires creating one new node and pointing it at the current head node — no existing nodes need to move. Inserting at the front of an array-backed list requires shifting every existing element one position to the right to make room, which takes time proportional to the number of elements already in the list.
• Q2: What are the two ways size() could be implemented for MyLinkedList, and why would one be preferred? size() could either walk the entire chain of nodes counting them each time it is called (O(n)), or the list could maintain a separate integer field that is incremented and decremented on every add and remove, making size() a simple O(1) field lookup. The second approach is preferred, and is what the real java.util.LinkedList does, because it avoids repeating an O(n) traversal every time the list’s size is checked.

Chapter 5: Doubly-linked list

Difficulty: Intermediate · Data Structures — Week 3–4 · Key topics: Doubly-linked nodes, the Deque interface, efficient removal, bidirectional traversal

This chapter extends the singly-linked list from the previous chapter into a doubly-linked list, where each node holds references to both its next and previous neighbors, and the list tracks both a head and a tail reference. It shows how this extra bookkeeping makes certain operations — notably removal of a node and insertion at the back — efficient in ways a singly-linked list cannot support without extra traversal cost.

Key Points:

• A doubly-linked node stores references to both its next and previous neighbors, and the list itself keeps a reference to both the head (first) and tail (last) node, rather than only the head.
• Because each node knows its own predecessor, removing an arbitrary node given a direct reference to it is O(1): the node’s neighbors can be relinked directly without any traversal to find the predecessor.
• Adding an element at the back of the list is O(1) with a maintained tail reference, since the new node can be attached directly to the current tail without walking the whole chain to find the end.
• A doubly-linked list supports efficient bidirectional traversal (forward from the head or backward from the tail), which is the structural basis for Java’s own Deque interface and its ArrayDeque/LinkedList implementations.
• The extra prev references and tail bookkeeping cost additional memory and additional pointer updates on every insertion and removal, compared to a singly-linked list — a real trade-off, not a free improvement, that this chapter makes explicit.

Practice Tip: Draw a small doubly-linked list of three or four nodes by hand, with both forward and backward arrows between each pair, then trace through removing the middle node on paper — the relinking of exactly two pairs of pointers (no traversal needed) makes the O(1) removal claim concrete.

Common Mistake: Forgetting to update both the next AND the previous references (in both directions) when inserting or removing a node in a doubly-linked list — updating only one direction leaves the list in an inconsistent state where forward and backward traversal disagree about the list’s actual contents.

Important Questions:

• Q1: Why can removing a node be done in O(1) time in a doubly-linked list, given a direct reference to the node, but not in a singly-linked list? In a doubly-linked list, each node already knows its own predecessor via its prev reference, so removal just relinks the predecessor and successor directly to each other. In a singly-linked list, a node has no reference to its predecessor, so removing it requires first traversing from the head to find the predecessor, making removal O(n) in general.
• Q2: What extra cost does a doubly-linked list pay compared to a singly-linked list, in exchange for its added capabilities? Each node needs an extra reference field (to its previous neighbor, not just its next one), and every insertion or removal must correctly update pointers in both directions rather than just one — more memory per node and more pointer bookkeeping per operation, in exchange for O(1) removal-given-a-reference and O(1) back-insertion.

Chapter 6: Tree traversal

Difficulty: Intermediate · Data Structures — Week 4 · Key topics: Tree data structures, recursive traversal, depth-first vs. breadth-first, HTML DOM as a tree example

This chapter introduces tree data structures using the HTML Document Object Model (DOM) as a concrete, motivating real-world example, and covers the classic traversal strategies for visiting every node in a tree: depth-first traversal (implemented recursively, diving down one branch before backtracking) and breadth-first traversal (implemented with a queue, visiting all nodes at one depth level before moving to the next).

Key Points:

• A tree is a hierarchical data structure of nodes, where each node (except the root) has exactly one parent and can have any number of children, with no cycles — the HTML DOM, where each element can contain other elements, is used here as a natural, familiar example.
• Depth-first traversal visits a node, then recursively traverses fully into one child’s subtree before moving to the next child, naturally implemented with recursion (or an explicit stack) and requiring memory proportional to the tree’s depth.
• Breadth-first traversal visits all nodes at the current depth level before moving to the next level, implemented using a queue (not a stack) to hold nodes waiting to be visited in level order.
• The choice between depth-first and breadth-first traversal depends on the task: depth-first is natural for tasks like searching a specific branch or evaluating an expression tree, while breadth-first is natural for tasks like finding the shortest path or the nearest match by level.
• This chapter’s tree-traversal techniques directly set up the following chapters (Getting to Philosophy, Indexer) which apply exactly these traversal ideas to real HTML documents fetched from live web pages.

Memory Tip: Keep the data-structure pairing straight: depth-first traversal naturally uses a stack (or recursion, which uses the call stack implicitly), while breadth-first traversal naturally uses a queue — the traversal order you get is a direct consequence of which of the two structures you choose to hold pending nodes.

Common Mistake: Using a stack when a breadth-first (level-by-level) traversal is required, or a queue when a depth-first traversal is required — swapping the underlying holding structure changes the visiting order completely, since a stack always processes the most recently added node next while a queue always processes the earliest added node next.

Important Questions:

• Q1: What is the key structural difference between depth-first and breadth-first tree traversal? Depth-first traversal fully explores one branch (subtree) before backtracking to explore the next branch, naturally implemented with recursion or a stack. Breadth-first traversal visits every node at the current depth level before moving on to the next level, implemented using a queue to hold nodes in the order they should be visited.
• Q2: Why is the HTML DOM a natural example for introducing tree traversal in this chapter? The HTML DOM is itself a tree: each HTML element can contain other elements as children, with a single root element at the top and no cycles — exactly the structure a general tree traversal algorithm is designed to visit, and a structure most readers already have some intuitive familiarity with from web pages.

Chapter 7: Getting to Philosophy

Difficulty: Intermediate · Data Structures — Week 5 · Key topics: Web scraping with Jsoup, the “Getting to Philosophy” Wikipedia phenomenon, following the first link, using a HashSet to detect cycles

This chapter applies the tree/graph traversal ideas from the previous chapter to a real, entertaining case study: the “Getting to Philosophy” phenomenon, where repeatedly following the first valid link in a Wikipedia article’s body text eventually leads to the Philosophy article for the great majority of pages. It walks through fetching and parsing live Wikipedia pages with the Jsoup HTML-parsing library and using a HashSet to detect when the chain of links starts to cycle.

Key Points:

• The “Getting to Philosophy” phenomenon is the observed tendency for repeatedly following the first non-parenthetical, non-italicized link in a Wikipedia article’s main text to eventually reach the Philosophy article, for most starting articles.
• Jsoup is used to fetch a live Wikipedia page’s HTML and parse it into a navigable DOM tree, from which the program locates the article’s first qualifying link using the DOM traversal techniques from the previous chapter.
• A HashSet of already-visited article titles is used to detect cycles: since some starting articles lead into a loop rather than reaching Philosophy, the program must recognize when it has already visited a page to avoid traversing forever.
• Implementing this chapter’s link-following program combines nearly every technique covered so far: HTML tree traversal, following an edge in an implicit web graph, and a hash-based set for fast membership testing, previewed here before hashing itself is formally covered.
• This chapter is a concrete, motivating bridge from the book’s early data-structure chapters into the web-crawling and information-retrieval project (Indexer, Crawling Wikipedia, Boolean search) that runs through the rest of the book.

Practice Tip: Before writing the cycle-detection logic, trace the “Getting to Philosophy” chain by hand for a Wikipedia article you know well, clicking the first link each time — predicting the chain yourself first makes it much easier to recognize whether your program’s automated version is actually finding the same links you found.

Common Mistake: Omitting cycle detection entirely, or checking for cycles by re-scanning the full history list on every step instead of using a HashSet — the first causes some inputs to loop forever, and the second works but degrades to slow, unnecessary O(n) checks on every step when a HashSet gives expected O(1) membership testing instead.

Important Questions:

• Q1: What is the “Getting to Philosophy” phenomenon this chapter investigates? The observation that if you repeatedly follow the first valid link in the body text of a Wikipedia article (ignoring links in parentheses, italics, and a few other exceptions), you eventually reach the Philosophy article for the great majority of starting articles.
• Q2: Why is a HashSet used to track visited articles in this chapter’s link-following program, rather than a List? Because the program needs to repeatedly check whether the current article has already been visited, to detect and stop at a cycle. A HashSet provides expected O(1) membership testing (contains()), while checking membership in a List would require an O(n) linear scan on every single step of the chain.

Chapter 8: Indexer

Difficulty: Intermediate · Data Structures — Week 6 · Key topics: Building a search index, mapping words to the pages containing them, the Map interface as a foundation, in-memory indexing

This chapter begins the book’s information-retrieval project by building a simple in-memory search index: a data structure that maps each word appearing across a small set of web pages to the set of pages containing that word. It motivates the Map interface as the natural tool for this job and previews the performance questions (how fast can a word be looked up, how is memory used) that the next several chapters on hashing and maps address directly.

Key Points:

• A search index inverts the natural document-to-words relationship into a word-to-documents relationship, so that given a search term, the index can immediately report which pages contain it, rather than scanning every page’s text on every search.
• The Map interface (word as key, set of containing pages as value) is the natural data structure for a search index, since it needs to associate each unique word with a collection of the pages where that word was found.
• Building the index requires processing each page’s text into individual words (tokenizing), then, for each word, adding the current page to that word’s associated set of pages in the map.
• This chapter’s index is deliberately built as a simple in-memory prototype first, entirely without persistence, so that the indexing logic itself can be understood before the book adds real persistent storage in a later chapter.
• The indexer built here is a direct precursor to the Boolean search chapter later in the book, which uses exactly this word-to-pages index structure to answer multi-word search queries.

Memory Tip: Think of the index as flipping a table: instead of a “page → words on that page” table (which is what you’d naturally build first), the index is a “word → pages containing that word” table — the whole point of an index is to make that second, inverted lookup direction fast.

Common Mistake: Building an index that maps a word to only the LAST page it was found on, by overwriting the previous entry instead of adding to a set of pages for that word — a real index must associate each word with the full collection of pages containing it, not just the single most-recently-processed page.

Important Questions:

• Q1: Why is a Map, rather than a List, the natural data structure for the search index built in this chapter? The index needs to associate each unique word (the key) with the set of pages that contain it (the value), so that looking up a word immediately returns its associated pages. A Map directly supports this key-to-value association and fast lookup by key, which a List does not provide without a slow linear search.
• Q2: What does it mean to say a search index “inverts” the natural page-to-words relationship? Naturally, each page has an associated set of words it contains. An index flips this around into a word-to-pages relationship: for each unique word, the index stores the set of pages containing that word, so a search for a word can jump directly to its relevant pages instead of scanning every page’s text.

Chapter 9: The Map interface

Difficulty: Intermediate · Data Structures — Week 6–7 · Key topics: The Map interface’s methods, key-value pairs, implementing MyLinearMap with a backing list, motivating faster implementations

This chapter formally introduces the Map interface’s core methods (put, get, containsKey, remove) and implements a first, deliberately simple version, MyLinearMap, backed by a plain list of key-value pair entries. It shows that while this simple approach correctly satisfies the Map interface’s contract, every operation requires an O(n) linear search through the list of entries — motivating the faster, hashing-based implementations covered in the next two chapters.

Key Points:

• The Map interface associates unique keys with values and provides methods including put (add or update a key-value pair), get (retrieve the value for a key), containsKey (check whether a key is present), and remove (delete a key-value pair).
• MyLinearMap stores its key-value pairs as a list of simple Entry objects, and implements get(key) by scanning the list from the start, comparing each entry’s key to the target key, until a match is found or the list is exhausted.
• Because every operation in MyLinearMap must potentially scan the entire list of entries, put, get, containsKey, and remove are all O(n) in the worst case — correct, but slow for a map with many entries.
• MyLinearMap is deliberately built as a correctness baseline and a teaching stepping stone, not as a practical map implementation: its simplicity makes the Map contract concrete before hashing is introduced to make these same operations fast.
• This chapter directly sets up the next two chapters, which build a hash-based map (MyHashMap) by combining many small MyLinearMap instances (buckets) with a hash function, turning O(n) linear search into expected O(1) lookup.

Practice Tip: Implement MyLinearMap’s get(key) method yourself and time it (informally) on maps of increasing size — watching the lookup time grow roughly linearly with the number of entries makes the O(n) cost, and the motivation for hashing in the next chapter, directly visible rather than theoretical.

Common Mistake: Assuming any Map implementation automatically provides fast O(1) lookup simply because it satisfies the Map interface — the interface only guarantees WHAT operations are available (put, get, and so on), not HOW FAST they are; MyLinearMap satisfies the exact same interface as a hash-based map while being asymptotically much slower for large maps.

Important Questions:

• Q1: Why is get(key) an O(n) operation for MyLinearMap in the worst case? MyLinearMap stores its key-value pairs as entries in a plain list with no special ordering or indexing by key. Finding the entry for a given key requires scanning through the list, comparing keys one at a time, until a match is found (or the list is exhausted), which takes time proportional to the number of entries in the worst case.
• Q2: What is the purpose of building MyLinearMap before building a hash-based map, given that MyLinearMap is slow? MyLinearMap establishes a simple, clearly correct baseline implementation of the Map interface’s contract, making the required behavior of put, get, containsKey, and remove concrete before introducing the added complexity of hashing. It also gives a clear performance baseline (O(n)) to compare against once a faster hash-based implementation is built in the following chapters.

Chapter 10: Hashing

Difficulty: Advanced · Data Structures — Week 7 · Key topics: Hash functions, hash codes, hashCode() and equals() in Java, hash collisions, distributing keys across buckets

This chapter explains hashing: converting a key into an integer hash code via a hash function, then using that code to determine which “bucket” the key belongs in, so that lookup can jump nearly directly to the right bucket instead of scanning every entry. It covers Java’s hashCode() and equals() methods and their required contract, and explains hash collisions — when different keys hash to the same bucket — as an unavoidable possibility that any hash-based map must handle correctly.

Key Points:

• A hash function converts a key into an integer hash code, ideally distributing different keys as evenly as possible across the range of possible hash codes, so that keys spread out roughly uniformly across available buckets.
• In Java, every object’s hashCode() and equals() methods must satisfy a strict contract: if two objects are equal according to equals(), they MUST return the same hashCode() value, though the reverse is not required (different objects can share a hash code).
• A hash collision occurs when two different keys produce the same hash code (and so map to the same bucket) — collisions are not a bug or a sign of a bad hash function, but an unavoidable possibility that must be handled correctly by any hash-based map.
• The quality of a hash function affects performance, not correctness: a poor hash function that clusters many keys into few buckets degrades lookup toward the O(n) worst case, while a good hash function keeps buckets small and lookup close to O(1).
• This chapter’s hashCode()/equals() contract and collision-handling concepts are the direct theoretical foundation for MyHashMap, implemented in the very next chapter using an array of MyLinearMap buckets.

Memory Tip: Remember the hashCode()/equals() contract in one direction only: equal objects MUST share a hash code, but objects sharing a hash code are NOT required to be equal — that asymmetry is exactly why collisions are possible and must be handled, not treated as a contract violation.

Common Mistake: Overriding equals() on a custom class without also overriding hashCode() (or vice versa) — this breaks the required contract that equal objects must produce equal hash codes, causing a hash-based map or set to fail to find an entry even when an “equal” key is used to look it up, a classic and hard-to-diagnose Java bug.

Important Questions:

• Q1: What is the required relationship between hashCode() and equals() in Java, and why does it matter for a hash-based map? If two objects are equal according to equals(), they must return the same value from hashCode(). This matters because a hash-based map uses hashCode() to decide which bucket to search, then equals() to confirm a match within that bucket — if equal objects had different hash codes, the map could look in the wrong bucket entirely and fail to find an entry that is genuinely present.
• Q2: Is a hash collision a sign that something has gone wrong with a hash function? Explain. No. A collision — two different keys producing the same hash code — is an unavoidable possibility for any hash function mapping a large space of possible keys onto a smaller range of hash codes. A good hash function minimizes how often collisions happen and spreads keys evenly across buckets, but a hash-based map must still correctly handle collisions whenever they do occur.

Chapter 11: HashMap

Difficulty: Advanced · Data Structures — Week 8 · Key topics: Implementing MyHashMap, array of buckets, resizing a hash table, amortized O(1) performance

This chapter implements MyHashMap by combining the hashing concepts from the previous chapter with an array of MyLinearMap buckets: a key’s hash code (modulo the number of buckets) determines which bucket’s small linear map holds it. It covers resizing the bucket array as the map grows to keep the average bucket small, arriving at the same amortized O(1) performance argument used for MyArrayList in Chapter 3, now applied to hash table resizing.

Key Points:

• MyHashMap stores an array of buckets, where each bucket is itself a small MyLinearMap; a key’s hashCode(), reduced modulo the array’s length, determines which bucket that key-value pair belongs in.
• get(key) computes the key’s target bucket via its hash code, then performs a linear search only within that one (typically very small) bucket, rather than across the entire map — this is what turns O(n) linear search into expected O(1) lookup.
• As more entries are added, the average number of entries per bucket (the load factor) grows; if buckets get too large, lookup within each bucket degrades back toward O(n), which is why the map must resize (grow the number of buckets) once the load factor crosses a threshold.
• Resizing a MyHashMap requires creating a new, larger bucket array and re-inserting every existing entry, recomputing each one’s bucket index against the new array length — an O(n) operation, exactly analogous to MyArrayList’s array-doubling resize from Chapter 3.
• Because resizes happen infrequently relative to the number of put() calls (following the same doubling strategy as MyArrayList), amortized analysis shows put() and get() are O(1) on average, even though individual operations can occasionally be O(n) during a resize.

Practice Tip: Draw a small MyHashMap as an array of, say, 4 buckets, each holding a tiny MyLinearMap, then manually compute the bucket index for several keys using their hash codes mod 4 — watching keys land in different (or occasionally the same) bucket makes the array-of-linear-maps design concrete.

Common Mistake: Forgetting to resize the bucket array as a MyHashMap grows, letting every key pile into a small, fixed number of buckets — without resizing, the average bucket size grows linearly with the total number of entries, and lookup degrades from the intended near-O(1) performance back toward the O(n) linear-search performance the hash table was built specifically to avoid.

Important Questions:

• Q1: How does MyHashMap use a key’s hash code to decide where to store a key-value pair? The key’s hashCode() is computed and then reduced modulo the length of the bucket array (the number of available buckets), producing a bucket index. The key-value pair is then stored (as an entry) inside that specific bucket’s own small MyLinearMap.
• Q2: Why does MyHashMap need to resize its bucket array as more entries are added, and what does this cost? As more entries are added without resizing, the average bucket grows larger, and since lookup within a bucket is a linear search, larger buckets mean slower lookups. Resizing — allocating a larger bucket array and reinserting every entry into its newly recomputed bucket — keeps the average bucket small and lookup fast, at the cost of an O(n) operation each time a resize occurs, which amortized analysis shows still averages out to O(1) per put().

Chapter 12: TreeMap

Difficulty: Advanced · Data Structures — Week 8–9 · Key topics: The TreeMap interface, ordered keys, sorted iteration, comparing TreeMap to HashMap trade-offs

This chapter introduces TreeMap as a Map implementation that, unlike MyHashMap, keeps its keys in sorted order, letting operations like finding the smallest or largest key, or iterating over all entries in order, be done efficiently and predictably. It contrasts TreeMap’s O(log n) operations and ordering guarantees against MyHashMap’s amortized O(1) but unordered operations, framing the choice as another instance of the book’s recurring implementation-trade-off theme.

Key Points:

• TreeMap keeps its keys in sorted order internally (using a self-balancing binary search tree, covered structurally in the next chapter), which HashMap makes no attempt to do — HashMap’s iteration order is effectively arbitrary.
• Because its keys are kept sorted, TreeMap can efficiently support order-dependent operations that HashMap cannot support efficiently at all, such as finding the smallest or largest key, or finding the nearest key above or below a given value.
• TreeMap’s core operations (put, get, remove) run in O(log n) time due to the underlying balanced tree structure — slower than HashMap’s amortized O(1), but with the added benefit of maintained order.
• Choosing between HashMap and TreeMap is a direct trade-off: HashMap is faster when only unordered key-value lookup is needed, while TreeMap is the right choice whenever sorted iteration or order-based queries are required by the application.
• TreeMap requires that its keys be comparable to one another (implementing Comparable, or supplied with a separate Comparator), since maintaining sorted order requires the ability to determine which of two keys comes first — a requirement HashMap does not share.

Memory Tip: Remember the core trade-off as speed versus order: HashMap trades away any ordering guarantee in exchange for amortized O(1) operations, while TreeMap accepts the slower O(log n) operations in exchange for always-sorted keys and efficient order-based queries.

Common Mistake: Choosing TreeMap by default for every situation “just to be safe,” without needing any of its ordering guarantees — if a program never needs sorted iteration or order-based queries, TreeMap’s O(log n) operations are needlessly slower than HashMap’s amortized O(1) operations for no practical benefit.

Important Questions:

• Q1: What capability does TreeMap provide that HashMap does not, and why? TreeMap maintains its keys in sorted order internally, so it can efficiently support order-based operations like retrieving the smallest or largest key, or finding entries near a given key. HashMap makes no attempt to maintain any ordering among its keys, so equivalent order-based queries are not efficiently supported by HashMap.
• Q2: What is the time-complexity trade-off between TreeMap and HashMap for basic operations like put and get? TreeMap’s put and get run in O(log n) time, due to its underlying balanced binary search tree structure. HashMap’s put and get run in amortized O(1) time via hashing. HashMap is faster for plain key-value lookup, but only TreeMap maintains sorted key order as a byproduct of its structure.

Chapter 13: Binary search tree

Difficulty: Advanced · Data Structures — Week 9 · Key topics: Binary search tree structure and invariant, implementing MyTreeMap, insertion and lookup by comparison, tree balance

This chapter implements the binary search tree (BST) structure underlying TreeMap, explaining the core BST invariant — every node’s left subtree contains only smaller keys and its right subtree contains only larger keys — and how this invariant makes both insertion and lookup proceed by a sequence of comparisons that discard half the remaining tree at each step. It also raises tree balance as a real concern: an unbalanced BST degrades toward the same O(n) worst case a linked list would have.

Key Points:

• A binary search tree maintains the invariant that, for every node, all keys in its left subtree are smaller than the node’s own key, and all keys in its right subtree are larger — this invariant is what makes efficient search possible.
• Looking up a key in a BST proceeds by comparing the target key to the current node’s key at each step, moving left or right accordingly, discarding the other half of the remaining subtree entirely at each comparison — the same halving idea as binary search over a sorted array.
• In a perfectly balanced BST, this halving gives O(log n) lookup and insertion, since the tree’s height is proportional to log n; but if a tree becomes unbalanced (for example, if keys are inserted in already-sorted order, producing a tree that degenerates into a straight chain), the height can grow to O(n), and performance degrades to that of a linked list.
• MyTreeMap implements get(key) and put(key, value) by walking down from the root, comparing keys at each node and moving left or right, inserting a new node as a leaf at the position where the search would otherwise have found the key.
• This chapter deliberately leaves rebalancing (the technique real production TreeMap implementations use to guarantee O(log n) even in the worst case) outside its scope, so that the BST invariant and the basic search/insert logic can be understood clearly on their own first.

Practice Tip: Insert the same set of keys into a BST in two different orders — once already sorted, and once in a random shuffle — and sketch the resulting tree shapes by hand; seeing the sorted order produce a long, degenerate chain while the shuffled order produces a shorter, bushier tree makes the balance concern concrete.

Common Mistake: Assuming a binary search tree’s operations are always O(log n) regardless of insertion order — the O(log n) guarantee depends entirely on the tree remaining roughly balanced; inserting keys in already-sorted order (a common real-world mistake) produces a completely unbalanced tree that degrades toward O(n), the same as a linked list.

Important Questions:

• Q1: What is the binary search tree invariant, and how does it make lookup efficient? For every node in the tree, all keys stored in its left subtree are smaller than the node’s own key, and all keys in its right subtree are larger. This lets lookup compare the target key to the current node and immediately discard one entire subtree (the one that cannot possibly contain the target) at every step, similar to how binary search discards half a sorted array at each step.
• Q2: Why can a binary search tree’s performance degrade to O(n), and under what circumstance does this typically happen? The O(log n) performance of BST operations depends on the tree being reasonably balanced (height proportional to log n). If keys are inserted in an order that produces a highly unbalanced tree — most notably inserting keys that are already sorted, which produces a tree that degenerates into a single long chain — the tree’s height approaches n, and operations degrade to the same O(n) cost as searching a linked list.

Chapter 14: Persistence

Difficulty: Advanced · Data Structures — Week 10 · Key topics: Persistent storage for the index, Redis as a key-value store, the Jedis Java client, serializing the in-memory index

This chapter extends the in-memory search index from Chapter 8 into a persistent one, backed by Redis, an external key-value store, accessed from Java via the Jedis client library. It covers why an in-memory index is insufficient for a real search application (all data is lost when the program exits) and walks through storing and retrieving the word-to-pages index data as Redis keys and values instead of plain in-memory Java collections.

Key Points:

• An entirely in-memory index (as built in Chapter 8) loses all of its data the moment the program exits, which is unacceptable for a real search index meant to be built once and queried repeatedly over time.
• Redis is an external, separately-running key-value store that persists its data to disk and can be accessed over a network connection, making it a natural choice for storing an index that must survive beyond a single program’s lifetime.
• Jedis is the Java client library used in this chapter to connect to a Redis server and issue commands (like storing a value under a key, or retrieving a value by key) directly from Java code.
• Moving the index from an in-memory Java Map to Redis requires re-expressing the word-to-pages structure as Redis’s own key-value and set operations — a concrete example of adapting an in-memory data structure design to an external persistent store.
• This chapter’s persistent index is what makes the following chapters (Crawling Wikipedia, Boolean search) practical at a realistic scale: a crawler can add pages to the index incrementally over multiple runs, and search queries can be answered against previously indexed data without re-crawling anything.

Memory Tip: Think of Redis in this chapter the same way you’d think of a filing cabinet outside your program: your Java program’s in-memory Map exists only while the program is running, but data stored in Redis through Jedis is still there, on disk, the next time your program starts up.

Common Mistake: Confusing Redis (an external key-value store your program connects to over a network) with a plain in-memory Java Map — unlike a Map, a Redis store exists independently of any single running Java program, requires an actual client connection (via Jedis) to read or write, and is what actually gives the index the ability to persist across separate program runs.

Important Questions:

• Q1: Why is an entirely in-memory index (like the one built in Chapter 8) insufficient for a real search application? An in-memory index exists only in the running Java program’s memory, so all of the indexed data is lost the moment the program exits. A real search index needs to be built once (or incrementally over time) and then queried repeatedly across many separate program runs, which requires the index data to persist independently of any single program’s lifetime.
• Q2: What role does Jedis play in this chapter’s persistent index? Jedis is the Java client library used to connect from Java code to an external Redis server, letting the program issue Redis commands (storing and retrieving key-value data) directly. It is the bridge that lets the index’s word-to-pages data actually be written to, and later read back from, Redis’s persistent storage.

Chapter 15: Crawling Wikipedia

Difficulty: Advanced · Data Structures — Week 11 · Key topics: Building a web crawler, a queue of pages to visit, extracting and following links, integrating with the persistent index

This chapter builds a web crawler that starts from a given Wikipedia page, indexes its content into the persistent Redis-backed index from the previous chapter, extracts the links on that page, and adds newly discovered pages to a queue to be crawled next. It combines the graph and queue-based breadth-first traversal ideas from Chapter 6 with the persistent indexing from Chapter 14 into a single working crawler-and-indexer program.

Key Points:

• The crawler maintains a queue of pages still to be visited, starting with one or more seed URLs, following a breadth-first traversal pattern directly analogous to the tree-traversal techniques covered in Chapter 6.
• For each page the crawler visits, it must do two things: index the page’s content into the persistent index (so the page becomes searchable), and extract the page’s outgoing links so newly discovered pages can be added to the crawl queue.
• The crawler must track which pages have already been visited (using a technique analogous to the HashSet-based cycle detection from Chapter 7) to avoid re-indexing the same page repeatedly or crawling forever in a cycle.
• Because the persistent index from Chapter 14 survives across program runs, the crawler can be stopped and restarted, gradually building up a larger and larger searchable index of Wikipedia content over multiple crawling sessions rather than needing to complete in one run.
• This chapter’s crawler is the data-gathering half of the book’s search-engine project: it populates the persistent index that the Boolean search chapter, next, will query against to actually answer search requests.

Practice Tip: Before running the crawler against many pages, test it against a tiny seed set of two or three closely linked pages and print out exactly which pages get queued and visited in what order — confirming the breadth-first queue behavior on a small, predictable case first makes debugging a larger crawl far easier.

Common Mistake: Failing to track already-visited pages while crawling, or checking the visited set inefficiently — without proper cycle/duplicate detection, a crawler can re-index the same heavily-linked pages repeatedly or, worse, loop forever between a small cluster of mutually-linking pages instead of making progress across the wider set of pages to be indexed.

Important Questions:

• Q1: What two things does the crawler do for each page it visits? It indexes the page’s content into the persistent Redis-backed index so the page becomes searchable, and it extracts the page’s outgoing links, adding any newly discovered pages to the queue of pages still to be crawled.
• Q2: Why does building the index in a persistent store (Chapter 14) matter specifically for the crawler in this chapter? Because a full web crawl can take a long time and may need to be stopped and resumed across multiple sessions. Since the index persists in Redis rather than only in the crawler program’s memory, the crawler can add to the same growing index incrementally across separate runs, rather than losing all indexed progress every time the program stops.

Chapter 16: Boolean search

Difficulty: Advanced · Data Structures — Week 12 · Key topics: Multi-term search queries, set intersection and union for AND/OR queries, querying the persistent index

This closing project chapter implements Boolean search — answering multi-word queries like “data AND structures” or “java OR python” — by querying the persistent index built by the crawler for each individual search term, then combining the resulting page sets using set intersection (for AND) or set union (for OR). It ties together the index (Chapter 8), persistence (Chapter 14), and crawler (Chapter 15) into a working, queryable mini search engine.

Key Points:

• A Boolean AND query (“data AND structures”) is answered by looking up each individual term’s set of containing pages in the index, then computing the set intersection of those sets — pages that contain every term in the query.
• A Boolean OR query (“java OR python”) is answered similarly, but by computing the set union of each term’s page set instead — pages that contain at least one of the query terms.
• This chapter reuses the exact index structure built in Chapter 8 (word mapped to set of containing pages) and now populated persistently by the crawler from Chapter 15, showing how a data structure designed early in the book directly enables a real feature built much later.
• Efficient set intersection and union rely on the underlying page-set implementation supporting fast membership testing (as a HashSet does, from the hashing chapters), rather than a naive nested loop comparing every pair of pages across the two sets.
• Completing this chapter delivers the book’s running project end to end: a crawler that indexes real Wikipedia pages into persistent storage, and a Boolean search layer on top of that index capable of answering real multi-word queries — the payoff for every data structure covered from Chapter 1 onward.

Memory Tip: Keep the AND/OR mapping simple and literal: AND means intersection (only pages present in EVERY term’s set survive), OR means union (pages present in ANY term’s set survive) — the Boolean query word tells you directly which basic set operation to reach for.

Common Mistake: Computing set intersection or union with a naive nested loop that compares every page in one term’s set against every page in another term’s set — when the underlying sets are HashSets, this throws away their O(1) membership-testing advantage; iterating over the smaller set and calling contains() on the other set is far more efficient than an unnecessary O(n²) pairwise comparison.

Important Questions:

• Q1: How is a Boolean AND query like “data AND structures” answered using the index built earlier in the book? The index is used to look up the set of pages containing “data” and, separately, the set of pages containing “structures.” The query is answered by computing the set intersection of these two sets — the pages that appear in both, since an AND query requires every term to be present.
• Q2: Why does this chapter’s Boolean search functionality depend on the persistence work from Chapter 14 and the crawler from Chapter 15? Boolean search answers queries by looking up terms in the index, but that index is only useful and complete if it has actually been populated with real page data first. The crawler (Chapter 15) is what populates the index by visiting real Wikipedia pages, and persistence (Chapter 14) is what allows that populated index to survive and accumulate across multiple crawling sessions, so that Boolean search has a substantial, realistic index to query against.

Chapter 17: Sorting

Difficulty: Advanced · Data Structures — Week 12–13 · Key topics: Comparison-based sorting algorithms, merge sort, the O(n log n) lower bound, Java’s built-in sort methods

This closing chapter steps back from the search-engine project to cover sorting algorithms, implementing merge sort as the primary example of an efficient, comparison-based, divide-and-conquer sorting algorithm running in O(n log n) time. It explains why O(n log n) is a fundamental lower bound for any comparison-based sorting algorithm, and relates this theoretical material back to Java’s own built-in Collections.sort() and Arrays.sort() methods.

Key Points:

• Merge sort works by recursively dividing a list in half until each piece has zero or one elements (trivially sorted), then merging pairs of already-sorted sublists back together in sorted order, all the way back up to a single fully sorted list.
• The merge step — combining two already-sorted lists into one sorted list — can be done in O(n) time by repeatedly comparing the two lists’ current front elements and taking the smaller one, without needing to compare every pair of elements.
• Merge sort’s recursive halving (log n levels of recursion) combined with an O(n) merge at each level gives an overall running time of O(n log n), which is asymptotically much faster than simple O(n²) sorting algorithms for large inputs.
• O(n log n) is not just a property of merge sort specifically — it is a proven lower bound for the running time of ANY comparison-based sorting algorithm, meaning no comparison-based algorithm can sort in better than O(n log n) time in the worst case.
• Java’s built-in Collections.sort() and Arrays.sort() (for object types) are themselves based on a highly-tuned merge sort variant (Timsort), so implementing merge sort by hand in this chapter directly explains the algorithm actually running underneath these familiar built-in library calls.

Practice Tip: Trace merge sort by hand on a small list of 8 numbers, writing out each recursive split down to single elements and then each merge step back up — seeing exactly log₂(8)=3 levels of splitting makes the O(n log n) time complexity’s origin concrete rather than a memorized formula.

Common Mistake: Assuming a faster sorting algorithm than O(n log n) must exist for comparison-based sorting, if only the right clever algorithm were found — O(n log n) is a proven mathematical lower bound for any algorithm that sorts purely by comparing pairs of elements; going faster than O(n log n) in the worst case is only possible for specialized non-comparison-based sorting methods under extra assumptions about the data, not for general comparison-based sorting.

Important Questions:

• Q1: How does merge sort achieve O(n log n) running time, in terms of its two main steps? Merge sort recursively divides the list in half until reaching trivially sorted pieces of zero or one elements — this recursive halving takes log n levels. At each level, merging all the sorted sublists back together takes O(n) total work across that level. Multiplying the O(n) work per level by the log n levels gives the overall O(n log n) running time.
• Q2: Why is O(n log n) described as a lower bound for comparison-based sorting, rather than just merge sort’s own specific running time? It has been mathematically proven that any sorting algorithm that works only by comparing pairs of elements to each other cannot sort a list of n elements faster than O(n log n) in the worst case, regardless of how cleverly it is designed. Merge sort achieves this optimal bound, but the bound itself applies to the entire category of comparison-based algorithms, not just to merge sort specifically.

Download Think Data Structures PDF (Free)

This book is free from its official source — author Allen B. Downey publishes this edition under a Creative Commons licence. Download the complete PDF below, or read the free HTML edition on the official site.

How to Study This Book

This book is organized to build progressively: Chapters 1–5 (Interfaces through Doubly-linked list) implement the List interface’s two classic backing structures from scratch, and should be read in order since each chapter builds directly on the analysis introduced in Chapter 2.

Chapters 6–9 (Tree traversal through The Map interface) shift to trees and the Map interface, using a live Wikipedia link-following program (Getting to Philosophy) as a motivating, hands-on case study before formally introducing Map.

Chapters 10–13 (Hashing through Binary search tree) cover the two main strategies for making a Map fast — hashing and balanced trees — and should be read in order, since HashMap depends directly on the hashing concepts covered immediately before it.

Chapters 14–17 (Persistence through Sorting) complete a running project: a persistent, crawler-built search index over real Wikipedia pages, queried with Boolean AND/OR search, closing with a self-contained chapter on merge sort.

This book teaches by implementing real Java Collections Framework classes (MyArrayList, MyHashMap, MyTreeMap, and so on) from scratch — working through the accompanying code on the author’s GitHub repository alongside the text is essential to how the material is meant to be used.

Used In These Programs

This book is used as a Data Structures, Algorithms, or Java-based CS elective text in: BSCS and Programming coursework. Browse all Computer Science category books.

Who Should Read This

Think Data Structures is written for students and self-learners who already know some Java and want to understand how core data structures — ArrayList, LinkedList, HashMap, TreeMap, and binary search trees — actually work internally, by implementing simplified versions of them from scratch. It suits BSCS students taking a Data Structures or Algorithms course, and is especially useful for anyone who wants to see these structures applied to a real, working project: a persistent web crawler and Boolean search engine built over live Wikipedia pages.

Applicable Universities

This book is useful for students at Pakistani universities offering BSCS programs with a Data Structures, Algorithms, or Java-based programming elective course, including Punjab University, Virtual University, COMSATS, FAST, UET, NUST, GIKI, and other HEC-recognized institutions, and for self-learners who already know Java and want a free, implementation-first introduction to data structures.

FAQs

Related Books

• Think Java – Allen B. Downey & Chris Mayfield (the introductory Java foundation this book assumes)
• Think Complexity – Allen B. Downey (a companion book applying Python to complexity science and simulation)
• Introduction to Programming Using Java – David J. Eck (another free Java-based university text)

Think Data Structures is a free, implementation-first introduction to data structures and algorithms — ArrayList, LinkedList, HashMap, TreeMap, binary search trees, and sorting — taught by building simplified versions of Java’s own Collections Framework classes and applying them to a real Wikipedia crawler and search engine. Browse more Computer Science books for the rest of your semester.

Think Data Structures: Algorithms and Information Retrieval in Java, by Allen B. Downey. Free under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported licence. Access for free at https://greenteapress.com/wp/think-data-structures/