Data Structures Complete Notes — B.Tech CS Sem 3

Data Structures kya hoti hain?

Data Structure ek systematic tarika hai data ko computer memory mein organize, store, aur manage karne ka — taaki efficiently access aur modify kiya ja sake.

Kyon zaroori hai?

• Sahi DS choose karne se program 100x faster ho sakta hai
• All competitive programming aur placements DS pe based hain
• Real systems (databases, OS, browsers) DS pe chal rahe hain

Classification:

• Linear: Array, Linked List, Stack, Queue
• Non-Linear: Tree, Graph
• Hashing: Hash Table, Hash Map

---

1. Arrays

Array ek contiguous memory block hai jisme same type ke elements store hote hain.

int arr[5] = {10, 20, 30, 40, 50};
// arr[0] = 10, arr[4] = 50
// Address of arr[i] = Base + i * sizeof(type)

Operations & Complexity:

| Operation | Time | Space | |---|---|---| | Access arr[i] | O(1) | O(1) | | Search (unsorted) | O(n) | O(1) | | Search (sorted) | O(log n) | O(1) | | Insert at end | O(1) amortized | O(1) | | Insert at middle | O(n) | O(1) | | Delete | O(n) | O(1) |

Types:

• 1D Array: int a[10]
• 2D Array (Matrix): int a[3][4] — Row major order
• Dynamic Array: ArrayList in Java, vector in C++ — doubles capacity when full

Important Patterns:

Two Pointer: i=0, j=n-1 — pair sum, palindrome check
Sliding Window: fixed/variable window — max subarray sum
Prefix Sum: pre[i] = pre[i-1] + a[i] — range queries O(1)
Kadane's Algorithm: max subarray sum O(n)

---

2. Linked List

Node structure: Data + Pointer(s) to next node. Memory not contiguous.

struct Node {
    int data;
    struct Node* next;
};

Types:

| Type | Pointers | Traversal | |---|---|---| | Singly LL | next only | Forward only | | Doubly LL | prev + next | Both directions | | Circular LL | last→first | Loops |

Key Operations:

Insert at head:   new→next = head; head = new;         O(1)
Insert at tail:   traverse to end, tail→next = new;    O(n)
Delete node:      prev→next = curr→next; free(curr);   O(n)
Reverse LL:       3 pointer technique (prev, curr, next) O(n)

Important Interview Problems:

• Detect cycle — Floyd's algorithm (slow/fast pointer)
• Middle of LL — slow/fast pointer
• Merge two sorted LLs
• Nth node from end — two pointer with gap n

---

3. Stack

LIFO — Last In First Out. Think of a stack of plates.

// Operations:
push(x)   // Insert x at top        O(1)
pop()     // Remove from top        O(1)
peek()    // View top element        O(1)
isEmpty() // Check if empty         O(1)

Implementations: Array-based (fixed size) or Linked List (dynamic)

Real Applications:

• Function call stack — recursion management
• Expression evaluation — infix to postfix, balanced parentheses
• Undo/Redo — editors like VS Code
• Browser history — back button
• DFS traversal — iterative version

Classic Problem — Balanced Parentheses:

Input: "{[()]}"  → Valid
Input: "{[(]}"   → Invalid

Algorithm: Push open brackets, pop on close, check match

---

4. Queue

FIFO — First In First Out. Think of a line at a counter.

Enqueue: Add at rear    O(1)
Dequeue: Remove from front  O(1)
Front/Rear access       O(1)

Types:

• Simple Queue — Basic FIFO
• Circular Queue — Efficient memory use, wrap-around using modulo
• Priority Queue — Highest priority served first (Heap-based)
• Deque (Double Ended Queue) — Insert/delete from both ends

Applications:

• CPU and disk scheduling
• BFS (Breadth First Search)
• Printer spooling
• Sliding window maximum (Deque)

---

5. Trees

A Tree is a hierarchical non-linear DS with a root node and subtrees.

Terminology:
- Root: Top node (no parent)
- Leaf: Node with no children
- Height: Longest path root→leaf
- Depth: Distance from root to node
- Degree: Number of children

Binary Tree

Every node has at most 2 children (left, right).

Traversals:

Inorder  (L-Root-R): Gives sorted output for BST
Preorder (Root-L-R): Used to copy/serialize tree
Postorder(L-R-Root): Used to delete tree, evaluate expressions
Level Order (BFS):   Uses queue, level by level

Binary Search Tree (BST)

Property: Left subtree < Root < Right subtree (at every node)

Search:  Compare and go left/right    O(h)
Insert:  Find correct position        O(h)
Delete:  3 cases — leaf, one child, two children (inorder successor)  O(h)

h = O(log n) for balanced BST
h = O(n) for skewed BST

AVL Tree — Self-Balancing BST

Keeps height difference (Balance Factor) = |h_left - h_right| ≤ 1

Rotations on imbalance:

