Data Structures Notes — BCA Sem 2

Data Structures — Introduction

Data Structure = data ko organized tarike se store karne ka method taaki efficiently access aur modify ho sake.

Classification:

Linear DS:     Array, Linked List, Stack, Queue
Non-Linear DS: Tree, Graph
Hash-Based:    Hash Table, Hash Map

---

1. Arrays

// Static array in C
int marks[5] = {85, 90, 78, 92, 88};
printf("%d\n", marks[2]);  // 78 — O(1) random access

// 2D array
int matrix[3][3] = {{1,2,3},{4,5,6},{7,8,9}};
printf("%d\n", matrix[1][2]);  // 6

// Array operations complexity
// Access: O(1), Search: O(n), Insert/Delete: O(n)

Array vs ArrayList: | Feature | Array | ArrayList | |---------|-------|-----------| | Size | Fixed | Dynamic | | Type | Primitive ok | Objects only | | Speed | Faster | Slightly slower | | Flexibility | Less | More |

---

2. Linked List

struct Node {
    int data;
    struct Node* next;
};

// Insert at beginning — O(1)
void insertFront(struct Node** head, int data) {
    struct Node* newNode = malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = *head;
    *head = newNode;
}

// Delete a node — O(n)
void deleteNode(struct Node** head, int key) {
    struct Node *temp = *head, *prev = NULL;
    if (temp && temp->data == key) {
        *head = temp->next; free(temp); return;
    }
    while (temp && temp->data != key) {
        prev = temp; temp = temp->next;
    }
    if (!temp) return;
    prev->next = temp->next; free(temp);
}

// Print list
void printList(struct Node* head) {
    while (head) {
        printf("%d → ", head->data);
        head = head->next;
    }
    printf("NULL\n");
}

Types:

• Singly: next pointer only
• Doubly: prev + next (bidirectional traversal)
• Circular: last → first (no NULL end)

---

3. Stack (LIFO)

#define MAX 100
int stack[MAX], top = -1;

void push(int x) {
    if (top == MAX-1) { printf("Overflow!\n"); return; }
    stack[++top] = x;
}

int pop() {
    if (top == -1) { printf("Underflow!\n"); return -1; }
    return stack[top--];
}

int peek() { return (top == -1) ? -1 : stack[top]; }
int isEmpty() { return top == -1; }

// Balanced parentheses check
int isBalanced(char* expr) {
    for (int i = 0; expr[i]; i++) {
        char c = expr[i];
        if (c=='(' || c=='{' || c=='[') push(c);
        else {
            if (isEmpty()) return 0;
            char t = pop();
            if ((c==')' && t!='(') || (c=='}' && t!='{') || (c==']' && t!='['))
                return 0;
        }
    }
    return isEmpty();
}

---

4. Queue (FIFO)

#define MAX 100
int queue[MAX], front = -1, rear = -1;

void enqueue(int x) {
    if (rear == MAX-1) { printf("Full!\n"); return; }
    if (front == -1) front = 0;
    queue[++rear] = x;
}

int dequeue() {
    if (front == -1) { printf("Empty!\n"); return -1; }
    int x = queue[front];
    if (front == rear) front = rear = -1;
    else front++;
    return x;
}

// Circular Queue fixes wasted space:
// rear = (rear + 1) % MAX
// front = (front + 1) % MAX

---

5. Binary Tree & BST

struct TreeNode {
    int data;
    struct TreeNode *left, *right;
};

// Insert in BST
struct TreeNode* insert(struct TreeNode* root, int data) {
    if (!root) {
        struct TreeNode* n = malloc(sizeof(struct TreeNode));
        n->data = data; n->left = n->right = NULL;
        return n;
    }
    if (data < root->data) root->left = insert(root->left, data);
    else if (data > root->data) root->right = insert(root->right, data);
    return root;
}

// Traversals
void inorder(struct TreeNode* root) {   // Left Root Right
    if (!root) return;
    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}

void preorder(struct TreeNode* root) {  // Root Left Right
    if (!root) return;
    printf("%d ", root->data);
    preorder(root->left);
    preorder(root->right);
}

BST Operations Complexity: | Operation | Average | Worst (skewed) | |-----------|---------|----------------| | Search | O(log n) | O(n) | | Insert | O(log n) | O(n) | | Delete | O(log n) | O(n) |

---

6. Sorting Algorithms

// Bubble Sort — O(n²)
void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++)
        for (int j = 0; j < n-i-1; j++)
            if (arr[j] > arr[j+1]) {
                int t = arr[j]; arr[j] = arr[j+1]; arr[j+1] = t;
            }
}

// Selection Sort — O(n²)
void selectionSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        int minIdx = i;
        for (int j = i+1; j < n; j++)
            if (arr[j] < arr[minIdx]) minIdx = j;
        int t = arr[i]; arr[i] = arr[minIdx]; arr[minIdx] = t;
    }
}

// Insertion Sort — O(n²) worst, O(n) best
void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i], j = i-1;
        while (j >= 0 && arr[j] > key) { arr[j+1] = arr[j]; j--; }
        arr[j+1] = key;
    }
}

// Merge Sort — O(n log n) always
void merge(int arr[], int l, int m, int r) {
    int n1=m-l+1, n2=r-m;
    int L[n1], R[n2];
    for(int i=0;i<n1;i++) L[i]=arr[l+i];
    for(int j=0;j<n2;j++) R[j]=arr[m+1+j];
    int i=0,j=0,k=l;
    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++];
}
void mergeSort(int arr[], int l, int r) {
    if(l<r){int m=(l+r)/2;mergeSort(arr,l,m);mergeSort(arr,m+1,r);merge(arr,l,m,r);}
}

Comparison Table:

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

---

7. Searching

// Linear Search — O(n)
int linearSearch(int arr[], int n, int key) {
    for (int i = 0; i < n; i++)
        if (arr[i] == key) return i;
    return -1;
}

// Binary Search — O(log n), requires SORTED array
int binarySearch(int arr[], int n, int key) {
    int low = 0, high = n-1;
    while (low <= high) {
        int mid = low + (high-low)/2;  // avoid overflow
        if (arr[mid] == key) return mid;
        if (arr[mid] < key) low = mid+1;
        else high = mid-1;
    }
    return -1;
}

---

Exam Important Questions

1. Linked list mein insert aur delete ka algorithm (with code)
2. Stack se balanced parentheses check karo
3. BST mein insertion aur inorder traversal
4. Merge sort ka working aur complexity
5. Binary search vs linear search — kab kya use karein?
6. Queue aur circular queue mein kya difference hai?
7. Array aur linked list — comparison table
8. Bubble sort code likhein aur trace karo: 12

---

Viva Questions

Q: Two pointers technique kya hai? A: Do pointers same array pe different speeds ya different positions se move karte hain. Middle of linked list: slow (1 step) + fast (2 steps). Cycle detect karna, palindrome check, sorted array mein pair sum — sab two pointers se O(n) mein.

Q: Recursion aur iteration mein kab kya prefer karein? A: Tree/graph traversal, divide-and-conquer (merge sort) — recursion natural hai. Performance critical code — iteration (no stack overhead). Deep recursion — stack overflow risk.

Q: Time complexity kaise calculate karte hain? A: Nested loops: O(n²). Single loop: O(n). Loop log n times (halving): O(log n). Recursion T(n) = 2T(n/2) + O(n): Master theorem → O(n log n). Best case vs worst case vs average case.