This HTML version of Think Data Structures is provided for convenience, but it is not the best format of the book. In particular, some of the symbols are not rendered correctly.

You might prefer to read the PDF version.

Or you can buy this book on Amazon.com.

Think Data Structures: Algorithms and Information Retrieval in Java

Allen B. Downey

Version 1.0.0

Copyright © 2016 Allen B. Downey.

Permission is granted to copy, distribute, and/or modify this work under the terms of the Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License, which is available at https://creativecommons.org/licenses/by-nc-sa/3.0/.

• Preface
  • The philosophy behind the book
  • Prerequisites
  • Working with the code
  • Contributors
• Interfaces
  • Why are there two kinds of List?
  • Interfaces in Java
  • The List interface
  • Exercise 1
• Analysis of Algorithms
  • Selection sort
  • Big O notation
  • Exercise 2
• ArrayList
  • Classifying MyArrayList methods
  • Classifying add
  • Problem Size
  • Linked Data Structures
  • Exercise 3
  • A note on garbage collection
• LinkedList
  • Classifying MyLinkedList methods
  • Comparing MyArrayList and MyLinkedList
  • Profiling
  • Interpreting results
  • Exercise 4
• Doubly-linked list
  • Performance profiling results
  • Profiling LinkedList methods
  • Adding to the end of a LinkedList
  • Doubly-linked list
  • Choosing a Structure
• Tree traversal
  • Search engines
  • Parsing HTML
  • Using jsoup
  • Iterating through the DOM
  • Depth-first search
  • Stacks in Java
  • Iterative DFS
• Getting to Philosophy
  • Getting started
  • Iterables and Iterators
  • WikiFetcher
  • Exercise 5
• Indexer
  • Data structure selection
  • TermCounter
  • Exercise 6
• The Map interface
  • Implementing MyLinearMap
  • Exercise 7
  • Analyzing MyLinearMap
• Hashing
  • Hashing
  • How does hashing work?
  • Hashing and mutation
  • Exercise 8
• HashMap
  • Exercise 9
  • Analyzing MyHashMap
  • The tradeoffs
  • Profiling MyHashMap
  • Fixing MyHashMap
  • UML class diagrams
• TreeMap
  • What’s wrong with hashing?
  • Binary search tree
  • Exercise 10
  • Implementing a TreeMap
• Binary search tree
  • A simple MyTreeMap
  • Searching for values
  • Implementing put
  • In-order traversal
  • The logarithmic methods
  • Self-balancing trees
  • One more exercise
• Persistence
  • Redis
  • Redis clients and servers
  • Making a Redis-backed index
  • Redis data types
  • Exercise 11
  • More suggestions if you want them
  • A few design hints
• Crawling Wikipedia
  • The Redis-backed indexer
  • Analysis of lookup
  • Analysis of indexing
  • Graph traversal
  • Exercise 12
• Boolean search
  • Crawler solution
  • Information retrieval
  • Boolean search
  • Exercise 13
  • Comparable and Comparator
  • Extensions
• Sorting
  • Insertion sort
  • Exercise 14
  • Analysis of merge sort
  • Radix sort
  • Heap sort
  • Bounded heap
  • Space complexity
• Index