Data Structures the Fun Way: An Amusing Adventure with Coffee-Filled Examples

Brief Contents
Contents in Detail
Acknowledgments
Introduction
	Intended Audience
	Language-Agnostic
	On Analogies and Brewing Coffee
	How to Use This Book
1 Information in Memory
	Variables
	Composite Data Structures
	Arrays
		Insertion Sort
	Strings
	Why This Matters
2 Binary Search
	The Problem
	Linear Scan
	Binary Search Algorithm
		Absent Values
		Implementing Binary Search
	Adapting Binary Search
	Runtime
	Why This Matters
3 Dynamic Data Structures
	The Limitations of Arrays
	Pointers and References
	Linked Lists
	Operations on Linked Lists
		Inserting into a Linked List
		Deleting from a Linked List
	Doubly Linked Lists
	Arrays and Linked Lists of Items
	Why This Matters
4 Stacks and Queues
	Stacks
		Stack as Arrays
		Stack as Linked Lists
	Queues
		Queues as Arrays
		Queues as Linked Lists
	The Importance of Order
		Depth-First Search
		Breadth-First Search
	Why This Matters
5 Binary Search Trees
	Binary Search Tree Structure
	Searching Binary Search Trees
		Iterative and Recursive Searches
		Searching Trees vs. Searching Sorted Arrays
	Modifying Binary Search Trees
		Adding Nodes
		Removing Nodes
	The Danger of Unbalanced Trees
	Bulk Construction of Binary Search Trees
	Why This Matters
6 Tries and Adapting Data Structures
	Binary Search Trees of Strings
		Strings in Trees
		The Cost of String Comparison
	Tries
		Searching Tries
		Adding and Removing Nodes
	Why This Matters
7 Priority Queues and Heaps
	Priority Queues
	Max Heaps
		Adding Elements to a Heap
		Removing the Highest-Priority Elements from Heaps
		Storing Auxiliary Information
	Updating Priorities
	Min Heaps
	Heapsort
	Why This Matters
8 Grids
	Introducing Nearest-Neighbor Search
		Nearest-Neighbor Search with Linear Scan
		Searching Spatial Data
	Grids
		Grid Structure
		Building Grids and Inserting Points
		Deleting Points
	Searches Over Grids
		Pruning Bins
		Linear Scan Over Bins
		Ideal Expanding Search over Bins
		Simplified Expanding Search
	The Importance of Grid Size
	Beyond Two Dimensions
	Beyond Spatial Data
	Why This Matters
9 Spatial Trees
	Quadtrees
		Building Uniform Quadtrees
		Adding Points
		Removing Points
		Searching Uniform QuadTrees
		Nearest-Neighbor Search Code
	k-d Trees
		k-d Tree Structure
		Tighter Spatial Bounds
		Building k-d Trees
		k-d Tree Operations
	Why This Matters
10 Hash Tables
	Storage and Search with Keys
	Hash Tables
		Collisions
		Chaining
		Linear Probing
	Hash Functions
		Handling Non-Numeric Keys
		An Example Use Case
	Why This Matters
11 Caches
	Introducing Caches
	LRU Eviction and Caches
		Building an LRU Cache
		Updating an Element’s Recency
	Other Eviction Strategies
	Why This Matters
12 B-trees
	B-Tree Structure
	Searching B-trees
	Adding Keys
		The Addition Algorithm
		Examples of Adding Keys
	Removing Keys
		Fixing Under-full Nodes
		Finding the Minimum Value Key
		The Removal Algorithm
		Examples of Removing Keys
	Why This Matters
13 Bloom Filters
	Introducing Bloom Filters
		Hash Tables of Indicators
		The Bloom Filter
		Bloom Filter Code
	Tuning Bloom Filter Parameters
	Bloom Filters vs. Hash Tables
	Why This Matters
14 Skip Lists
	Randomized vs. Deterministic Structures
	Introducing Skip Lists
		Searching Skip Lists
		Adding Nodes
		Deleting Nodes
	Runtimes
	Why This Matters
15 Graphs
	Introducing Graphs
		Representing Graphs
		Searching Graphs
	Finding Shortest Paths with Dijkstra’s Algorithm
	Finding Minimum Spanning Trees with Prim’s Algorithm
	Topological Sort with Kahn’s Algorithm
	Why This Matters
Conclusion
	What Is the Impact of the Data’s Structure?
	Do We Need Dynamic Data Structures?
	What Is the Amortized Cost?
	How Can We Adapt Data Structures to a Specific Problem?
	What Are the Memory vs. Runtime Tradeoffs?
	How Can We Tune Our Data Structure?
	How Does Randomization Impact Expected Behavior?
	Why This Matters