6. DS.md

Data Structures

31. Difference Between Array and Linked List

Array

• Fixed Size: The size is defined at creation.
• Contiguous Memory: Stored in contiguous memory locations.
• Access Time: Faster (O(1)) for random access.
• Insertion/Deletion: Expensive (O(n)) for resizing or shifting.

Linked List

• Dynamic Size: Can grow or shrink dynamically.
• Non-Contiguous Memory: Stored in nodes linked via pointers.
• Access Time: Slower (O(n)) for random access.
• Insertion/Deletion: Efficient (O(1)) if pointers are known.

When to Use

• Use arrays for fixed-size collections requiring frequent access.
• Use linked lists for dynamic collections with frequent insertions/deletions.

---

32. Hash Table

What is a Hash Table?

A hash table is a data structure that maps keys to values using a hash function.

Collision Handling Techniques

1. Chaining: Store multiple values at the same index using a linked list.
2. Open Addressing: Probe for the next available slot.

Example: Chaining

class HashTable {
    private LinkedList[] table;

    public HashTable(int size) {
        table = new LinkedList[size];
    }

    void put(int key, String value) {
        int index = key % table.length;
        if (table[index] == null) table[index] = new LinkedList<>();
        table[index].add(value);
    }
}

---

33. Stack vs Queue

Stack

• LIFO: Last In, First Out.
• Operations: push(), pop(), peek().

Queue

• FIFO: First In, First Out.
• Operations: enqueue(), dequeue().

Stack Implementation Using Array

class Stack {
    private int[] stack;
    private int top;

    public Stack(int size) {
        stack = new int[size];
        top = -1;
    }

    void push(int value) {
        if (top == stack.length - 1) return;
        stack[++top] = value;
    }

    int pop() {
        if (top == -1) return -1;
        return stack[top--];
    }
}

---

34. Trees and Graphs

Trees

• Hierarchical data structure.
• Binary Search Tree (BST): Each node has at most two children, and the left subtree values are less than the root.

Graphs

• Collection of nodes (vertices) connected by edges.
• DFS: Depth-First Search.
• BFS: Breadth-First Search.

Binary Search Tree Implementation

class Node {
    int value;
    Node left, right;

    Node(int value) {
        this.value = value;
        left = right = null;
    }
}

class BST {
    Node root;

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

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

DFS Implementation

void dfs(Node root) {
    if (root == null) return;
    System.out.print(root.value + " ");
    dfs(root.left);
    dfs(root.right);
}

BFS Implementation

void bfs(Node root) {
    Queue queue = new LinkedList<>();
    queue.add(root);

    while (!queue.isEmpty()) {
        Node current = queue.poll();
        System.out.print(current.value + " ");
        if (current.left != null) queue.add(current.left);
        if (current.right != null) queue.add(current.right);
    }
}

---

35. Difference Between Heap and Stack in Memory

Stack

• Usage: Stores method calls, local variables.
• Lifespan: Automatic memory management (deallocated after method execution).
• Speed: Faster due to sequential memory access.

Heap

• Usage: Stores dynamically allocated objects.
• Lifespan: Managed by the garbage collector.
• Speed: Slower due to complex memory management.

Feature	Stack	Heap
Memory Type	Static memory allocation	Dynamic memory allocation
Management	LIFO (Last In, First Out)	Managed by garbage collector
Access Speed	Faster	Slower