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

11 Caches

This chapter introduces caches, data structures that seek to alleviate high data access costs by storing some data closer to the computation. As we have seen throughout the previous chapters, the cost of data access is a critical factor in the efficiency of our algorithms. This is important not just to how we organize the data in storage but also to the type of storage we use. We say data is local when it is stored closer to the processor and thus quickly available for processing. If we copy some of the data from more expensive, distant locations to local storage, we can read the data significantly faster.

For example, we might ...