Book 12
Data Structures
The shapes programs use to organize data, from lists and stacks to trees and graphs, and the classic ways to search and sort them.
Contents
- 01Adjacency List1An adjacency list is a way of storing a graph in which each node keeps a list of the nodes it connects to, using memory in proportion to its nodes and edges.
- 02B-Tree2A B-tree is a self-balancing search tree whose nodes hold many sorted keys and children, which keeps it shallow so lookups need very few disk or page reads.
- 03Backtracking3Backtracking is a search technique that builds a solution one choice at a time and undoes the latest choice when it hits a dead end, then tries another option.
- 04Balanced Tree4A balanced tree is a tree that keeps its height close to log n by rebalancing after changes, so search, insert, and delete stay O(log n) even in the worst case.
- 05Binary Search5Binary search is an algorithm that finds a value in a sorted list by repeatedly halving the search range, taking O(log n) time instead of checking every item.
- 06Binary Search Tree6A binary search tree is a binary tree in which each node's left subtree holds smaller values and its right subtree larger ones, enabling fast ordered lookups.
- 07Bloom Filter7A Bloom filter is a compact probabilistic data structure that tells you an item is definitely not in a set or probably is, while using very little memory.
- 08Breadth-First Search8Breadth-first search is a graph traversal algorithm that visits nodes in order of their distance from the start, exploring all neighbors before going deeper.
- 09Bubble Sort9Bubble sort is a simple sorting algorithm that keeps swapping out-of-order neighbors, so each pass carries the largest remaining value to the end.
- 10Depth-First Search10Depth-first search is a graph traversal algorithm that follows one path as far as it can go before backtracking to explore the next unvisited branch.
- 11DequeDouble-Ended Queue11A deque is a double-ended queue that lets you add and remove items at both the front and the back in constant time, so it can act as both a stack and a queue.
- 12Dijkstra's Algorithm12Dijkstra's algorithm is a graph algorithm that finds the shortest paths from a starting node to every other node when all edge weights are zero or positive.
- 13Divide and Conquer13Divide and conquer is an algorithm design technique that splits a problem into smaller independent parts, solves each recursively, and combines the results.
- 14Dynamic Programming14Dynamic programming is a technique for solving problems by breaking them into overlapping subproblems and storing each answer so none is solved twice.
- 15Graph15A graph is a data structure made of nodes, called vertices, connected by edges, and is used to model relationships such as roads, friendships, and dependencies.
- 16Greedy Algorithm16A greedy algorithm builds a solution step by step, always taking the choice that looks best right now, without going back to reconsider earlier decisions.
- 17Hash Collision17A hash collision is two different inputs sharing a hash value or bucket, which hash tables must handle and cryptographic hashes must make infeasible to find.
- 18Hash Table18A hash table is a data structure that stores key-value pairs and uses a hash function to find the value for any key in constant time on average.
- 19Heap19A heap is a tree-based data structure that keeps the smallest or largest item at its root, so you can read it in O(1) and remove it in O(log n) time.
- 20Insertion Sort20Insertion sort builds a sorted list one element at a time, putting each new one in its place among those already sorted, like sorting cards in your hand.
- 21Linear Search21Linear search finds a value by checking each element of a list one by one from the start until it finds a match or reaches the end, taking O(n) time.
- 22Linked List22A linked list is a data structure that stores items in separate nodes, where each node holds a value and a reference to the next node in the chain.
- 23LRU CacheLeast Recently Used Cache23An LRU (least recently used) cache holds a fixed number of items and, when full, evicts the one unused the longest, betting that recent data will be reused.
- 24Merge Sort24Merge sort is a divide and conquer sorting algorithm that splits a list in half, sorts each half recursively, and merges the sorted halves in O(n log n) time.
- 25Priority Queue25A priority queue is a collection in which every item has a priority, and the highest-priority item is always removed first, no matter when it was added.
- 26Queue26A queue is a data structure that stores items in first in, first out (FIFO) order, so the item that has waited longest is always the next one removed.
- 27Quicksort27Quicksort is a divide and conquer sorting algorithm that partitions items around a chosen pivot, then sorts the smaller and larger groups the same way.
- 28Set28A Set is a collection that stores each distinct value at most once and can check whether a value is present very quickly, usually in constant time.
- 29Sliding Window29The sliding window technique solves problems on contiguous parts of an array or string by updating a window as it slides instead of recomputing each subarray.
- 30Sorting Algorithm30A sorting algorithm is a step-by-step method for arranging items in a defined order, such as numbers from smallest to largest or names alphabetically.
- 31Stack31A stack is a data structure that stores items in last in, first out (LIFO) order, so the most recently added item is always the first one removed.
- 32Topological Sort32Topological sort is an algorithm that orders the nodes of a directed acyclic graph so that for every edge from A to B, A comes before B in the resulting list.
- 33Tree33A tree is a hierarchical data structure made of nodes connected by edges, with a single root node at the top and child nodes branching out below it.
- 34Trie34A trie is a tree-shaped data structure that stores strings character by character, so all words that share a prefix also share the same path from the root.
- 35Two Pointers35The two pointers technique walks an array or list with two indexes moved by simple rules, turning many problems that seem to need nested loops into one pass.
- 36Union-FindDisjoint Set Union36Union-find, or disjoint set union, is a data structure that tracks which elements share a group and can merge groups or check connectivity almost instantly.