Data Structure (IT-303) - Unit 5 Short Notes

UNIT 5: Data Structures

I. Fundamentals of Data Structures & Algorithm Analysis

Abstract Data Types (ADT)

An ADT is a mathematical model for data types defined by its behavior (semantics) from the user's perspective, specifying possible values and operations.
Examples:

• Stack ADT: LIFO (Last-In-First-Out) operations: push, pop, peek.

• Queue ADT: FIFO (First-In-First-Out) operations: enqueue, dequeue.

• List ADT: Ordered collection with insert, delete, search, traverse.

Asymptotic Notations

Used to describe limiting behavior of functions:

• Big-O (O): Upper bound. $$\displaystyle f(n) = O(g(n)) $$ if $$\displaystyle \exists c>0, n_0 $$ such that $0 \le f(n) \le c \cdot g(n)$ for all $$\displaystyle n \ge n_0 $$.

  Example: $$\displaystyle 3n^2 + 2n + 1 = O(n^2) $$.

• Omega (Ω): Lower bound. $$\displaystyle f(n) = \Omega(g(n)) $$ if $$\displaystyle \exists c>0, n_0 $$ such that $0 \le c \cdot g(n) \le f(n)$ for all $$\displaystyle n \ge n_0 $$.

• Theta (Θ): Tight bound. $$\displaystyle f(n) = \Theta(g(n)) $$ if $$\displaystyle f(n) = O(g(n)) $$ and $$\displaystyle f(n) = \Omega(g(n)) $$.

  Example: $$\displaystyle 3n^2 + 2n + 1 = \Theta(n^2) $$.

Algorithm Characteristics

1. Input: Zero or more externally supplied quantities.

2. Output: At least one produced quantity.

3. Definiteness: Each step precisely defined.

4. Finiteness: Terminates after finite steps.

5. Effectiveness: Each step is basic and feasible.

Efficiency Analysis

• Time Complexity: Number of primitive operations as function of input size $n$. Measured using asymptotic notations.

• Space Complexity: Amount of memory used as function of $n$, including input space and auxiliary space.

Recurrence Relations

Solving using Master Theorem: For $$\displaystyle T(n) = aT(n/b) + f(n) $$, where $$\displaystyle a \ge 1, b > 1 $$:

1. If $$\displaystyle f(n) = O(n^{\log_b a - \epsilon}) $$, then $$\displaystyle T(n) = \Theta(n^{\log_b a}) $$.

2. If $$\displaystyle f(n) = \Theta(n^{\log_b a}) $$, then $$\displaystyle T(n) = \Theta(n^{\log_b a} \log n) $$.

3. If $$\displaystyle f(n) = \Omega(n^{\log_b a + \epsilon}) $$ and regularity condition holds, then $$\displaystyle T(n) = \Theta(f(n)) $$.

Example: $$\displaystyle T(n) = 2T(n/2) + n \log n $$. Here $$\displaystyle a=2, b=2, \log_b a = 1 $$, $$\displaystyle f(n)=n \log n = \Theta(n^{\log_b a} \log n) $$ (case 2 with $$\displaystyle k=1 $$).

\boxed{T(n) = \Theta(n \log^2 n)}.

II. Linear Data Structures

A. Arrays

Memory Layout

• Row-major: Elements stored row by row. Address of $A[i][j]$: $$\displaystyle Addr(A[i][j]) = Base + [(i \times \text{numCols}) + j] \times \text{size} $$.

• Column-major: Elements stored column by column. Address: $$\displaystyle Addr(A[i][j]) = Base + [(j \times \text{numRows}) + i] \times \text{size} $$.

Sparse Matrices

Matrix with mostly zero elements. Representations:

• Triplet (Array-based): Store only non-zero elements as $(row, col, value)$.

• Upper/Lower Triangular: Store only elements on/below (or above) diagonal.

  Address formula for lower triangular in row-major: $$\displaystyle Addr(i,j) = \frac{i(i-1)}{2} + j $$ for $j \le i$.

Array Issues

• Overflow: Insertion when array full.

