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

About the Author

Jeremy Kubica is an engineering director specializing in artificial intelligence and machine learning. He received a PhD in robotics from Carnegie Mellon University and a BS in computer science from Cornell University. He spent his graduate school years creating algorithms to detect killer asteroids (actually stopping them was, of course, left as “future work”). He is the author of multiple books designed to introduce people to computer science, including Computational Fairy Tales and The CS Detective (No Starch Press, 2016), as well as the Computational Fairy Tales blog.

About the Technical Reviewer

Dr. Daniel Zingaro is an associate teaching professor of computer science and award-winning teacher at the University of Toronto. ...

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

About the Author

About the Technical Reviewer

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

About the Technical Reviewer

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.