Data Structures Notes — B.Tech IT Sem 2

Data Structures — Introduction

Data Structure ek organized tarika hai data ko store, manage aur access karne ka. Sahi data structure choose karna program ki efficiency ko 10x–100x improve kar sakta hai.

Types:

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

---

1. Arrays

Array ek contiguous memory mein same-type elements ka collection hai.

// Java Array Example
int[] marks = {85, 90, 78, 92, 88};
System.out.println(marks[2]); // Output: 78

| Operation | Time Complexity | |-----------|----------------| | Access | O(1) | | Search (linear) | O(n) | | Insert at end | O(1) amortized | | Insert at middle | O(n) | | Delete | O(n) |

2D Arrays (Matrix):

int[][] matrix = new int[3][3];
// Row-major order mein store hota hai memory mein
for(int i = 0; i < 3; i++)
  for(int j = 0; j < 3; j++)
    matrix[i][j] = i * 3 + j;

---

2. Linked List

Node = Data + Pointer (next node ka address)

class Node {
    int data;
    Node next;
    Node(int d) { data = d; next = null; }
}

class LinkedList {
    Node head;

    // Insert at beginning — O(1)
    void insertFront(int data) {
        Node newNode = new Node(data);
        newNode.next = head;
        head = newNode;
    }

    // Delete by value — O(n)
    void delete(int key) {
        Node temp = head, prev = null;
        if (temp != null && temp.data == key) {
            head = temp.next;
            return;
        }
        while (temp != null && temp.data != key) {
            prev = temp;
            temp = temp.next;
        }
        if (temp == null) return;
        prev.next = temp.next;
    }
}

Types:

• Singly Linked List — ek direction (next only)
• Doubly Linked List — dono direction (prev + next)
• Circular Linked List — last node → head se connect

---

3. Stack (LIFO)

Last In First Out — jaise plate stack ya browser back button.

import java.util.Stack;

Stack<Integer> stack = new Stack<>();
stack.push(10);  // [10]
stack.push(20);  // [10, 20]
stack.push(30);  // [10, 20, 30]
System.out.println(stack.pop());  // 30 — LIFO
System.out.println(stack.peek()); // 20 — top without remove

Applications:

• Infix → Postfix conversion
• Balanced parentheses check
• Function call management (recursion)
• Undo/Redo operations

Balanced Parentheses Algorithm:

boolean isBalanced(String expr) {
    Stack<Character> s = new Stack<>();
    for (char c : expr.toCharArray()) {
        if (c == '(' || c == '{' || c == '[') s.push(c);
        else {
            if (s.isEmpty()) return false;
            char top = s.pop();
            if (c == ')' && top != '(') return false;
            if (c == '}' && top != '{') return false;
            if (c == ']' && top != '[') return false;
        }
    }
    return s.isEmpty();
}

---

4. Queue (FIFO)

First In First Out — jaise line/queue mein wait karna.

import java.util.LinkedList;
import java.util.Queue;

Queue<Integer> queue = new LinkedList<>();
queue.add(10);     // enqueue
queue.add(20);
queue.add(30);
System.out.println(queue.poll()); // 10 — FIFO
System.out.println(queue.peek()); // 20

Types:

• Simple Queue — basic FIFO
• Circular Queue — rear wrap around to front
• Priority Queue — highest priority first
• Deque — insert/delete both ends

---

5. Trees

Tree ek hierarchical non-linear data structure hai.

Terminology:

• Root — top node (no parent)
• Leaf — node with no children
• Height — longest path from root to leaf
• Depth — distance from root to node

Binary Tree

Har node ke maximum 2 children hote hain.

Binary Search Tree (BST)

• Left subtree < Node < Right subtree
• Search/Insert/Delete: O(log n) average, O(n) worst

class BST {
    Node root;

    void insert(int data) {
        root = insertRec(root, data);
    }

    Node insertRec(Node root, int data) {
        if (root == null) return new Node(data);
        if (data < root.data) root.left = insertRec(root.left, data);
        else if (data > root.data) root.right = insertRec(root.right, data);
        return root;
    }

    // Inorder traversal → sorted output
    void inorder(Node root) {
        if (root != null) {
            inorder(root.left);
            System.out.print(root.data + " ");
            inorder(root.right);
        }
    }
}

Tree Traversals: | Traversal | Order | Use | |-----------|-------|-----| | Inorder | Left → Root → Right | BST sorted output | | Preorder | Root → Left → Right | Copy tree | | Postorder | Left → Right → Root | Delete tree | | Level Order | Level by level | BFS |

---

6. Sorting Algorithms

| Algorithm | Best | Average | Worst | Space | Stable | |-----------|------|---------|-------|-------|--------| | Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | ✅ | | Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | ❌ | | Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | ✅ | | Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | ✅ | | Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | ❌ | | Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | ❌ |

// Merge Sort Implementation
void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

void merge(int[] arr, int left, int mid, int right) {
    int n1 = mid - left + 1, n2 = right - mid;
    int[] L = new int[n1], R = new int[n2];
    System.arraycopy(arr, left, L, 0, n1);
    System.arraycopy(arr, mid + 1, R, 0, n2);
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2)
        arr[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

---

7. Hashing

Hash Function key ko fixed-size index mein convert karta hai.

// Simple hash function
int hash(String key, int size) {
    int hash = 0;
    for (char c : key.toCharArray())
        hash = (hash * 31 + c) % size;
    return hash;
}

Collision Handling:

• Chaining — linked list at each index
• Open Addressing — linear probing, quadratic probing

import java.util.HashMap;
HashMap<String, Integer> map = new HashMap<>();
map.put("Alice", 95);
map.put("Bob", 88);
System.out.println(map.get("Alice")); // 95
System.out.println(map.containsKey("Bob")); // true

---

Exam Important Questions

1. Array aur Linked List mein kya difference hai? Kab kya use karein?
2. Stack ka use karke infix expression ko postfix mein convert karo
3. BST mein insertion aur deletion ka algorithm likhein
4. Merge sort aur Quick sort mein kya difference hai?
5. Hashing mein collision kaise resolve hoti hai?
6. Binary tree ke traversals explain karo with example
7. Circular queue implement karo
8. Priority queue kya hai aur kahan use hoti hai?

---

Viva Questions

Q: Stack aur Queue mein kya difference hai? A: Stack LIFO (Last In First Out) hai, Queue FIFO (First In First Out). Stack mein push/pop ek hi end se, Queue mein enqueue/dequeue alag ends se.

Q: O(n log n) sorting algorithms kaunse hain? A: Merge Sort, Heap Sort, aur average case mein Quick Sort.

Q: Linked List mein mid element kaise dhundein? A: Two pointer technique — slow (1 step) aur fast (2 step) pointers. Jab fast end pe pahunche, slow mid pe hoga.