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

UNIT 4: Data Structures - Short Notes

I. Fundamentals and Analysis

Data Structure: Organized way to store and manage data for efficient access/modification.
Classification:

• Linear: Arrays, Linked Lists, Stacks, Queues (elements in sequence).

• Non-linear: Trees, Graphs (hierarchical/networked).

• Primitive: Basic types (int, char).

• Non-primitive: Derived (arrays, structures).

Abstract Data Type (ADT): Mathematical model defining data + operations, hiding implementation.
Examples: Stack (LIFO), Queue (FIFO), List (ordered collection).

Asymptotic Notations:

• Big-O (O): Upper bound. $$\displaystyle f(n) = O(g(n)) $$ if ∃ $$\displaystyle c, n_0 $$ s.t. $0 \le f(n) \le c \cdot g(n)$ ∀ $$\displaystyle n \ge n_0 $$.

• Omega (Ω): Lower bound.

• Theta (Θ): Tight bound (both O and Ω).

Complexity Analysis:

• Time complexity: Steps vs input size $n$.

• Space complexity: Memory used.

• Cases: Worst-case (max steps), Average-case (expected), Best-case (min steps).

Algorithm Characteristics: Input, Output, Definiteness, Finiteness, Effectiveness.

Recurrence Relations:

Solving $$\displaystyle T(n) = 2T(n/2) + n \log n $$:

Using Master Theorem: $$\displaystyle a=2, b=2, f(n)=n \log n $$.
$$\displaystyle n^{\log_b a} = n^{\log_2 2} = n $$.
$$\displaystyle f(n) = \Theta(n \log n) = \Theta(n^{\log_b a} \log^k n) $$ with $$\displaystyle k=1 $$.

→ Case 2: $$\displaystyle T(n) = \Theta(n \log^2 n) $$.

[!TIP] Master Theorem applies only to $$\displaystyle T(n)=aT(n/b)+f(n) $$ with $$\displaystyle a \ge 1, b > 1 $$.

II. Arrays and Searching

Array Representation:

• Row-major: $$\displaystyle Address(A[i,j]) = Base + ((i \times Cols) + j) \times ElementSize $$.

• Column-major: $$\displaystyle Address(A[i,j]) = Base + ((j \times Rows) + i) \times ElementSize $$.

Example: $20 \times 5$ array, base=840, word=8 bytes.

Row-major $A[15,3]$: $$\displaystyle 840 + ((15 \times 5) + 3) \times 8 = 840 + 78 \times 8 = \boxed{1464} $$.

Column-major: $$\displaystyle 840 + ((3 \times 20) + 15) \times 8 = 840 + 75 \times 8 = \boxed{1440} $$.

Sparse Matrices: Mostly zeros.

• Triplet representation: Store (row, col, value) for non-zeros.

• Upper/Lower triangular: Store only elements where $i \le j$ (upper) or $i \ge j$ (lower).

Address formula for lower triangular (row-major): $$\displaystyle Address(i,j) = Base + \left( \frac{i(i-1)}{2} + j \right) \times Size $$, for $j \le i$.

Array Issues:

• Overflow: Insertion beyond capacity.

• Underflow: Deletion from empty.

• Compaction: Shifting elements to eliminate holes after deletion.

Searching Algorithms:

• Linear Search: Sequential. $O(n)$ worst-case.

• Binary Search: Sorted array. Divide & conquer. $O(\log n)$.

  Procedure: Compare mid, recurse left/right.

• Fibonacci Search: Uses Fibonacci numbers to divide. Mid = $$\displaystyle start + F_{k-2} $$.

  Steps: Compute $$\displaystyle F_k \ge n $$, set offset=-1, compare, adjust offset/mid. $O(\log n)$.

III. Linked Lists

Types:

• Singly: Node = data + next.

• Doubly: Node = data + prev + next.

• Circular: Last node points to head (singly/doubly).

Operations (Time Complexity):

• Insertion at beginning: $O(1)$.

• Insertion at end: $O(n)$ (singly), $O(1)$ with tail pointer.

• Insertion after node $x$: $O(1)$ given $x$.

• Deletion from beginning: $O(1)$.

