Core Algorithms & Data Structures

Stack

Stores elements in LIFO order (last in, first out); operations push/pop; runtime O(1)

Queue

Stores elements in FIFO order (first in, first out); operations enqueue/dequeue; runtime O(1)

Selection Sort

Repeatedly selects minimum and places it in order; runtime O(N^2) always; not stable

Insertion Sort

Inserts elements into sorted prefix; runtime O(N^2) worst, O(N) best; stable

Merge Sort

Divide array into halves and merge sorted halves; runtime O(N log N) worst; stable, not in-place

Quick Sort

Uses pivot and partitioning; runtime O(N log N) average, O(N^2) worst; in-place

Heap Sort

Uses binary heap and repeatedly removes max; runtime O(N log N) worst; not stable, in-place

Radix Sort

Sorts by digits (non-comparison); runtime O(N) for fixed digit size

Priority Queue (Heap)

Data structure supporting insert and delMax/delMin; implemented with binary heap; operations O(log N), peek O(1)

Binary Search Tree (BST)

Tree where left < root < right; search/insert O(log N) average, O(N) worst

Hash Table

Maps keys to indices using hash function; average O(1), worst O(N)

Trie (Prefix Tree)

Tree storing strings character-by-character; operations O(ℓ), ℓ = string length

Graph

Collection of vertices and edges; used to model networks and relationships

Depth-First Search (DFS)

Graph traversal using stack/recursion; explores deep paths first; runtime O(V + E)

Breadth-First Search (BFS)

Graph traversal using queue; explores level-by-level; runtime O(V + E)

Dijkstra’s Algorithm

Finds shortest paths from a source in weighted graph; uses priority queue; runtime O(E log V)

Kruskal’s Algorithm

MST algorithm that sorts edges and uses union-find; runtime O(E log E)

Prim’s Algorithm

MST algorithm that grows tree from a node using priority queue; runtime O(E log V)