• Underflow: Deletion when array empty.

• Compaction: Shifting elements to eliminate gaps after deletions.

B. Linked Lists

Types

1. Singly Linked List: Node has data and next.

2. Doubly Linked List: Node has data, prev, next.

3. Circular Linked List: Last node points to first.

Operations & Time Complexity

Special Cases

• Finding Merging Point:

  Algorithm:

  1. Traverse both lists to get lengths $m$ and $n$.

  2. Advance longer list by $|m-n|$ nodes.

  3. Traverse both together until nodes match.

  Time: $O(m+n)$, Space: $O(1)$.

• Reversing:

  Iterative: Use three pointers (prev, curr, next).

  Time: $O(n)$, Space: $O(1)$.

Applications

• Polynomial Representation: Each node stores coefficient and exponent.

• Polynomial Addition: Merge two sorted lists by exponent. Time: $O(m+n)$.

[!TIP]

Drawbacks of singly linked list: Cannot traverse backward, deletion of a node requires previous node's address.

C. Stacks

Stack ADT & Array Implementation

Array-based stack with top index.

• Push: If top == size-1, overflow; else arr[++top] = x.

• Pop: If top == -1, underflow; else return arr[top--].

• Peek: Return arr[top].

Applications

1. Infix to Postfix Conversion:

   Algorithm:

   • Scan infix left to right.

   • If operand, output.

   • If '(', push.

   • If ')', pop and output until '('.

   • If operator, pop operators with higher/equal precedence and output, then push current.

   • Finally, pop all.

   Example: $a+b*c \to abc*+$.

2. Postfix Evaluation:

   Algorithm:

   • Scan postfix.

   • If operand, push.

   • If operator, pop two operands, apply operator, push result.

   Example: $284-5*+77/+$ → stack steps: push 2,8,4; pop 4,8 → $$\displaystyle 8-4=4 $$; push 4; push 5; pop 5,4 → $$\displaystyle 4*5=20 $$; push 20; pop 20,2 → $$\displaystyle 2+20=22 $$; push 22; push 7,7; pop 7,7 → $$\displaystyle 7/7=1 $$; push 1; pop 1,22 → $$\displaystyle 22+1=23 $$; push 23; pop 23,6 → $6/23≈0.26$; push 0.26; pop 0.26,? → error? Actually expression ends with /? Let's correct: Expression is 2 8 4 - 5 * + 7 7 / + 6 / 7 +. After 22+1=23, push 23; then 6/23? Wait, after + we have 23, then 6 push, then / pop 6 and 23 → $6/23≈0.26$, push 0.26; then 7 push, then + pop 7 and 0.26 → $$\displaystyle 7+0.26=7.26 $$. Result: 7.26.

3. Balanced Parentheses:

   Algorithm:

   • Scan expression.

   • If '(', push.

   • If ')', if stack empty or top not '(' → unbalanced; else pop.

   • After scan, if stack empty → balanced.

4. Recursion Simulation: Stack stores return addresses and local variables.

5. Josephus Problem:

   $n$ people in circle, count $k$, eliminate $k$-th, repeat.

   Simulation: Enqueue 1..n, dequeue $k-1$ and enqueue back, dequeue $k$-th (eliminate), repeat until one left.

[!TIP]

Stack is recursive because each function call creates a new activation record on the stack.

D. Queues

Queue ADT & Array Implementation

Array with front and rear.

• Enqueue: If (rear+1)%size == front, overflow; else arr[rear] = x, rear = (rear+1)%size.

• Dequeue: If front == rear, underflow; else x = arr[front], front = (front+1)%size.

Circular Queue

Wraps around array to avoid wasted space.

• Full condition: (rear+1)%size == front.

• Empty condition: front == rear.

Advantage: Better space utilization than linear queue.

Deque (Double-ended Queue)

Insert/delete at both ends. Types:

• Input-restricted: Insert at one end only.

• Output-restricted: Delete at one end only.

Priority Queue

Elements with priorities. Higher priority dequeued first.

Implementation: Heap (min-heap or max-heap).

Operations:

• Insert: Add at end, heapify up.