• Deletion from end: $O(n)$ (singly), $O(1)$ with doubly.

• Search: $O(n)$.

• Modify: $O(n)$ (search first).

Advantages over Arrays: Dynamic size, efficient insert/delete (no shifting).
Disadvantages: Extra memory for pointers, no random access.

Merging Point of Intersecting Lists:

Algorithm:

1. Find lengths $len1, len2$.

2. Advance longer list by $|len1-len2|$ nodes.

3. Traverse both together until nodes match.

Complexity: $O(m+n)$.

Polynomial Representation & Addition:

• Node: (coefficient, exponent, next).

• Addition: Merge like exponents, traverse both lists. $O(m+n)$.

IV. Stacks

ADT: LIFO. Operations: push(x), pop(), peek().
Array Implementation: Use top index. Push: check overflow, $$\displaystyle arr[++top]=x $$. Pop: check underflow, return $arr[top--]$.

Applications:

1. Balanced Parentheses: Push opening, pop on matching closing. Stack empty at end → balanced.

2. Infix to Postfix Conversion:

   • Precedence: $$\displaystyle ^ > */ > +- $$.

   • Algorithm: Scan infix, output operands, push operators based on precedence/parentheses.

   Example: $$\displaystyle a+b*c \rightarrow abc*+ $$.

3. Postfix Evaluation:

   Scan, push operands, on operator pop two, compute, push result.

   Example: $284-5*+77/$ → step-by-step stack shown below.

4. Josephus Problem: $n$ people, $k$-th eliminated. Use circular linked list or simulate with stack.

Recursive Nature: Stack frames in recursion use stack implicitly.

[!TIP] For infix to postfix: output operands immediately; operators go to stack based on precedence and parentheses.

V. Queues

ADT: FIFO. Operations: enqueue(x), dequeue().
Types:

• Linear Queue: Array with front/rear. Dequeue from front, enqueue at rear.

• Circular Queue: Connect ends. Avoids false overflow.

  Enqueue: $$\displaystyle rear = (rear+1) \mod size $$; check full ($$\displaystyle (rear+1)\%size == front $$).

  Dequeue: $$\displaystyle front = (front+1) \mod size $$; check empty ($$\displaystyle front == -1 $$).

• Dequeue: Insert/delete at both ends.

Linked List Queue: Use head as front, tail as rear. Why head as rear inefficient? Dequeue from head is $O(1)$, but enqueue at head requires traversal to end → $O(n)$. Better: maintain tail pointer.

Priority Queue: Elements with priority.

• Operations: insert(key), deleteMax/Min().

• Heap-based: Complete binary tree, array storage. Insert: percolate up. Delete: replace root with last, percolate down. $O(\log n)$.

VI. Trees

Binary Tree Fundamentals:

• Node, root, leaf, height (max edges from root to leaf), depth (edges from root to node), order (max children), degree (actual children).

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

  Proof: Level $i$ has $$\displaystyle 2^i $$ nodes. Sum $$\displaystyle i=0 $$ to $h$: $$\displaystyle \sum_{i=0}^{h} 2^i = 2^{h+1}-1 $$.

Traversals:

• DFS:

  • Inorder: left, root, right.

  • Preorder: root, left, right.

  • Postorder: left, right, root.

• BFS (Level-order): Queue-based, visit level by level.

Binary Search Tree (BST):

• Left subtree < root < right subtree.

• Insertion: Recursively find leaf position, insert. $O(h)$.

• Deletion:

  1. Leaf: Remove.

  2. One child: Replace with child.

  3. Two children: Replace with inorder successor (min in right subtree), delete successor.

  Example: Delete 45 from BST with children → replace with successor (min in right subtree).

Expression Trees:

• Leaves: operands. Internal nodes: operators.

• Construction from $(a+b*c)+(d*e+f*g)$:

  DiagramCANVAS: Expression tree with + at root, left child +, right child +, etc.

• Traversals:

  • Inorder: $a + b * c + d * e + f * g$ (with parentheses).

  • Preorder: $+ + a * b c + * d e * f g$.

  • Postorder: $a b c * + d e * f g * +$.

Balanced BSTs:

