--- title: "Data Structures and Algorithms Guide" description: "Common data structures and the problems they solve." url: "https://briansunter.com/data-structures-algorithms-guide" --- NOV 26, 2022 · 3 MIN READ # Data Structures and Algorithms Guide Common data structures and the problems they solve. ## Array ### Concepts - 2D arrays - N-dimensional arrays - Jagged arrays ### Problems - Two sum - Search insert position - Kth largest element in array ## Linked List ### Operations - Insert - Delete - Find - Reverse ### Problems - Counting nodes - Finding middle element - Merging lists - Kth to last node - Detecting cycles ## Stack LIFO (Last In, First Out) ### Problems Towers of Hanoi ## Queue FIFO (First In, First Out) ## Tree ### Concepts - Root - Edge - Leaf - Depth - Height ### Binary Tree #### Binary Search Trees ##### Problems - Level order traversal - Construct tree from traversal ### Balanced Trees - AVL Tree - B-tree - Red-Black Tree ### Operations - Insertion - Deletion - Traversal (pre-order, in-order, post-order) - Search (BFS, DFS) - Find min/max - Find successor/predecessor ## Hash Table ### Implementations - Array - Linked List - Binary Tree ### Operations - Get - Put - Delete ### Concepts - Hash function - Linear probing - Quadratic probing - Collision resolution - Load factor ### Problems - LRU cache ## Heap ### Concepts - Complete binary tree - Priority queue - Array representation - Min heap - Max heap ### Priority Queue Operations - Enqueue - Dequeue - Peek - Compare function ### Heap Operations - Build - Insert - Get - Delete - Heapify - Heap sort (in-place) ### Problems - Merge k sorted lists - Kth largest element in array - The skyline problem ## Trie - Compressed trie - Suffix trie ## Advanced Data Structures - Skip list - Suffix tree - Suffix array - Bloom filter - Segment tree - Fenwick tree (Binary Indexed Tree) ## Sorting ### Algorithms - Bubble sort - Insertion sort - Selection sort - Merge sort - Quick sort - Heap sort - Radix sort - Counting sort ### Concepts - Sort stability - In-place sorting - Comparison vs non-comparison sorts ### Problems - Dutch national flag - Merge two sorted arrays ## Graph ### Concepts - Graph theory - Directed vs undirected graphs - Weighted vs unweighted graphs - Pathfinding - Connectivity - Shortest path - Minimum spanning tree - Cycles - Disjoint graphs ### Traversal - Breadth First Search (BFS) - Depth First Search (DFS) ### Algorithms - Bipartite graph detection - Topological sort - Dijkstra’s algorithm - Bellman-Ford algorithm - Floyd-Warshall algorithm - Prim’s algorithm - Kruskal’s algorithm ### Representations - Adjacency list - Adjacency matrix - Edge list ## Recursion ### Concepts - Base case - Recursive case - Inductive step - Tail recursion - Memoization - Backtracking ### Problems - Recursive factorial - Recursive exponent - Fibonacci numbers - Pascal’s triangle - Towers of Hanoi - Subsets of size n - Letter case permutations - Subsets - Permutations - Subset sum - Generate parentheses - N-Queens - Subarray sum equals k - Valid parentheses ## String Algorithms ### Concepts - String matching - Pattern matching - String search - Data compression - Edit distance - Substring search - String similarity measures ### Algorithms - Rabin-Karp - KMP (Knuth-Morris-Pratt) - Boyer-Moore ### Problems - First non-repeating character - Anagram detection - Palindrome check - Character frequency counting - Reverse string ## Dynamic Programming ### Concepts - Optimal substructure - Overlapping subproblems - Memoization (top-down) - Tabulation (bottom-up) ### Problems - 0/1 Knapsack - Longest common subsequence - Subset sum - Minimum edit distance - Minimum number of coins - Longest increasing subsequence - Longest palindromic subsequence - Text justification ## Computational Geometry ## Network Flow Algorithms ### Concepts - Network flow - Maximum flow - Minimum cut ### Algorithms - Ford-Fulkerson - Edmonds-Karp - Dinic’s algorithm - König’s theorem ## NP-Complete ### Approximation Algorithms - Simulated annealing - Tabu search - Genetic algorithms - Ant colony optimization - Particle swarm optimization - Cross-entropy method ### Examples of NP-Complete Problems - Set cover - Knapsack - Bin packing - Vertex cover - Hamiltonian path - Traveling salesman - Boolean satisfiability (SAT) - Partition problem - Clique problem - Graph coloring ## Search ### Basic Search - Linear search - Binary search ### Graph Search - Depth-first search (DFS) - Breadth-first search (BFS) - Best-first search - A\* search ### Shortest Path - Dijkstra’s algorithm - Bellman-Ford algorithm - Floyd-Warshall algorithm - Johnson’s algorithm ## Algorithm Design - Greedy algorithms - Dynamic programming - Divide and conquer - Decrease and conquer - Transform and conquer - Randomized algorithms - Brute force ## Algorithm Analysis ### Time Complexity - Big-O notation (upper bound) - Omega notation (lower bound) - Theta notation (tight bound) - Little-o notation ### Space Complexity - Auxiliary space - In-place algorithms ### Mathematical Series - Arithmetic series - Geometric series - Harmonic series - Arithmetic-geometric series ## Subscribe to newsletter I send occasional emails about new blog posts, side projects, and things I'm learning. By subscribing, you agree to our [Privacy Policy](/privacy). [Older Newsletter Issue 9 ](/newsletter/issue-9)[Newer AI Learning Resources](/ai-learning-resources) ## Related - [Binary Search Algorithm Jan 5, 2023](/binary-search) - [Heap, Heap Sort, Heapify, and Priority Queues Jan 5, 2023](/heap) - [Recurrence Relation and Master's Theorem for Dividing Functions Jan 5, 2023](/recurrence-relation-masters-theorem-dividing) ### Share this article