book

Data Structures the Fun Way

by Jeremy Kubica

October 2022

Beginner to intermediate

304 pages

8h 30m

English

No Starch Press

Read now

Unlock full access

Intended AudienceLanguage-AgnosticOn Analogies and Brewing Coffee How to Use This Book
Variables Composite Data StructuresArraysInsertion SortStringsWhy This Matters
The ProblemLinear ScanBinary Search AlgorithmAbsent ValuesImplementing Binary SearchAdapting Binary SearchRuntimeWhy This Matters
The Limitations of ArraysPointers and ReferencesLinked ListsOperations on Linked ListsInserting into a Linked ListDeleting from a Linked ListDoubly Linked ListsArrays and Linked Lists of ItemsWhy This Matters
StacksStacks as ArraysStacks as Linked ListsQueuesQueues as ArraysQueues as Linked ListsThe Importance of OrderDepth-First SearchBreadth-First SearchWhy This Matters

Binary Search Tree StructureSearching Binary Search TreesIterative and Recursive SearchesSearching Trees vs. Searching Sorted ArraysModifying Binary Search TreesAdding NodesRemoving NodesThe Danger of Unbalanced TreesBulk Construction of Binary Search TreesWhy This Matters
Binary Search Trees of StringsStrings in TreesThe Cost of String ComparisonTriesSearching TriesAdding and Removing NodesWhy This Matters
Priority QueuesMax HeapsAdding Elements to a HeapRemoving the Highest-Priority Elements from HeapsStoring Auxiliary InformationUpdating PrioritiesMin HeapsHeapsortWhy This Matters
Introducing Nearest-Neighbor SearchNearest-Neighbor Search with Linear ScanSearching Spatial DataGridsGrid StructureBuilding Grids and Inserting PointsDeleting PointsSearches Over GridsPruning BinsLinear Scan Over BinsIdeal Expanding Search over BinsSimplified Expanding Search The Importance of Grid SizeBeyond Two DimensionsBeyond Spatial DataWhy This Matters
QuadtreesBuilding Uniform QuadtreesAdding PointsRemoving PointsSearching Uniform QuadTreesNearest-Neighbor Search Codek-d Treesk-d Tree StructureTighter Spatial BoundsBuilding k-d Treesk-d Tree OperationsWhy This Matters
Storage and Search with KeysHash TablesCollisionsChainingLinear ProbingHash FunctionsHandling Non-numeric KeysAn Example Use CaseWhy This Matters
Introducing CachesLRU Eviction and CachesBuilding an LRU CacheUpdating an Element’s Recency Other Eviction StrategiesWhy This Matters
B-tree StructureSearching B-treesAdding KeysThe Addition AlgorithmExamples of Adding KeysRemoving KeysFixing Under-full NodesFinding the Minimum Value KeyThe Removal AlgorithmExamples of Removing KeysWhy This Matters
Introducing Bloom FiltersHash Tables of IndicatorsThe Bloom FilterBloom Filter CodeTuning Bloom Filter ParametersBloom Filters vs. Hash TablesWhy This Matters
Randomized vs. Deterministic StructuresIntroducing Skip ListsSearching Skip ListsAdding NodesDeleting NodesRuntimesWhy This Matters
Introducing GraphsRepresenting GraphsSearching Graphs Finding Shortest Paths with Dijkstra’s AlgorithmFinding Minimum Spanning Trees with Prim’s Algorithm Topological Sort with Kahn’s Algorithm Why This Matters
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

Content preview from Data Structures the Fun Way

Acknowledgments

I would like to start by thanking the whole team at No Starch Press who helped make this book a reality. A huge thank-you to Bill Pollock for starting this entire journey by suggesting I do a more technical follow-up to The CS Detective. Thank you to my amazing editors, Abigail Schott-Rosenfield and Liz Chadwick, for their excellent help, guidance, and suggestions. I would also like to thank Carlos Bueno, who originally pointed me to the team at No Starch.

Thank you to Daniel Zingaro for his thorough and insightful technical review. His work was vital in improving both the accuracy and understandability of the material.

A tremendous thanks goes out to all the people who provided valuable comments on earlier versions of this book: ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

Start your free trial

Publisher Resources

ISBN: 9781098156602Errata Page

Data Structures the Fun Way

by Jeremy Kubica

Acknowledgments

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

You might also like

Grokking Data Structures

Grokking Algorithms

Grokking Algorithms, Second Edition

Designing Data-Intensive Applications

Publisher Resources

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,and much more.

You might also like

Grokking Data Structures

Grokking Algorithms

Grokking Algorithms, Second Edition

Designing Data-Intensive Applications

Publisher Resources

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.