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

UNIT 3: Data Structures

I. Fundamentals of Data Structures

A. Definition and Classification

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

• Classification:

  • Linear: Elements arranged sequentially (e.g., Array, Linked List, Stack, Queue).

  • Non-linear: Hierarchical or network relationships (e.g., Trees, Graphs).

  • Primitive: Basic types (int, char) directly supported by language.

  • Non-primitive: Derived from primitives (e.g., Array, Structure, Class).

B. Abstract Data Types (ADT)

• ADT: Mathematical model defining data and operations without implementation details.

• Examples:

  • Stack ADT: LIFO; operations: Push, Pop, Peek, isEmpty, isFull.

  • Queue ADT: FIFO; operations: Enqueue, Dequeue, Front, Rear, isEmpty.

  • List ADT: Ordered collection; operations: Insert, Delete, Search, Traverse.

C. Asymptotic Analysis

• Purpose: Describe algorithm efficiency as input size grows.

• Notations:

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

  • Omega (Ω): Lower bound (best-case).

  • Theta (Θ): Tight bound (average-case).

• Time Complexity: Number of primitive operations.

• Space Complexity: Memory used.

• Recurrence Relations:

  • Master Theorem: For $$\displaystyle T(n) = aT(n/b) + f(n) $$:

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

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

    • If $$\displaystyle f(n) = \Omega(n^{\log_b a + \epsilon}) $$, then $$\displaystyle T(n) = \Theta(f(n)) $$.

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

[!TIP] Common Pitfall: Confusing worst-case (Big-O) with average-case (Theta). Always specify which bound you are analyzing.

II. Linear Data Structures

A. Arrays

• Memory Layout: Contiguous block; address calculation for 2D array:

  • Row-major: $$\displaystyle Addr(A[i][j]) = Base + ((i \times Col) + j) \times Size $$

  • Column-major: $$\displaystyle Addr(A[i][j]) = Base + ((j \times Row) + i) \times Size $$

• Sparse Matrices: Mostly zeros.

  • Representations:

    • Triplet (3-tuple): Store (row, col, value) for non-zero elements.

    • 2D Array: Direct but wasteful.

  • Triangular Matrices:

    • Upper triangular: Non-zero only when $i \le j$. Total elements: $n(n+1)/2$.

    • Lower triangular: Non-zero only when $i \ge j$.

• Issues:

  • Overflow: No space for new element.

  • Underflow: Deleting from empty structure.

  • Compaction: Shifting elements to remove gaps (in sparse arrays).

B. Linked Lists

• Types:

  • Singly: Each node has data and next.

  • Doubly: Each node has prev, data, next.

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

• Operations & Time Complexities (for singly list, $n$ = length):

  | Operation | At Beginning | At End | After Specified Node | Search/Modify | |-----------|--------------|--------|----------------------|---------------| | Time | $O(1)$ | $O(n)$ | $O(n)$ (search) + $O(1)$ (insert) | $O(n)$ |

• Applications:

  • Polynomial Representation: Each node stores coefficient and exponent; sorted by exponent.

  • Merging Point of Two Lists:

    
    1. Find lengths L1, L2.
    
    2. Advance longer list by |L1 - L2| nodes.
    
    3. Traverse both together until nodes match.
    
    

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

• Drawbacks of Singly Linked List:

  • Cannot traverse backward.

  • Deletion of last node requires $O(n)$ (need previous node).

  • No efficient access to previous node.

C. Stacks

• ADT Operations:

  • Push(x): Add to top.

  • Pop(): Remove from top.

  • Peek(): Return top without removing.

  • isEmpty(), isFull().

• Implementations:

  • Array-based:

    
    #define MAX 100
    
    int stack[MAX], top = -1;
    
    void push(int x) { if (top < MAX-1) stack[++top] = x; }
    
    int pop() { if (top >= 0) return stack[top--]; }
    
    

    Overflow: top == MAX-1; Underflow: top == -1.

  • Linked List-based: top points to head; Push/Pop at head ($O(1)$).