• Delete Max/Min: Replace root with last element, heapify down.

Limitations of Simple Queue

After several dequeues, front moves to end, wasting space at beginning. Circular queue overcomes this.

E. Comparison: Array vs Linked List

III. Trees

A. Binary Trees

Terminology

• Root: Top node.

• Leaf: Node with no children.

• Height: Longest path from root to leaf (edges).

• Depth: Path length from root to node.

• Level: Depth+1.

• Order: Number of children.

• Degree: Number of children.

Properties

Max nodes in binary tree of height $h$: $$\displaystyle 2^{h+1} - 1 $$.

Proof: By induction. Level $i$ has $$\displaystyle 2^i $$ nodes, sum from $$\displaystyle i=0 $$ to $h$: $$\displaystyle \sum_{i=0}^{h} 2^i = 2^{h+1}-1 $$.

Traversals

• In-order (LNR): Left, Root, Right → gives sorted order in BST.

• Pre-order (NLR): Root, Left, Right.

• Post-order (LRN): Left, Right, Root.

• Level-order (BFS): Use queue.

Construction from Traversals

Given Inorder and Postorder:

1. Last element in postorder is root.

2. Find root in inorder → left/right subtrees.

3. Recurse on left/right inorder and corresponding postorder segments.
   Example: Inorder: D G B A H E I C F, Postorder: G D B H I E F C A.

Root = A. Left inorder: D G B, right: H E I C F. Left postorder: G D B, right: H I E F C. Recurse.

B. Binary Search Trees (BST)

Properties

Left subtree keys < root key, right subtree keys > root key. No duplicates typically.

Operations

• Search: Recursive/iterative comparison. Time: $O(h)$, worst $O(n)$ (skewed).

• Insertion:

  
  Node* insert(Node* root, int key) {
  
      if (!root) return newNode(key);
  
      if (key < root->data) root->left = insert(root->left, key);
  
      else root->right = insert(root->right, key);
  
      return root;
  
  }
  
  

• Deletion (three cases):

  1. Leaf: Simply remove.

  2. One child: Replace node with child.

  3. Two children: Find inorder successor (min in right subtree), copy its value, delete successor (which is leaf or one child).

  Example: Delete 10 from BST: if 10 has two children, find successor (min in right subtree), say 11, replace 10 with 11, then delete 11 (which is leaf).

Construction from Sequence

Insert keys one by one in given order.
Example: 45,26,10,60,70,30,40 → insert sequentially.

C. Balanced Binary Search Trees

1. AVL Trees

Balance Factor (BF) = height(left) - height(right). Must be -1, 0, or +1.

Rotations (single/double):

• LL (Left-Left): Right rotate at unbalanced node.

• RR (Right-Right): Left rotate.

• LR (Left-Right): Left rotate on left child, then right rotate on node.

• RL (Right-Left): Right rotate on right child, then left rotate on node.

Insertion with Rebalancing

1. Insert as in BST.

2. Update heights and BF from bottom-up.

3. If BF becomes ±2, perform appropriate rotation.
   Example: Insert 30 into AVL with root 20 (BF=0), left 10, right 40. After insert 30 at right of 20? Actually 30 < 40, so right child of 20 becomes 40 with left 30. BF(20)= left height(1) - right height(2) = -1? Wait: left subtree (10) height=0? Actually height of leaf is 0? Standard: height of leaf = 0, empty = -1. So after insert: root 20, left 10 (height 0), right 40 with left 30 (height 1). BF(20)=0-1=-1, balanced. But if insert 50? Then 40's right 50, BF(40)=0-1=-1, BF(20)=0-2=-2 → RR rotation on 20? Actually unbalanced at 20, right-heavy, and right child 40 is also right-heavy? 40's right is 50, so RR case. Left rotate 20: 40 becomes root, 20 left child, 50 right child of 40. Then update heights.

Deletion with Rebalancing

Similar to insertion: after deletion, update heights and BF, rebalance if needed. May require multiple rotations up the tree.

2. Red-Black Trees

Properties

1. Every node is red or black.

