1. Introduction to Data Structures
A data structure is a way of organizing data so that it can be used efficiently.
Why it matters
- Faster search, insert, delete
- Forms the base of algorithms & interviews
- Core subject for BTech CSE (Sem 3/4)
Classification
- Linear: Array, Linked List, Stack, Queue
- Non-linear: Tree, Graph, Heap
- Hash-based: Hash Table / HashMap
2. Arrays
Definition: Contiguous memory block storing same-type elements.
Operations & Complexity
- Access by index → O(1)
- Search (unsorted) → O(n)
- Insert / Delete at end → O(1) amortized
- Insert / Delete at middle → O(n)
When to use
- Need random access
- Size is known or grows rarely
- Cache-friendly sequential data
Exam tip: Mention contiguous memory + O(1) access when comparing with linked lists.
3. Linked Lists
Types: Singly, Doubly, Circular
Singly Linked List node
data | next →
Complexity
- Access i-th node → O(n)
- Insert/Delete at head → O(1)
- Insert/Delete at end → O(n) without tail pointer
Pros: Dynamic size, cheap insert/delete at ends
Cons: No random access, extra pointer memory
Common interview tasks: reverse list, detect cycle (Floyd), merge two sorted lists, find middle (slow-fast pointers).
4. Stack & Queue
Stack (LIFO)
Operations: push, pop, peek — all O(1)
Uses: recursion call stack, undo, balanced parentheses, expression evaluation (infix→postfix)
Queue (FIFO)
Operations: enqueue, dequeue — O(1) with circular array or linked list
Uses: BFS, scheduling, printers, buffers
Variants
- Deque (double-ended)
- Priority Queue (heap-based)
- Circular Queue (avoids wasted space)
5. Trees
Binary Tree: each node has ≤ 2 children
BST: left < root < right
AVL / Red-Black: self-balancing BSTs
Traversals
- Inorder (L-Root-R) → sorted order for BST
- Preorder (Root-L-R) → copy / serialize
- Postorder (L-R-Root) → delete / expression trees
- Level order → BFS with queue
Height & complexity
- Balanced tree ops → O(log n)
- Skewed tree ops → O(n)
Must-know problems: LCA, diameter, max path sum, serialize/deserialize.
6. Graphs
Representations
- Adjacency Matrix → O(V²) space, O(1) edge check
- Adjacency List → O(V+E) space (preferred)
Traversals
- BFS → shortest path in unweighted graph
- DFS → cycle detection, topological sort, components
Algorithms to revise
- Dijkstra (weighted shortest path)
- Kruskal / Prim (MST)
- Topological Sort (DAG)
- Union-Find (disjoint sets)
Complexity of BFS/DFS: O(V + E)
7. Complexity Cheat Sheet
| Structure | Access | Search | Insert | Delete |
|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) |
| Linked List | O(n) | O(n) | O(1)* | O(1)* |
| Stack/Queue | O(n) | O(n) | O(1) | O(1) |
| HashMap | — | O(1) avg | O(1) avg | O(1) avg |
| BST (bal.) | O(log n) | O(log n) | O(log n) | O(log n) |
| Heap | O(1) min/max | O(n) | O(log n) | O(log n) |
*at known position / head