• Applications:

  • Infix to Postfix Conversion:

    • Precedence: ^ > *// > +/-.

    • Algorithm: Scan infix; output operands; push operators; pop higher/equal precedence operators.

  • Postfix Evaluation:

    • Scan postfix; push operands; on operator, pop two operands, compute, push result.

  • Balanced Parentheses: Push opening brackets; pop on closing; stack empty at end → balanced.

  • Recursion: Call stack stores return addresses and local variables.

  • Josephus Problem:

    
    1. Create circular linked list of n nodes.
    
    2. Start at head, count k-1, delete kth node.
    
    3. Repeat until one node remains.
    
    

D. Queues

• ADT Operations:

  • Enqueue(x): Add to rear.

  • Dequeue(): Remove from front.

  • Front(), Rear().

• Types:

  • Ordinary (Linear) Queue: FIFO; array-based suffers from false overflow.

  • Circular Queue: Connect last to first; avoid false overflow using modulo arithmetic.

    • Enqueue: rear = (rear+1) % MAX; check (rear+1)%MAX == front for overflow.

    • Dequeue: front = (front+1) % MAX; check front == rear for underflow.

  • Priority Queue: Elements with priority; often implemented with min-heap/max-heap.

  • Dequeue (Double-ended): Insert/delete from both ends.

• Implementations:

  • Array-based (Circular): Use front, rear indices.

  • Linked List-based: head as front, tail as rear; Enqueue at tail ($O(1)$), Dequeue at head ($O(1)$).

• Applications: CPU scheduling, I/O buffers, BFS traversal.

[!TIP] Circular Queue Condition: Use (rear + 1) % MAX == front to check full, not rear == MAX-1.

III. Trees

A. Binary Trees

• Properties:

  • Height (h): Longest path from root to leaf (edges). Depth of node: path length from root.

  • Degree: Number of children.

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

• Traversals:

  • Inorder (LNR): Left, Root, Right → BST gives sorted order.

  • Preorder (NLR): Root, Left, Right → used to copy tree.

  • Postorder (LRN): Left, Right, Root → used to delete tree.

  • Level-order (BFS): Queue-based; visit by levels.

B. Binary Search Trees (BST)

• Property: Left subtree < root < right subtree.

• Operations:

  • Insertion: Recursively find leaf position; insert as leaf.

    
    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 Cases:

    1. Leaf: Simply remove.

    2. One child: Replace with child.

    3. Two children: Find inorder successor (min in right subtree), copy data, delete successor.

  • Search: Recursive/iterative comparison.

• Time Complexity:

  • Average (balanced): $O(\log n)$.

  • Worst (skewed): $O(n)$.

C. Expression Trees

• Construction:

  • From postfix: Push operands; on operator, pop two operands, make them children, push new subtree.

  • From infix: Use stack (shunting-yard) to get postfix, then build.

• Traversals:

  • Inorder: Gives infix (with parentheses).

  • Preorder: Prefix expression.

  • Postorder: Postfix expression.

• Evaluation: Postorder traversal; compute when operator node encountered.

• Example: For $(a + b \times c) + (d \times e + f \times g)$:

  • Postfix: a b c * + d e * f g * + +

  • Inorder: (a + (b * c)) + ((d * e) + (f * g))

D. Balanced BSTs

1. AVL Trees

• Balance Factor (BF): $$\displaystyle BF = height(left) - height(right) $$; must be $-1, 0, 1$.

• Rotations (single/double):

  • LL (Left-Left): Right rotate on 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/Deletion: Standard BST operation, then check balance and rotate up the path.

2. Red-Black Trees

• Properties:

  1. Every node is red or black.

  2. Root is black.

  3. Leaves (NIL) are black.

  4. Red node's children are black.

  5. Every path from node to leaves has same black height.

• Contrast with AVL: AVL more strictly balanced (height $O(\log n)$); Red-Black allows more flexibility (fewer rotations on insert/delete).