2. Root is black.

3. All leaves (NIL) are black.

4. Red node's children are black (no two consecutive reds).

5. Every path from node to descendant leaves has same black height (number of black nodes).

Insertion/Deletion

• Insert: Insert as red, then fix violations by recoloring and rotations.

• Delete: Complex, may require up to 3 rotations.
  Overview: If deleted node is red, no violation. If black, may violate black height → fix by moving extra black up until root or restructure.

D. Expression Trees

Construction

From postfix: Use stack. For each token:

• If operand, create node and push.

• If operator, pop two nodes (right then left), make them children of new operator node, push operator.
  Example: Postfix ab+c* → push a, push b, see +: pop b, a, create + with children a,b, push +; see c: push c; see *: pop c, pop +, create * with children + and c, push *. Root is *.

Traversals

• In-order: Left, Root, Right → gives infix (need parentheses for correct order).

• Pre-order: Root, Left, Right → prefix.

• Post-order: Left, Right, Root → postfix.

Evaluation

Recursive:

• If leaf, return value.

• Else compute left and right subtrees, apply operator at root.

E. Heaps

Properties

• Min-heap: Parent ≤ children.

• Max-heap: Parent ≥ children.

Complete binary tree (all levels filled except last, left-aligned).

Array Representation

Index from 1:

• Parent(i) = floor(i/2)

• Left(i) = 2i

• Right(i) = 2i+1

Operations

• Insert: Add at end, then "heapify up" (swap with parent while violates heap property). Time: $O(\log n)$.

• Extract Min/Max: Remove root, replace with last element, then "heapify down" (swap with smaller/larger child). Time: $O(\log n)$.

• Heapify: Build heap from array: start from last non-leaf down to root, heapify down. Time: $O(n)$.

Heap Sort

1. Build max-heap.

2. Repeatedly extract max (swap root with last element, reduce heap size, heapify root).

Time: $O(n \log n)$, in-place but not stable.

IV. Graphs

A. Graph Representations

Conversion:

• Matrix to List: For each row $i$, for each column $j$ with matrix[i][j]=1, add $j$ to $i$'s list.

• List to Matrix: Initialize $V \times V$ zero matrix, for each $i$ and neighbor $j$ in list, set matrix[i][j]=1.

B. Graph Traversal

Breadth-First Search (BFS)

Algorithm:

1. Start from source, mark visited, enqueue.

2. While queue not empty: dequeue $u$, for each unvisited neighbor $v$, mark visited, enqueue $v$.

Uses queue.
Example: Graph with edges: a-b, a-c, b-d, c-e. BFS from a: queue: [a] → dequeue a, enqueue b,c → [b,c] → dequeue b, enqueue d → [c,d] → dequeue c, enqueue e → [d,e] → order: a,b,c,d,e.

Depth-First Search (DFS)

Algorithm (recursive):

DFS(u) {

    visited[u]=true;

    for each neighbor v of u:

        if !visited[v]: DFS(v);

}

Or iterative with stack.
Example: Same graph, DFS from a: push a → pop a, push c,b → pop b, push d → pop d → pop c, push e → pop e → order: a,b,d,c,e (depends on neighbor order).

Graph vs Tree Traversal

• Graph may have cycles → must track visited nodes.

• Tree has no cycles, traversal visits each node once.

• Graph may be disconnected → need outer loop for all vertices.

DFS Traversal Sequences Validation

Given adjacency list and stack contents, can validate if sequence is possible DFS. Push neighbors in reverse order if using stack.

C. Minimum Spanning Tree (MST)

Spanning Tree: Subgraph that is tree and connects all vertices.
MST: Spanning tree with minimum total edge weight.

Prim's Algorithm

1. Start with arbitrary vertex.

2. Grow tree by adding minimum weight edge connecting tree to outside vertex.

3. Use priority queue (min-heap) keyed by edge weight.