• LL → Right Rotation
• RR → Left Rotation
• LR → Left then Right
• RL → Right then Left

Heap

Complete Binary Tree where parent is always greater (Max-Heap) or smaller (Min-Heap) than children.

Insert:  Add at end, bubble up (heapify up)     O(log n)
Delete:  Remove root, bring last, bubble down   O(log n)
Build heap from array:                          O(n)
Heap Sort:                                      O(n log n)

---

6. Graphs

Graph G = (V, E) — Set of Vertices (nodes) and Edges (connections).

Types:
- Directed / Undirected
- Weighted / Unweighted
- Cyclic / Acyclic
- Connected / Disconnected
- DAG (Directed Acyclic Graph)

Representations:
- Adjacency Matrix: O(V²) space, O(1) edge lookup
- Adjacency List:  O(V+E) space, O(degree) edge lookup

BFS (Breadth First Search):

Use Queue. Visit all neighbors before going deeper.
Time: O(V+E)  |  Applications: Shortest path (unweighted), level order, connected components

DFS (Depth First Search):

Use Stack (or recursion). Go deep before backtracking.
Time: O(V+E)  |  Applications: Topological sort, cycle detection, path finding, SCC

Shortest Path Algorithms:

| Algorithm | Graph Type | Complexity | |---|---|---| | BFS | Unweighted | O(V+E) | | Dijkstra | Weighted, no -ve | O((V+E) log V) | | Bellman-Ford | Weighted, -ve allowed | O(V·E) | | Floyd-Warshall | All pairs | O(V³) |

Minimum Spanning Tree:

• Prim's: Greedy, start from vertex, add min-cost edge — O(E log V)
• Kruskal's: Sort edges by weight, use Union-Find — O(E log E)

---

7. Hashing

Hash Function: Maps a key to a bucket index. Goal: Uniform distribution.

index = key % table_size

Good hash function properties:
- Fast to compute
- Uniform distribution
- Minimize collisions

Collision Handling:

| Method | Idea | Pros | Cons | |---|---|---|---| | Chaining | LL at each bucket | Easy to implement | Extra memory | | Linear Probing | Check next slot | Cache friendly | Clustering | | Quadratic Probing | Check i² slots ahead | Less clustering | May miss slots | | Double Hashing | Use 2nd hash for step | Best distribution | 2 hash functions |

Average case: O(1) for insert/search/delete (with good hash + low load factor)

---

8. Sorting Algorithms

Key Sorting Algorithms:

Bubble Sort:    Compare adjacent, swap if wrong order   O(n²)  O(n) best  Stable
Selection Sort: Find min, put at correct position       O(n²)  O(n²) always  Unstable
Insertion Sort: Build sorted array one by one           O(n²)  O(n) best  Stable
Merge Sort:     Divide & Conquer, merge sorted halves   O(n log n)  always  Stable
Quick Sort:     Pivot, partition, recurse               O(n log n) avg  O(n²) worst  Unstable
Heap Sort:      Build max-heap, extract one by one      O(n log n)  always  Unstable
Counting Sort:  Count frequencies (integers only)       O(n+k)    Stable

When to use what?

• Small array (< 10 elements): Insertion Sort
• General use: Merge Sort (guaranteed O(n log n))
• In-place, average case: Quick Sort
• Finding kth largest: Heap / Quick Select
• Integer range known: Counting Sort / Radix Sort

---

9. Time & Space Complexity Cheat Sheet

| DS | Access | Search | Insert | Delete | Space | |---|---|---|---|---|---| | Array | O(1) | O(n) | O(n) | O(n) | O(n) | | Stack | O(n) | O(n) | O(1) | O(1) | O(n) | | Queue | O(n) | O(n) | O(1) | O(1) | O(n) | | Linked List | O(n) | O(n) | O(1) | O(1) | O(n) | | BST (avg) | O(log n) | O(log n) | O(log n) | O(log n) | O(n) | | Hash Table | N/A | O(1) | O(1) | O(1) | O(n) | | Heap | N/A | O(n) | O(log n) | O(log n) | O(n) |

---

10. Important Interview Questions

Arrays & Strings:

• Two Sum, Three Sum (sorting + two pointer)
• Maximum subarray (Kadane's)
• Rotate array by k positions
• Find duplicate in array (Floyd's cycle)

Linked List:

• Reverse linked list (iterative + recursive)
• Detect and remove cycle
• Merge k sorted lists (heap)
• LRU Cache (HashMap + Doubly LL)

Stack & Queue:

• Valid parentheses
• Min stack (O(1) getMin)
• Next greater element
• Sliding window maximum (Deque)

Trees:

• Height, diameter of binary tree
• Lowest Common Ancestor (LCA)
• Level order / zigzag traversal
• Serialize and deserialize tree

Graphs:

• Number of islands (DFS/BFS)
• Topological sort (DFS + Kahn's BFS)
• Detect cycle (directed + undirected)
• Dijkstra's shortest path