E. B+ Trees

• Structure:

  • Internal nodes: Keys + child pointers.

  • Leaves: All data pointers; linked sequentially.

• Properties:

  • All leaves at same level.

  • Order $m$: Max $m$ children, min $\lceil m/2 \rceil$ (except root).

• Use: Databases/file systems (range queries, disk-based).

IV. Graphs

A. Representations

B. Graph Traversals

• Breadth-First Search (BFS):

  
  1. Queue Q; visited[all]=false.
  
  2. Enqueue start, visited[start]=true.
  
  3. While Q not empty:
  
       u = Dequeue(Q);
  
       for each neighbor v of u:
  
         if !visited[v]: visited[v]=true; Enqueue(Q, v).
  
  

  Time: $O(V+E)$; Space: $O(V)$.

• Depth-First Search (DFS):

  
  1. visited[all]=false.
  
  2. DFS(u): visited[u]=true; for each neighbor v: if !visited[v] DFS(v).
  
  

  Time: $O(V+E)$; Space: $O(V)$ (stack).

• Graph vs Tree Traversal: Graph may have cycles → track visited; may be disconnected → loop all vertices.

C. Spanning Trees

• Spanning Tree: Subgraph connecting all vertices without cycles.

• Minimum Spanning Tree (MST): Spanning tree with minimum total edge weight.

• Algorithms:

  • Prim's (Greedy, dense graphs):

    1. Start with arbitrary vertex.

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

    3. Use priority queue (min-heap) for edges.

    Time: $O(E \log V)$ with heap.

  • Kruskal's (Greedy, sparse graphs):

    1. Sort all edges by weight.

    2. Add edges in order, skipping those that form cycle (use Union-Find).

    Time: $O(E \log E)$ (sorting dominates).

• Comparison:

  | Prim's | Kruskal's | |------------|---------------| | Grows single tree | Grows forest | | Better for dense graphs ($$\displaystyle E \approx V^2 $$) | Better for sparse graphs ($E \approx V$) | | $O(E \log V)$ with heap | $O(E \log E)$ |

D. Shortest Path

• Dijkstra's Algorithm (non-negative weights):

  
  1. dist[all]=∞; dist[source]=0; PQ = min-heap of (dist, vertex).
  
  2. While PQ not empty:
  
       u = extract-min(PQ);
  
       for each neighbor v with weight w:
  
         if dist[u] + w < dist[v]:
  
           dist[v] = dist[u] + w; decrease-key(PQ, v).
  
  

  Time: $O((V+E) \log V)$ with heap.

E. Counting Connected Components

1. visited[all]=false; count=0.

2. for each vertex u:

     if !visited[u]: count++; DFS(u) or BFS(u).

Time: $O(V+E)$.

V. Hashing

A. Hash Functions

• Purpose: Map keys to indices in hash table.

• Common Functions:

  • Division: $$\displaystyle h(k) = k \mod m $$ (simple, but clustering if $m$ not prime).

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

  • Folding: Divide key into parts, sum them.

  • Multiplication: $$\displaystyle h(k) = \lfloor m(kA \mod 1) \rfloor $$, $$\displaystyle 0<A<1 $$.

• Properties of Good Hash Function:

  • Fast to compute.

  • Uniform distribution.

  • Minimizes collisions.

B. Collision Resolution

• Separate Chaining:

  • Array of linked lists; collisions stored in same bucket.

  • Example with $$\displaystyle h(k)=k \mod 7 $$:

    
    Insert 32: 32%7=4 → bucket[4]: 32
    
    Insert 50: 50%7=1 → bucket[1]: 50
    
    Insert 700: 700%7=0 → bucket[0]: 700
    
    Insert 140: 140%7=0 → bucket[0]: 700 → 140
    
    