Time: $O(E \log V)$ with binary heap.
Example: Graph with vertices a,b,c,d and edges: a-b(1), a-c(3), b-c(1), c-d(1). Start a: add b(1). Tree {a,b}. Edges: a-c(3), b-c(1), c-d(1). Min is b-c(1) → add c. Tree {a,b,c}. Edges: a-c(3), c-d(1). Add c-d(1). MST edges: a-b, b-c, c-d total weight=3.

Kruskal's Algorithm

1. Sort all edges by weight.

2. Initialize each vertex as separate set (Union-Find).

3. Process edges in order: if endpoints in different sets, add edge and union sets.

Time: $O(E \log E)$ for sorting, Union-Find nearly $O(E \alpha(V))$.
Example: Same graph. Sorted edges: a-b(1), b-c(1), c-d(1), a-c(3). Add a-b (union a,b). Add b-c (union b,c → now a,b,c together). Add c-d (union c,d). All vertices connected, stop. MST same as Prim's.

Comparison: Prim's vs Kruskal's

D. Shortest Path

Dijkstra's Algorithm (Single-source, non-negative weights)

1. Initialize distance to source = 0, others = ∞.

2. Set of visited vertices $S$ initially empty.

3. While unvisited vertices exist:

   • Pick vertex $u$ with min distance (use min-heap).

   • Add $u$ to $S$.

   • For each neighbor $v$ of $u$: if dist[u] + w(u,v) < dist[v], update dist[v].

Time: $O((V+E) \log V)$ with binary heap.
Example: Graph: a-b(4), a-c(1), c-b(2), b-d(1). From a: dist[a]=0. Visit a: update b=4, c=1. Pick c (min): update b=min(4, 1+2=3)=3. Pick b: update d=3+1=4. Pick d. Distances: a=0, b=3, c=1, d=4.

E. Other Graph Algorithms

Counting Connected Components

Algorithm:

1. Initialize visited[V]=false, count=0.

2. For each vertex $v$: if not visited, do DFS/BFS from $v$, increment count.

Time: $O(V+E)$.

V. Sorting Algorithms

A. Comparison Sorts

1. Insertion Sort

Algorithm (in-place):

for i=1 to n-1:

    key = arr[i]

    j = i-1

    while j>=0 and arr[j] > key:

        arr[j+1] = arr[j]

        j--

    arr[j+1] = key

Example: [5,2,4,6,1,3] → after i=1: [2,5,4,6,1,3]; i=2: [2,4,5,6,1,3]; etc.

Time Complexity

• Best: Already sorted → $O(n)$.

• Average: $$\displaystyle O(n^2) $$.

• Worst: Reverse sorted → $$\displaystyle O(n^2) $$.
  Space: $O(1)$ (in-place).

2. Selection Sort

Algorithm:

for i=0 to n-2:

    min = i

    for j=i+1 to n-1:

        if arr[j] < arr[min]: min=j

    swap(arr[i], arr[min])

Example: [5,2,4,6,1,3] → i=0: min=4 (value 1), swap → [1,2,4,6,5,3]; i=1: min=1 (value 2), no swap; i=2: min=5 (value 3), swap → [1,2,3,6,5,4]; etc.

Time Complexity Derivation

Comparisons: $$\displaystyle \sum_{i=0}^{n-2} (n-i-1) = \frac{(n-1)n}{2} = O(n^2) $$.

Swaps: $O(n)$.

Overall: $$\displaystyle O(n^2) $$ in all cases. Space: $O(1)$.

3. Merge Sort

Divide and Conquer:

1. Divide array into two halves.

2. Recursively sort halves.

3. Merge two sorted halves.

Recursive Pseudocode:

mergeSort(arr, l, r):

    if l < r:

        m = (l+r)/2

        mergeSort(arr, l, m)

        mergeSort(arr, m+1, r)

        merge(arr, l, m, r)

Merge: Use temporary array, compare elements from two halves, copy smaller.

Iterative Approach: Bottom-up, merge subarrays of size 1, then 2, etc.

Time Complexity: $O(n \log n)$ in best, average, worst (always divides and merges).
Space Complexity: $O(n)$ for temporary array (not in-place).

4. Quick Sort

Algorithm (Lomuto partition, pivot = last element):

