Data Structures Atlas

Comprehensive Reference: Properties, Operations & Complexity.

📝

1. The List ADT

Ordered series: $A_0, A_1, \dots, A_{N-1}$

Properties

  • ArrayList: Growable array. Best for frequent access ($O(1)$). Expensive insert/remove ($O(N)$).
  • LinkedList: Doubly linked nodes. Efficient insert/remove ($O(1)$) if position is known.
  • Circular Linked List: Last node points back to the first node.

Commands

get(index) set(index, val) add(index, val) remove(index) clear() contains(val)

Algorithmic Complexity

Operation ArrayList (Worst) LinkedList (Worst)
get / set$O(1)$$O(N)$
add (front)$O(N)$$O(1)$
add (end)$O(1)$ (Avg)$O(1)$
remove (front)$O(N)$$O(1)$
contains$O(N)$$O(N)$
🥞

2. Stack

LIFO: Last In, First Out

Properties & Applications

Restricted list where insertion/deletion occur only at the top.

Expression Eval (Postfix) Balancing Symbols Recursion Management

Operations

  • Push Insert at top ($O(1)$).
  • Pop Delete from top ($O(1)$).
  • Top/Peek Examine top ($O(1)$).
🚶

3. Queue

FIFO: First In, First Out

Overview

Insertion at Rear, Deletion at Front. Usually implemented with a Circular Array.

Operation Description Complexity
Enqueue Insert at Rear $O(1)$
Dequeue Delete from Front $O(1)$
🌳

4. Binary Search Tree (BST)

Left < Node < Right

Inorder Traversal = Sorted Avg Depth: $O(\log N)$ Worst Depth: $O(N)$
contains(x) findMin/Max insert(x) remove(x)
Operation Average Case Worst Case
Search / Insert / Remove $O(\log N)$ $O(N)$

* Worst case happens when input is sorted (tree becomes a linked list).

⚖️

5. Balanced Search Trees

Guaranteed $O(\log N)$ performance

AVL Tree

Strict balance (diff $\le 1$). Uses rotations.

Splay Tree

Self-adjusting. Accessed nodes move to root.

Red-Black Tree

Color rules ensuring height $\le 2\log(N+1)$.

Treap

BST + Heap (Random priorities).

Tree Type Metric Performance
AVL TreeWorst Case$O(\log N)$
Splay TreeAmortized$O(\log N)$
Red-Black TreeWorst Case$O(\log N)$
TreapExpected$O(\log N)$
🔑

6. Hash Table

Map keys to indices for constant access

Collision Resolution

  • Separate Chaining: Linked lists at each index.
  • Open Addressing: Search next empty (Linear/Quadratic Probing).
  • Cuckoo/Hopscotch: Specialized for $O(1)$ worst-case.
Operation Average Case Worst Case
Insert / Delete / Search $O(1)$ $O(N)$
🏗️

7. Binary Heap

Priority Queue Implementation

Heap-Order Property

Parent is smaller than children (Min-Heap).

Left: 2i
Right: 2i+1
Operation Average Worst
insert$O(1)$$O(\log N)$
deleteMin$O(\log N)$$O(\log N)$
buildHeap$O(N)$$O(N)$
🔗

8. Disjoint Sets

Union-Find Data Structure

Maintains a collection of disjoint sets. Uses Union-by-Rank and Path Compression.

find(x) union(root1, root2)
Complexity: $O(M \alpha(M, N))$
($\alpha$ is effectively constant, nearly linear time)
🕸️

9. Graph Algorithms

$G = (V, E)$

Representations: Adjacency Matrix (Dense) or Adjacency List (Sparse).
Algorithm Purpose Complexity
Topological Sort Ordering in DAG $O(|E| + |V|)$
BFS Shortest Path (Unweighted) $O(|E| + |V|)$
Dijkstra Shortest Path (Weighted) $O(|E| \log |V|)$
Prim / Kruskal Minimum Spanning Tree $O(|E| \log |V|)$
🚀

10. Specialized & Analogy

Advanced Structures & Understanding

Specialized Structures

  • Suffix Array/Tree: Pattern searching. $O(N)$ construction.
  • k-d Tree: Multi-dimensional search.
  • Skip List: Randomized $O(\log N)$ search/insert.
  • Pairing Heap: Practical alternative to Fibonacci heaps.

💡 The Tool Shed Analogy

  • 📦 Array: A shelf with fixed spots. Easy to grab, hard to reorganize.
  • 🔗 Linked List: A chain of tools. Easy to add a link, but must follow the chain to find a tool.
  • 🗂️ Tree: A filing system. Narrow down your search at every folder.
  • ✨ Hash Table: A magic box. Call out a tool's name, and it appears instantly!