• Open Addressing (all in array):

  • Linear Probing: $$\displaystyle h(k,i) = (h'(k) + i) \mod m $$; clusters form.

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

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

C. HashMap Implementation (Java/C++)

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

• C++ unordered_map: Typically separate chaining.

• Concept:

  
  class HashMap {
  
    List<Entry>[] table;
  
    int hash(key) { ... }
  
    void put(key, value) {
  
      int idx = hash(key) % table.length;
  
      for (Entry e : table[idx]) if (e.key==key) { e.value=value; return; }
  
      table[idx].add(new Entry(key,value));
  
    }
  
  }
  
  

D. Applications

• Compiler Symbol Table: Fast lookup of identifiers.

• Database Indexing: Hash indexes for equality searches.

• Cryptography: Password storage (with salt).

• LRU Cache:

  • Use hash map (key → node) + doubly linked list (access order).

  • On access: move node to head.

  • On capacity full: remove tail node.

VI. Sorting Algorithms

A. Comparison-Based Sorts

Selection Sort

• Algorithm:

  
  for i=0 to n-2:
  
    min = i
  
    for j=i+1 to n-1:
  
      if A[j] < A[min]: min = j
  
    swap(A[i], A[min])
  
  

• Time Complexity:

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

  • Swaps: $O(n)$.

  • \boxed{\text{Total: } O(n^2)}.

Insertion Sort

• Algorithm:

  
  for i=1 to n-1:
  
    key = A[i]; j = i-1
  
    while j>=0 and A[j] > key:
  
      A[j+1] = A[j]; j--
  
    A[j+1] = key
  
  

• Time:

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

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

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

Merge Sort

• Recursive:

  
  mergeSort(A, l, r):
  
    if l < r:
  
      m = (l+r)/2
  
      mergeSort(A, l, m)
  
      mergeSort(A, m+1, r)
  
      merge(A, l, m, r)
  
  

• Iterative: Bottom-up; merge pairs of subarrays.

• Time: All cases $O(n \log n)$; Space: $O(n)$ (auxiliary array).

Quick Sort

• Algorithm:

  
  quickSort(A, l, r):
  
    if l < r:
  
      p = partition(A, l, r)  // pivot at correct position
  
      quickSort(A, l, p-1)
  
      quickSort(A, p+1, r)
  
  
  
  partition(A, l, r):
  
    pivot = A[r]; i = l-1
  
    for j=l to r-1:
  
      if A[j] <= pivot: i++; swap(A[i], A[j])
  
    swap(A[i+1], A[r]); return i+1
  
  

• Time:

  • Best/Average: $O(n \log n)$.

  • Worst (sorted, pivot last): $$\displaystyle O(n^2) $$.

• Example (last pivot): 26, 56, 47, 36, 13, 95, 85, 32

  • Pivot=32: partition → [26,13] 32 [56,47,36,95,85]

  • Recurse on subarrays.

B. 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: create sorted runs, merge multi-way).

VII. Searching Algorithms

Binary Search

• Procedure (on sorted array):

  
  low=0, high=n-1
  
  while low <= high:
  
    mid = (low+high)/2
  
    if A[mid] == key: return mid
  
    else if A[mid] < key: low = mid+1
  
    else high = mid-1
  
  return -1
  
  

• Time Complexity: $O(\log n)$.

• Requirement: Sorted array.

Fibonacci Search

• Technique: Use Fibonacci numbers to divide array.

  
  fibM = smallest Fib >= n; offset = -1
  
  while fibM > 1:
  
    i = min(offset+fibM2, n-1)
  
    if A[i] < key: fibM = fibM1; offset = i
  
    else if A[i] > key: fibM = fibM2
  
    else: return i
  
  if fibM1 and A[offset+1]==key: return offset+1
  
  return -1
  
  

• Advantage: Fewer comparisons on average; useful for uniform access cost (e.g., tape drives).

VIII. Advanced Topics and Applications

A. Heap Operations

• Heap Property:

  • Min-heap: Parent ≤ children.

  • Max-heap: Parent ≥ children.

• Implementation: Array (complete binary tree).

  • Parent: $\lfloor(i-1)/2\rfloor$, Left: $2i+1$, Right: $2i+2$.