quickSort(arr, low, high):

    if low < high:

        pi = partition(arr, low, high)

        quickSort(arr, low, pi-1)

        quickSort(arr, pi+1, high)

partition(arr, low, high):

    pivot = arr[high]

    i = low-1

    for j=low to high-1:

        if arr[j] <= pivot:

            i++

            swap(arr[i], arr[j])

    swap(arr[i+1], arr[high])

    return i+1

Example: [5,2,4,6,1,3], pivot=3. i starts -1. j=0:5>3 skip. j=1:2≤3 → i=0, swap arr[0] and arr[1] → [2,5,4,6,1,3]. j=2:4>3 skip. j=3:6>3 skip. j=4:1≤3 → i=1, swap arr[1] and arr[4] → [2,1,4,6,5,3]. End, swap arr[i+1=2] with pivot → [2,1,3,6,5,4]. Pivot at index 2.

Time Complexity

• Best/Average: Pivot divides evenly → $O(n \log n)$.

• Worst: Pivot smallest/largest each time (sorted/reverse) → $$\displaystyle O(n^2) $$.
  Space: $O(\log n)$ average (recursion stack), $O(n)$ worst.

Comparison with Merge Sort

• Quick sort: In-place (Lomuto), but worst $$\displaystyle O(n^2) $$.

• Merge sort: Not in-place, stable, always $O(n \log n)$.

B. Heap Sort

See III.E. Time: $O(n \log n)$, in-place but not stable.

C. Internal vs External Sorting

• Internal Sorting: All data in main memory (e.g., quick, merge, heap).

• External Sorting: Data too large for memory, uses disk (e.g., external merge sort with multi-way merge).

VI. Searching Algorithms

A. Linear Search

Sequential comparison. Time: $O(n)$ worst.

B. Binary Search

Precondition: Sorted array.
Procedure:

1. low=0, high=n-1.

2. While low <= high:

   mid = (low+high)/2.

   If arr[mid] == key, return mid.

   Else if key < arr[mid], high = mid-1.

   Else low = mid+1.

3. Not found.
   Time: $O(\log n)$.
   Applications: Searching in sorted arrays, debugging (binary search on buggy code), etc.

C. Fibonacci Search

Uses Fibonacci numbers to divide array.

• Compute smallest Fibonacci number $\ge n$.

• Use offset to index: mid = min(offset + fibM2, n-1).

• Compare, adjust Fibonacci numbers and offset.
  Comparison: Similar $O(\log n)$, but fewer comparisons on average? Actually binary search is generally better, but Fibonacci search useful when uniform cost assumption fails (e.g., magnetic tape).
  Example: Array [10,20,30,40,50,60,70], n=7. Fib: 5,8,13 → fibM2=5, fibM1=8. offset=0, mid=min(0+5,6)=5 → arr[5]=60. If key=40 <60, set fibM=fibM2-fibM1? Actually: fibM = fibM1, fibM1=fibM2, fibM2=fibM-fibM1. Then offset remains? Detailed steps omitted for brevity.

VII. Hashing & Advanced Structures

A. Hashing

Hash Functions

• Division Method: $$\displaystyle h(k) = k \mod m $$ (m prime not near power of 2).

• Mid-square: Square k, extract middle digits.

• Folding: Shift folding or boundary folding.

Collision

When two keys hash to same slot.
Impact: Degrades performance from $O(1)$ to $O(n)$ per operation if not resolved.

Collision Resolution

1. Separate Chaining: Each slot points to linked list of entries.

   Example with key mod 7: Insert 32,50,700,140,76,85,46,92,70,73,101.

   Hash values: 32%7=4, 50%7=1, 700%7=0, 140%7=0 (collision with 700 → chain), 76%7=6, 85%7=1 (collision with 50), 46%7=4 (collision with 32), 92%7=1 (collision), 70%7=0 (collision), 73%7=3, 101%7=3 (collision).

   Table:

   0: 700 → 140 → 70

   1: 50 → 85 → 92

   2:

   3: 73 → 101

   4: 32 → 46

   5:

   6: 76

