Data Structures — Diploma Computer Engineering Notes

Introduction

Data Structures organize and store data efficiently for easy access and modification. For Diploma students, focus on practical implementation in C/C++.

---

Arrays — Simplest Structure

int arr[10] = {5, 2, 8, 1, 9, 3, 7, 4, 6, 0};

// Accessing: arr[i] → O(1)
// Searching (linear): O(n)
// Binary search (sorted): O(log n)
// Insert at position i: shift right → O(n)
// Delete at position i: shift left → O(n)

2D Arrays (Matrix):

int matrix[3][3] = {1,2,3},{4,5,6},{7,8,9};
// Element at row i, col j: matrix[i][j]
// Row-major storage: elements stored row by row

---

Linked List Implementation

#include <stdio.h>
#include <stdlib.h>

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

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

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

// Delete node with given value
struct Node* deleteNode(struct Node* head, int val) {
    if (head == NULL) return NULL;
    if (head->data == val) {
        struct Node* temp = head;
        head = head->next;
        free(temp);
        return head;
    }
    struct Node* curr = head;
    while (curr->next && curr->next->data != val)
        curr = curr->next;
    if (curr->next) {
        struct Node* temp = curr->next;
        curr->next = temp->next;
        free(temp);
    }
    return head;
}

---

Stack Implementation

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

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

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

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

// Application: Balanced Parentheses Check
int isBalanced(char* expr) {
    for (int i = 0; expr[i]; i++) {
        if (expr[i] == '(') push('(');
        else if (expr[i] == ')') {
            if (isEmpty()) return 0;
            pop();
        }
    }
    return isEmpty();
}

---

Queue Implementation

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

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

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

// Circular Queue: uses (rear+1) % MAX

---

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 temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp;
            }
}

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 temp = arr[i]; arr[i] = arr[minIdx]; arr[minIdx] = temp;
    }
}

Insertion Sort — O(n²) but O(n) for nearly sorted

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;
    }
}

Quick Sort — O(n log n) average

int partition(int arr[], int low, int high) {
    int pivot = arr[high], i = low-1;
    for (int j = low; j < high; j++)
        if (arr[j] <= pivot) { i++; int t=arr[i]; arr[i]=arr[j]; arr[j]=t; }
    int t = arr[i+1]; arr[i+1] = arr[high]; arr[high] = t;
    return i+1;
}
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi-1);
        quickSort(arr, pi+1, high);
    }
}

Sorting Algorithm Comparison: | Algorithm | Best | Average | Worst | Space | Stable | |---|---|---|---|---|---| | Bubble | O(n) | O(n²) | O(n²) | O(1) | Yes | | Selection | O(n²) | O(n²) | O(n²) | O(1) | No | | Insertion | O(n) | O(n²) | O(n²) | O(1) | Yes | | Merge | O(n lg n) | O(n lg n) | O(n lg n) | O(n) | Yes | | Quick | O(n lg n) | O(n lg n) | O(n²) | O(lg n) | No | | Heap | O(n lg n) | O(n lg n) | O(n lg n) | O(1) | No |

---

Binary Trees

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

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

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

---

Solved PYQ Questions

Q1 (2023): What is the time complexity of searching in a BST? Average case: O(log n) — halves search space at each step. Worst case (skewed tree): O(n). Balanced BST guarantees O(log n) always.

Q2 (2023): Convert infix expression A+B*C to postfix. Using Stack:

• Read A → output: A
• Read + → push to stack
• Read B → output: AB
• Read * → higher priority, push: stack[+, *]
• Read C → output: ABC
• End: pop stack → ABC*+ Postfix: ABC+*

Q3 (2022): Trace Bubble Sort on 12 Pass 1: 34,25,12,64 (64 moved to end) Pass 2: 25,12,34,64 (34 in place) Pass 3: 12,25,34,64 (sorted!)

---

Revision Checklist

• Array: random access O(1), insert/delete O(n)
• Linked List: insert at head O(1), search O(n)
• Stack: LIFO, push/pop O(1), applications (balanced brackets, undo)
• Queue: FIFO, enqueue/dequeue O(1), circular queue
• Sorting: know time complexity for all 6 algorithms
• BST: left < root < right; inorder gives sorted output