Learn how and when to use the right data structures in any situation, strengthening your computational thinking, problem-solving, and programming skills in the process.
This accessible and entertaining book provides an in-depth introduction to computational thinking through the lens of data structures — a critical component in any programming endeavor. You’ll learn how to work with more than 15 key data structures, from arrays, stacks, and queues, to caches, bloom filters, skip lists, and graphs. You’ll also master linked lists by virtually standing in line at a cafe, hash tables by cataloging the history of the summer Olympics, and QuadTrees by neatly organizing your kitchen cabinets, all while becoming familiar with basic computer science concepts, like recursion and running time analysis.
Author(s): Kubica, Jermy
Series: Early Access
Year: 2022
Language: English
Commentary: Computers, Data Structures
Pages: 298
Tags: Computers, Data Structures
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
