Data Structures the Fun Way

Data Structures the Fun Way

by Jeremy Kubica
Released October 2022
Publisher(s): No Starch Press
ISBN: 9781718502604

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book description

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. Through diagrams, pseudocode, and humorous analogies, you’ll learn how the structure of data drives algorithmic operations, gaining insight into not just how to build data structures, but precisely how and when to use them.

This book will give you a strong background in implementing and working with more than 15 key data structures, from stacks, queues, and caches to bloom filters, skip lists, and graphs. Master linked lists by standing in line at a cafe, hash tables by cataloging the history of the summer Olympics, and Quadtrees by neatly organizing your kitchen cabinets. Along with basic computer science concepts like recursion and iteration, you’ll learn:

•The complexity and power of pointers
•The branching logic of tree-based data structures
•How different data structures insert and delete data in memory
•Why mathematical mappings and randomization are useful
•How to make tradeoffs between speed, flexibility, and memory usage

Data Structures the Fun Way shows how to efficiently apply these ideas to real-world problems—a surprising number of which focus on procuring a decent cup of coffee. At any level, fully understanding data structures will teach you core skills that apply across multiple programming languages, taking your career to the next level.

Table of contents

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

Product information

  • Title: Data Structures the Fun Way
  • Author(s): Jeremy Kubica
  • Release date: October 2022
  • Publisher(s): No Starch Press
  • ISBN: 9781718502604