• Operations:

  • Insert: Add at end, bubble up (heapify-up). $O(\log n)$.

  • Delete (extract root): Replace root with last element, bubble down (heapify-down). $O(\log n)$.

• Example (max-heap): Insert 15 into [20,10,12,5,7] → add at end, compare with parent, swap if needed.

B. Polynomial Operations

• Representation: Singly linked list; each node: {coeff, exp, next}; sorted by exponent.

• Addition Algorithm:

  
  while p1 && p2:
  
    if p1->exp > p2->exp: add p1 to result; p1=p1->next
  
    else if p1->exp < p2->exp: add p2 to result; p2=p2->next
  
    else: sum coeffs; if sum≠0 add; p1=p1->next; p2=p2->next
  
  add remaining nodes of p1 or p2.
  
  

  Time: $O(m+n)$.

C. Expression Conversion and Evaluation

• Infix to Postfix (using stack):

  
  while infix not empty:
  
    if operand: output
  
    if '(': push
  
    if ')': pop until '('
  
    if operator: while stack top has higher/equal precedence (not '('): pop output; push current.
  
  pop all remaining operators.
  
  

• Postfix Evaluation:

  
  for each token:
  
    if operand: push
  
    if operator: pop b, pop a; push (a op b)
  
  result = pop()
  
  

• Example: Infix a+b*c → Postfix abc*+.

D. Tree Construction from Traversals

• From Inorder & Postorder:

  • Last element in postorder is root.

  • Find root in inorder → left/right subtrees.

  • Recurse on left/right inorder and postorder segments.

• From Inorder & Preorder:

  • First element in preorder is root.

  • Find root in inorder → left/right subtrees.

  • Recurse on left/right inorder and preorder segments.

• Example:

  Inorder: DGBAHEICF, Postorder: GDBHIEFCA

  • Root = A (last postorder).

  • Inorder left: DGB (before A), right: HEICF.

  • Postorder left: GDB (first 3), right: HIEFC (next 5).

  • Recurse.

E. Mixed Data Structure Design

• Design: Array of size $n$; first $$\displaystyle n_1 $$ indices for stacks, next $$\displaystyle n-n_1 $$ for queues.

• Operations:

  • Stack push/pop: Use array index within stack region; maintain top pointer per stack.

  • Queue enqueue/dequeue: Use circular queue logic within queue region; maintain front/rear per queue.

• Example: $$\displaystyle n=10 $$, $$\displaystyle n_1=3 $$ stacks (each size 3), $$\displaystyle n_2=1 $$ queue (size 7). Use separate pointers for each ADT.

IX. Algorithm Design and Analysis

Criteria and Characteristics

• Criteria:

  • Correctness: Produces expected output.

  • Efficiency: Time/space complexity.

  • Simplicity: Easy to understand/implement.

  • Generality: Handles broad inputs.

• Characteristics:

  • Input, Output, Definiteness, Finiteness, Effectiveness.

Demonstrating Efficiency

• Time/Space Trade-off: E.g., using more space (hash table) reduces time (search $O(1)$ vs $O(n)$).

• Empirical Analysis: Run on varied inputs, measure.

• Theoretical Analysis: Asymptotic notation (Big-O).

Designing for Specific Problems

• Problem: Find two elements with sum closest to zero.

• Algorithm:

  1. Sort array ($O(n \log n)$).

  2. Use two pointers: left=0, right=n-1.

  3. While left < right:

     • Compute sum = A[left] + A[right].

     • Track min absolute sum.

     • If sum < 0: left++ (increase sum).

     • Else: right-- (decrease sum).

  4. Return pair with min sum.

• Complexity: $O(n \log n)$ (sorting dominates).

• Optimization: Without sorting? $$\displaystyle O(n^2) $$ brute-force; sorting is optimal.

[!TIP] For closest sum, sorting enables two-pointer technique; always consider sorting first if comparison-based.