Data structure tricks that make storage click

Stack = LIFO (Last In First Out, like a stack of plates). Queue = FIFO (First In First Out, like a line).

Stack vs Queue — Stack: push to top, pop from top. Function call stacks, undo operations. Queue: enqueue at back, dequeue from front. Print jobs, breadth-first search.

Linked List: O(1) insert at head, O(n) search — no random access

Linked Lists — Each node stores data + pointer to next. No contiguous memory. Fast insert/delete at head. Must traverse to find element. Doubly linked: each node has prev and next pointers.

BST: left < root < right → O(log n) average search

Binary Search Trees — In a BST: left subtree < root < right subtree. O(log n) average for search/insert/delete. O(n) worst case when unbalanced. AVL and Red-Black trees self-balance.

Hash Table: key → hash function → index → O(1) average lookup

Hash Tables — Hash function converts key to array index. O(1) average for insert, delete, lookup. Collision handling: chaining (linked list) or open addressing. Python dict, Java HashMap.

Graph: vertices + edges. BFS (Breadth-First Search) uses queue (level-by-level). DFS (Depth-First Search) uses stack (depth-first).

Graphs and Graph Traversal — Vertices (nodes) connected by edges. BFS (breadth-first search): uses queue, finds shortest path in unweighted graph. DFS (depth-first search): uses stack (or recursion), explores as far as possible before backtracking.

Array: O(1) random access by index. O(n) insert/delete in middle. Fixed size (static) or dynamic.

Arrays — Elements stored in contiguous memory → O(1) random access by index. Insert/delete at end: O(1). Insert/delete in middle: O(n) — must shift elements. Static array: fixed size. Dynamic array (ArrayList, Python list): doubles when full — amortized O(1) append.

Heap: complete binary tree. Max-heap: parent ≥ children. Min-heap: parent ≤ children. O(log n) insert and extract.

Heaps — Complete binary tree stored as array. Max-heap: parent always ≥ children → root is maximum. Min-heap: parent ≤ children → root is minimum. Insert: add at end, bubble up → O(log n). Extract max/min: swap root with last, remove, bubble down → O(log n). Heapsort: O(n log n).

Trie (prefix tree): efficient string storage and retrieval. Each node = one character. Used in autocomplete.

Tries — Each node represents one character. Root → complete words traced down the tree. Search/insert: O(m) where m = string length — independent of number of stored strings. Applications: autocomplete, spell-check, IP routing, DNA sequence matching. More memory than hash table but faster prefix lookups.

AVL (Adelson-Velsky and Landis) tree: self-balancing BST. Balance factor = height(left) - height(right) must be -1, 0, or 1.

Balanced Binary Trees — BST degenerates to O(n) if elements inserted in sorted order (becomes a linked list). AVL tree: automatically rebalances via rotations when balance factor falls outside [-1, 0, 1]. Red-Black tree: less strictly balanced but faster insertions — used in Java TreeMap, C++ std::map.

Adjacency matrix: O(1) edge lookup, O(V²) space. Adjacency list: O(V+E) space, better for sparse graphs.

MatrixO(1) edge lookup, O(V²) space — dense graphs

ListO(V+E) space — sparse graphs, most algorithms

Circular buffer (ring buffer): fixed-size queue using array with wraparound — efficient for streaming data

Circular Buffer — Fixed-size array with head and tail pointers. Enqueue: add at tail, advance tail (mod size). Dequeue: remove at head, advance head. When tail reaches end, wraps to beginning. O(1) enqueue and dequeue. Used in: audio/video streaming buffers, OS I/O buffers, producer-consumer problems.

Set: unordered collection of unique elements. O(1) average for add/remove/contains using hashing.

Sets — Set stores unique values — duplicates ignored. HashSet: O(1) average add/contains/remove, no ordering. TreeSet: O(log n), maintains sorted order. Useful for: removing duplicates from a list, membership testing, finding common elements (intersection), finding differences. Python set(), Java HashSet.