• AVL Trees: Balance factor $$\displaystyle |h_{left} - h_{right}| \le 1 $$.

  • Rotations:

    • LL: Right rotate at unbalanced node.

    • RR: Left rotate.

    • LR: Left rotate on left child, then right rotate on node.

    • RL: Right rotate on right child, then left rotate on node.

  • Insertion/Deletion: Update heights, check balance, rotate if needed. $O(\log n)$.

• Red-Black Trees: Properties: root black, red nodes have black children, equal black-height. Approx. balanced.

• B+ Trees: All leaves at same level, internal nodes only keys, linked leaves. Used in databases.

Tree from Traversals:

• Inorder + Postorder: Last in postorder = root. Find root in inorder → left/right subtrees. Recurse.

• Inorder + Preorder: First in preorder = root.

[!TIP] For BST deletion with two children, always use inorder successor (min in right subtree) or predecessor (max in left).

VII. Graphs

Representations:

• Adjacency Matrix: $V \times V$ matrix, $$\displaystyle A[i][j]=1 $$ if edge. $$\displaystyle O(V^2) $$ space.

• Adjacency List: Array of lists, each list stores neighbors. $O(V+E)$ space.

Traversal:

• BFS: Queue-based. Visit neighbors level-wise.

  Example: Start at A, enqueue A, dequeue A, enqueue B,C, etc.