2. Open Addressing: All entries in table itself. Probe sequences:

   • Linear Probing: $$\displaystyle h(k,i) = (h'(k) + i) \mod m $$. Suffers from primary clustering.

   • Quadratic Probing: $$\displaystyle h(k,i) = (h'(k) + c_1 i + c_2 i^2) \mod m $$. Reduces clustering.

   • Double Hashing: $$\displaystyle h(k,i) = (h_1(k) + i \cdot h_2(k)) \mod m $$. $$\displaystyle h_2(k) $$ must be relatively prime to $m$.

Operations

• Insert: Compute hash, if slot occupied (in separate chaining, add to list; in open addressing, probe until empty).

• Search: Compute hash, then probe sequence until found or empty.

• Delete: Mark as deleted (tombstone) in open addressing to preserve probe chain.

Load Factor $\alpha$ = $$\displaystyle \frac{\text{number of entries}}{\text{table size}} $$.
Rehashing: When $\alpha$ exceeds threshold (e.g., 0.7), create larger table, rehash all keys.

B. Applications of Hashing

1. HashMap in Java:

   • Uses separate chaining with linked lists (Java 8+ uses balanced trees if list length > 8).

   • hashCode() method computes hash, then index = (hash & 0x7FFFFFFF) % table.length.

   • Collisions handled by chaining.

   • Rehash when size exceeds capacity * load factor (default 0.75).

2. LRU Cache:

   • Algorithm: On access (get/put), move node to front (most recently used). On capacity exceeded, evict least recently used (tail).

   • Implementation:

     • Doubly Linked List: Maintains access order. Head = MRU, tail = LRU.

     • HashMap: Key → node pointer for O(1) lookup.

     • get(key): If exists, remove node from list, add to head, return value.

     • put(key,value): If key exists, update value, move to head. Else create node, add to head and map. If capacity exceeded, remove tail node and its map entry.

   Time: $O(1)$ for both operations.

C. LRU Cache

See above.

D. B+ Trees

Properties

• All leaves at same level.

• Internal nodes: keys for routing, not data.

• Leaves: contain all data (or pointers to data), linked sequentially for range queries.

• Order $d$: internal node has between $d$ and $2d$ children (except root), leaf has between $d$ and $2d$ keys.

Use in Databases/File Systems

• Efficient for disk-based access (high fanout reduces height).

• Range queries fast via leaf links.

• Balanced, supports $O(\log n)$ search, insert, delete.

Operations Overview

• Search: Like BST, traverse from root to leaf.

• Insert: Insert in leaf, if overflow (2d+1 keys), split leaf and propagate split upward.

• Delete: Remove from leaf, if underflow (<d keys), borrow or merge with sibling, propagate upward.

[!EXAM TIPS]

• Linked Lists: Practice insertion after a given node (requires previous pointer in doubly linked list).

• Stacks: Infix to postfix and postfix evaluation are frequently asked. Remember precedence: ^ > */ > +-.

• Queues: Circular queue conditions: full = (rear+1)%size == front, empty = front == rear.

• BST Deletion: Three cases—leaf (remove), one child (replace with child), two children (replace with inorder successor, then delete successor).

• AVL Rotations: Draw before/after. LL: right rotate at node; LR: left rotate left child, then right rotate node.

• Graph Traversal: BFS uses queue, DFS uses stack/recursion. In DFS, visited array is crucial to avoid infinite loops.

• MST: Prim's grows tree from one vertex; Kruskal's adds edges globally. Prim's better for dense graphs, Kruskal's for sparse.

• Hashing: Separate chaining example with key mod 7 is common. Remember load factor and rehashing.

• Sorting: Quick sort partition steps and time complexity analysis (best/avg/worst). Selection sort time derivation: $$\displaystyle \frac{n(n-1)}{2} $$ comparisons.

• Recurrence: Master Theorem—identify $a, b, f(n)$ and compare $$\displaystyle n^{\log_b a} $$ with $f(n)$.

• Expression Trees: In-order traversal gives infix with parentheses; post-order gives postfix; pre-order gives prefix.