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.

Representations:

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.

Key Algorithms:

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).

Data Structures