• DFS: Stack-based (explicit or recursion). Go deep first.

  Example: Start at A, push A, visit B (first neighbor), push B, visit D (B's neighbor), etc.

• Comparison: BFS finds shortest path (unweighted), DFS may not. DFS uses less memory for sparse graphs.

Minimum Spanning Tree (MST):

• Spanning Tree: Connects all vertices, no cycles.

• MST: Spanning tree with min total edge weight.

• Prim's: Grow tree from arbitrary start. Pick min edge to new vertex. $$\displaystyle O(V^2) $$ with matrix, $O(E \log V)$ with heap.

• Kruskal's: Sort edges, add if no cycle (using union-find). $O(E \log E)$.

• Comparison: Prim's good for dense ($$\displaystyle E \approx V^2 $$), Kruskal's for sparse.

Shortest Path:

• Dijkstra's: Greedy, non-negative weights.

  Algorithm: Initialize dist[source]=0, others=∞. Pick min dist unvisited, relax neighbors.

  Example: Graph with nodes A,B,C, weights given.

Connected Components:

Count using DFS/BFS: For each unvisited vertex, run DFS → one component. Count runs.

VIII. Hashing

Hash Function: Maps key to index.

Design: Simple (key mod $m$), multiplication, universal.
Example: $$\displaystyle h(key) = key \mod 7 $$.

Collision Resolution:

• Separate Chaining: Array of linked lists. Colliding keys stored in same bucket.

  Load factor $$\displaystyle \alpha = n/m $$ (avg chain length). Rehash when $\alpha$ high.

• Open Addressing: All in array.

  • Linear Probing: $$\displaystyle h(key, i) = (h'(key) + i) \mod m $$. Clustering.

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

  • Double Hashing: $$\displaystyle h(key, i) = (h_1(key) + i \cdot h_2(key)) \mod m $$.

HashMap Implementation (Java):

class HashMap {

    LinkedList<Entry>[] table;

    int size, capacity;

    float loadFactor = 0.75f;

    void put(K key, V value) {

        int idx = key.hashCode() % capacity;

        for (Entry e : table[idx]) if (e.key.equals(key)) { e.value=value; return; }

        table[idx].add(new Entry(key,value));

        if ((float)size/capacity > loadFactor) rehash();

    }

}

Applications:

1. Databases: Indexing (hash indexes).

2. Caches: LRU cache using hash map + doubly linked list.

3. Compilers: Symbol tables.

4. Password storage: With salt (hash functions).

LRU Policy:

• Data structures: Doubly linked list (access order) + hash map (key → node).

• Algorithm: On access, move node to head. On insert, add to head; if full, remove tail. $O(1)$.

[!TIP] Separate chaining handles arbitrary load factor but has pointer overhead; open addressing is cache-friendly but needs careful load factor (<0.7).

IX. Sorting Algorithms

Basic Sorts:

• Selection Sort: Find min, swap with first unsorted.

  $$\displaystyle O(n^2) $$ always.

  Example: [64,25,12,22,11] → min=11 swap with 64, etc.

• Insertion Sort: Insert each element into sorted left part.

  $$\displaystyle O(n^2) $$ worst, $O(n)$ best (already sorted).

  Example: [5,2,4,6,1,3] → shift elements.

Divide and Conquer:

• Merge Sort:

  • Divide array into halves, sort recursively, merge.

  • Merge: two pointers, compare, copy smaller.

  • Time: $O(n \log n)$ all cases. Space: $O(n)$.

• Quick Sort:

  • Partition: choose pivot (last element), arrange < pivot left, > right.

  • Recurse on partitions.

  • Time: Best/Avg $O(n \log n)$, Worst $$\displaystyle O(n^2) $$ (sorted with bad pivot).

  Example: [26,56,47,36,13,95,85,32], pivot=32 → partition.

Heap Sort (brief):

• Build max-heap (array as complete binary tree).

• Repeatedly extract max (swap root with last, heapify root). $O(n \log n)$.

Internal vs External Sorting:

• Internal: Fits in main memory (all above).

• External: For large data (disk). Techniques: multi-way merge, replacement selection.

X. Advanced Topics and Applications

Hybrid Data Structures:

Map $n$ objects to array $[1,n]$, some stacks, some queues.

• Use array of structs with type flag (stack/queue) and top/front/rear indices.

• Add/delete: check type, perform corresponding operation.

Polynomial Operations:

• Representation: Linked list of (coeff, exp) sorted by exp.

• Addition: Traverse both, compare exponents, add coefficients if equal, else copy larger exp node. $O(m+n)$.

Expression Evaluation:

• Infix to Postfix: Use stack as in Unit IV.

• Postfix Evaluation: Stack as in Unit IV.

  Example: $7 3 4 + - 2 4 5 / + * 6 / 7 +$ → step-by-step stack:

  
  Push 7,3,4 → stack: 7,3,4
  
  +: pop 4,3 → 3+4=7, push 7 → stack: 7,7
  
  -: pop 7,7 → 7-7=0, push 0 → stack: 0
  
  Push 2,4,5 → stack: 0,2,4,5
  
  /: pop 5,4 → 4/5=0.8, push 0.8 → stack: 0,2,0.8
  
  +: pop 0.8,2 → 2+0.8=2.8, push 2.8 → stack: 0,2.8
  
  *: pop 2.8,0 → 0*2.8=0, push 0 → stack: 0
  
  Push 6 → stack: 0,6
  
  /: pop 6,0 → 0/6=0, push 0 → stack: 0
  
  Push 7 → stack: 0,7
  
  +: pop 7,0 → 0+7=7 → stack: 7
  
  

  Result: 7.

Graph Problems:

• Drawing from Adjacency Matrix: Vertex set, for each $$\displaystyle A[i][j]=1 $$ draw edge $i \to j$.

• Connected Components: Initialize visited=false. For each vertex $v$, if not visited, DFS/BFS from $v$, increment count.

Fibonacci Search:

Use Fibonacci numbers to find mid index.

Steps:

1. Find smallest $$\displaystyle F_k \ge n $$.

2. Set offset = -1.

3. While $$\displaystyle F_k > 1 $$:

   $$\displaystyle i = \min(offset+F_{k-2}, n-1) $$.

   If $$\displaystyle key > arr[i] $$, offset = i, $$\displaystyle F_k = F_{k-1} $$.

   Else if $$\displaystyle key < arr[i] $$, $$\displaystyle F_k = F_{k-2} $$.

   Else return $i$.

4. Check last element.

Josephus Problem:
$n$ people, eliminate every $k$-th.

• Stack approach: Simulate circle with circular linked list.

• Mathematical: $$\displaystyle J(n,k) = (J(n-1,k) + k) \mod n $$, $$\displaystyle J(1,k)=0 $$. (0-indexed)

[!TIP] For expression tree, inorder gives infix (with parentheses), postorder gives postfix, preorder gives prefix.