1. Linear Structures 📏
Arrays
Contiguous memory. O(1) access by index. Fixed size (usually). Expensive insertion/deletion O(n).
Linked Lists
Nodes with pointers. Dynamic size. O(1) insert/delete (if at head/tail). O(n) access (sequential).
Stacks (LIFO)
Last In, First Out. Push/Pop. Used for recursion, undo features, expression parsing.
Queues (FIFO)
First In, First Out. Enqueue/Dequeue. Used for printer spooling, task scheduling, BFS.
2. Trees and Heaps 🌳
Hierarchical structures. Essential for database indexing and file systems.
- Binary Tree: Each node has max 2 children.
- BST (Binary Search Tree): Left < Root < Right. Allows O(log n) search/insert/delete if balanced.
- Heap: Complete binary tree. Max-Heap (Parent > Child) or Min-Heap. Foundation of Priority Queues and Heapsort.
- AVL / Red-Black: Self-balancing BSTs. Guarantees O(log n) even in worst case.
3. Graphs 🕸️
The ultimate versatile structure. Nodes (Vertices) connected by Edges.
- Adjacency Matrix: 2D array. Good for dense graphs. O(1) edge check. O(V^2) space.
- Adjacency List: Array of lists. Good for sparse graphs. O(V+E) space.
- BFS (Breadth-First Search): Uses Queue. Shortest path in unweighted graph.
- DFS (Depth-First Search): Uses Stack/Recursion. Path finding, cycle detection.
- Dijkstra: Shortest path in weighted graph (no negative weights).
4. Hashing 🔑
The magic of O(1) lookup. Key $\to$ Hash Function $\to$ Index.
Collision Handling: What if two keys hash to the same index?
1. Chaining: Store a list at that index.
2. Open Addressing: Probe for next available slot (Linear, Quadratic, Double Hashing).