For Loops

The for loop syntax in C mirrors that of JavaScript:

for (initialization; condition; increment/decrement) {
    // loop body
}

Arrays

Time Complexity

Operation	Average Case	Worst Case
Acess	O(1)	O(1)
Search	O(n)	O(n)
Insert	O(n)	O(n)
Delete	O(n)	O(n)

Multidimensional Arrays

C++ stores multidimensional arrays as a contiguous one-dimensional sequence. For a 2D array A with M rows and N columns, the element A[i][j] is equivalent to A[i * N + j].

STL Container Arrays

The Standard Template Library, part of the C++ standard libray, provides two flexible array structures:

array<int, 5> arr = {1, 2, 3, 4, 5};  // Fixed-size STL array
vector<int> vec = {3, 4, 3};          // Dynamic-size STL vector

Address Calculation in 2D Arrays

Memory layout differs between row-major and column-major ordering, requiring different address formulas:

Row-Major Storage:

• Formula: Address(a[i][j]) = BA + (i * n + j) * size
• Variables: BA (base address), i (row index), j (column index), n (column count), size (element size in bytes)

Column-Major Storage:

• Formula: Address(a[i][j]) = BA + ((j * m) + i) * size
• Variables: BA (base address), i (row index), j (column index), m (row count), size (element size in bytes)

Given: 2D array a[3][4], base address BA=0x1000, element size=4 bytes

Row-major calculation for a[1][2]:
Address(a[1][2]) = 0x1000 + (1 * 4 + 2) * 4
                 = 0x1000 + 24
                 = 0x1018

Column-major calculation for a[1][2]:
Address(a[1][2]) = 0x1000 + (2 * 3 + 1) * 4
                 = 0x1000 + 28
                 = 0x101C

Aray Operations Implementation

#include <iostream>
using namespace std;

int main() {
    const int capacity = 20;
    int count = 10;
    int data[20] = {1, 3, 4, 5, 6, 7, 4, 2, 4, 5};

    // Traversal
    for (int i = 0; i < 10; i++) {
        cout << data[i];
    }

    // Tail insertion
    int newVal = 9;
    if (count < capacity) {
        data[count] = newVal;
        count++;
    } else {
        cout << "overflow" << endl;
    }

    // Head insertion
    int headVal = 10;
    if (count < capacity) {
        for (int i = count; i > 0; i--) {
            data[i] = data[i - 1];
        }
        data[0] = headVal;
    } else {
        cout << "overflow" << endl;
    }

    // Deletion at index
    int targetIdx = 8;
    if (targetIdx >= count) {
        cout << "overbound" << endl;
    } else {
        for (int i = targetIdx; i < count - 1; i++) {
            data[i] = data[i + 1];
        }
        count--;
    }

    return 0;
}

Linked Lists

Concept

A linked list consists of nodes, where each node contains data and a pointer (or reference) to the next node. The first node is the head, and the last node's pointer is NULL, marking the list's end.

Characteristics

• Dynamic sizing: Lists can grow or shrink at runtime without preallocation.
• Efficient insertion/deletion: Pointers are adjusted in O(1) time when position is known.
• Sequential access only: No random access; traversal from head is required.

Linked Lists vs Arrays

Feature	Linked List	Array
Size	Variable	Fixed
Memory	Discontinuous	Contiguous
Access Time	O(n) sequential	O(1) random
Insert/Delete	O(1) at known position	O(n) shifting
Memory Allocation	On-demand	Pre-allocated

Linked List Types

Singly Linked List: Each node has one pointer to the next node, suitable for simple sequential operations.

Head -> Node1 -> Node2 -> Node3 -> NULL

Doubly Linked List: Each node has two pointers: one to the next node, one to the previous. Supports bidirectional traversal.

NULL <- Node1 <-> Node2 <-> Node3 -> NULL

Circular Linked List: The last node's pointer returns to the head, forming a cycle. Can be singly or doubly circular.

Head -> Node1 -> Node2 -> Node3 -> Head (cycle)

Doubly Circular Linked List: Combines doubly linked properties with circular structure.

Head <-> Node1 <-> Node2 <-> Node3 <-> Head (cycle)

Singly Linked List

Time Complexity:

Operation	Average	Worst
Access	θ(n)	θ(n)
Search	θ(n)	θ(n)
Insert	θ(1)	θ(1)
Delete	θ(1)	θ(1)

Node Structure:

struct node {
    int data;
    struct node *next;
};
struct node *head, *current;
current = (struct node *)malloc(sizeof(struct node));

Complete Implementation:

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

struct node {
    int data;
    struct node *next;
};
struct node *head;

void insertAtHead();
void insertAtTail();
void insertAtPosition();
void deleteFromHead();
void deleteFromTail();
void deleteAfterPosition();
void displayList();
void findElement();

int main() {
    int option = 0;
    while (option != 9) {
        printf("\n\n********* Main Menu *********\n");
        printf("Select an operation from the menu...\n");
        printf("===============================================\n");
        printf("1. Insert at beginning\n");
        printf("2. Insert at end\n");
        printf("3. Insert at random position\n");
        printf("4. Delete from beginning\n");
        printf("5. Delete from end\n");
        printf("6. Delete after given position\n");
        printf("7. Search for element\n");
        printf("8. Display list\n");
        printf("9. Exit\n\n");
        printf("===============================================\n");
        printf("Enter your choice: ");
        scanf("%d", &option);

        switch (option) {
            case 1: insertAtHead(); break;
            case 2: insertAtTail(); break;
            case 3: insertAtPosition(); break;
            case 4: deleteFromHead(); break;
            case 5: deleteFromTail(); break;
            case 6: deleteAfterPosition(); break;
            case 7: findElement(); break;
            case 8: displayList(); break;
            case 9: exit(0); break;
            default: printf("Please enter a valid option...\n");
        }
    }
    return 0;
}

void insertAtHead() {
    struct node *ptr;
    int item;
    ptr = (struct node *)malloc(sizeof(struct node));
    if (ptr == NULL) {
        printf("Memory allocation failed!\n");
    } else {
        printf("Enter integer value: ");
        scanf("%d", &item);
        ptr->data = item;
        ptr->next = head;
        head = ptr;
        printf("Node inserted successfully\n");
    }
}

void insertAtTail() {
    struct node *ptr, *temp;
    int item;
    ptr = (struct node *)malloc(sizeof(struct node));
    if (ptr == NULL) {
        printf("Memory allocation failed!\n");
    } else {
        printf("Enter integer value: ");
        scanf("%d", &item);
        ptr->data = item;
        if (head == NULL) {
            ptr->next = NULL;
            head = ptr;
            printf("Node inserted successfully\n");
        } else {
            temp = head;
            while (temp->next != NULL) {
                temp = temp->next;
            }
            temp->next = ptr;
            ptr->next = NULL;
            printf("Node inserted successfully\n");
        }
    }
}

void insertAtPosition() {
    int i, position, item;
    struct node *ptr, *temp;
    ptr = (struct node *)malloc(sizeof(struct node));
    if (ptr == NULL) {
        printf("Memory allocation failed!\n");
    } else {
        printf("Enter integer value: ");
        scanf("%d", &item);
        ptr->data = item;
        printf("Enter insertion position: ");
        scanf("%d", &position);
        temp = head;
        for (i = 0; i < position; i++) {
            temp = temp->next;
            if (temp == NULL) {
                printf("Cannot insert at this position\n");
                return;
            }
        }
        ptr->next = temp->next;
        temp->next = ptr;
        printf("Node inserted successfully\n");
    }
}

void deleteFromHead() {
    struct node *ptr;
    if (head == NULL) {
        printf("List is empty, nothing to delete!\n");
    } else {
        ptr = head;
        head = ptr->next;
        free(ptr);
        printf("Head node deleted\n");
    }
}

void deleteFromTail() {
    struct node *ptr, *prev;
    if (head == NULL) {
        printf("List is empty, nothing to delete!\n");
    } else if (head->next == NULL) {
        head = NULL;
        free(head);
        printf("Only node deleted...\n");
    } else {
        ptr = head;
        while (ptr->next != NULL) {
            prev = ptr;
            ptr = ptr->next;
        }
        prev->next = NULL;
        free(ptr);
        printf("Last node deleted...\n");
    }
}

void deleteAfterPosition() {
    struct node *ptr, *prev;
    int position, i;
    printf("Enter position after which to delete: ");
    scanf("%d", &position);
    ptr = head;
    for (i = 0; i < position; i++) {
        prev = ptr;
        ptr = ptr->next;
        if (ptr == NULL) {
            printf("Cannot delete\n");
            return;
        }
    }
    prev->next = ptr->next;
    free(ptr);
    printf("Node at position %d deleted\n", position + 1);
}

void findElement() {
    struct node *ptr;
    int item, i = 0, found;
    ptr = head;
    if (ptr == NULL) {
        printf("List is empty!\n");
    } else {
        printf("Enter element to search: ");
        scanf("%d", &item);
        while (ptr != NULL) {
            if (ptr->data == item) {
                printf("Item found at position %d\n", i + 1);
                found = 0;
                break;
            } else {
                found = 1;
            }
            i++;
            ptr = ptr->next;
        }
        if (found == 1) {
            printf("Item not found\n");
        }
    }
}

void displayList() {
    struct node *ptr;
    ptr = head;
    if (ptr == NULL) {
        printf("List is empty, nothing to display.\n");
    } else {
        printf("List values:\n");
        printf("--------------------------------------------------\n");
        while (ptr != NULL) {
            printf("\n%d", ptr->data);
            ptr = ptr->next;
        }
    }
    printf("\n\n\n");
}

Doubly Linked List

Node Structure:

struct node {
    struct node *prev;
    int data;
    struct node *next;
};

STL Implementation:

#include <list>
list<int> dll;

Complete Implementation:

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

struct node {
    struct node *prev;
    struct node *next;
    int data;
};
struct node *head;

void insertAtHead();
void insertAtTail();
void insertAtPosition();
void deleteFromHead();
void deleteFromTail();
void deleteAtPosition();
void display();
void search();

int main() {
    int choice = 0;
    while (choice != 9) {
        printf("********* Main Menu *********\n");
        printf("Choose one option from the following list...\n");
        printf("===============================================\n");
        printf("1.Insert at beginning\n2.Insert at end\n3.Insert at position\n");
        printf("4.Delete from beginning\n5.Delete from end\n6.Delete at position\n");
        printf("7.Search\n8.Display\n9.Exit\n");
        printf("Enter your choice: \n");
        scanf("%d", &choice);

        switch (choice) {
            case 1: insertAtHead(); break;
            case 2: insertAtTail(); break;
            case 3: insertAtPosition(); break;
            case 4: deleteFromHead(); break;
            case 5: deleteFromTail(); break;
            case 6: deleteAtPosition(); break;
            case 7: search(); break;
            case 8: display(); break;
            case 9: exit(0); break;
            default: printf("Please enter valid choice..\n");
        }
    }
    return 0;
}

void insertAtHead() {
    struct node *ptr;
    int item;
    ptr = (struct node *)malloc(sizeof(struct node));
    if (ptr == NULL) {
        printf("OVERFLOW\n");
    } else {
        printf("Enter value: ");
        scanf("%d", &item);
        if (head == NULL) {
            ptr->next = NULL;
            ptr->prev = NULL;
            ptr->data = item;
            head = ptr;
        } else {
            ptr->data = item;
            ptr->prev = NULL;
            ptr->next = head;
            head->prev = ptr;
            head = ptr;
        }
        printf("Node inserted\n");
    }
}

void insertAtTail() {
    struct node *ptr, *temp;
    int item;
    ptr = (struct node *)malloc(sizeof(struct node));
    if (ptr == NULL) {
        printf("OVERFLOW\n");
    } else {
        printf("Enter value: ");
        scanf("%d", &item);
        ptr->data = item;
        if (head == NULL) {
            ptr->next = NULL;
            ptr->prev = NULL;
            head = ptr;
        } else {
            temp = head;
            while (temp->next != NULL) {
                temp = temp->next;
            }
            temp->next = ptr;
            ptr->prev = temp;
            ptr->next = NULL;
        }
    }
    printf("node inserted\n");
}

void insertAtPosition() {
    struct node *ptr, *temp;
    int item, loc, i;
    ptr = (struct node *)malloc(sizeof(struct node));
    if (ptr == NULL) {
        printf("OVERFLOW\n");
    } else {
        temp = head;
        printf("Enter location: ");
        scanf("%d", &loc);
        for (i = 0; i < loc; i++) {
            temp = temp->next;
            if (temp == NULL) {
                printf("Less than %d elements\n", loc);
                return;
            }
        }
        printf("Enter value: ");
        scanf("%d", &item);
        ptr->data = item;
        ptr->next = temp->next;
        ptr->prev = temp;
        temp->next = ptr;
        temp->next->prev = ptr;
        printf("node inserted\n");
    }
}

void deleteFromHead() {
    struct node *ptr;
    if (head == NULL) {
        printf("UNDERFLOW\n");
    } else if (head->next == NULL) {
        head = NULL;
        free(head);
        printf("node deleted\n");
    } else {
        ptr = head;
        head = head->next;
        head->prev = NULL;
        free(ptr);
        printf("node deleted\n");
    }
}

void deleteFromTail() {
    struct node *ptr;
    if (head == NULL) {
        printf("UNDERFLOW\n");
    } else if (head->next == NULL) {
        head = NULL;
        free(head);
        printf("node deleted\n");
    } else {
        ptr = head;
        if (ptr->next != NULL) {
            ptr = ptr->next;
        }
        ptr->prev->next = NULL;
        free(ptr);
        printf("node deleted\n");
    }
}

void deleteAtPosition() {
    struct node *ptr, *temp;
    int val;
    printf("Enter data after which node to delete: ");
    scanf("%d", &val);
    ptr = head;
    while (ptr->data != val) {
        ptr = ptr->next;
    }
    if (ptr->next == NULL) {
        printf("Can't delete\n");
    } else if (ptr->next->next == NULL) {
        ptr->next = NULL;
    } else {
        temp = ptr->next;
        ptr->next = temp->next;
        temp->next->prev = ptr;
        free(temp);
        printf("node deleted\n");
    }
}

void display() {
    struct node *ptr;
    printf("Values in list:\n");
    ptr = head;
    while (ptr != NULL) {
        printf("%d\n", ptr->data);
        ptr = ptr->next;
    }
}

void search() {
    struct node *ptr;
    int item, i = 0, found;
    ptr = head;
    if (ptr == NULL) {
        printf("Empty List\n");
    } else {
        printf("Enter item to search: \n");
        scanf("%d", &item);
        while (ptr != NULL) {
            if (ptr->data == item) {
                printf("item found at position %d\n", i + 1);
                found = 0;
                break;
            } else {
                found = 1;
            }
            i++;
            ptr = ptr->next;
        }
        if (found == 1) {
            printf("Item not found\n");
        }
    }
}

Circular Singly Linked List

Node Structure:

struct node {
    int data;
    struct node *next;
};
struct node *head, *ptr;
ptr = (struct node *)malloc(sizeof(struct node));

STL Implementation:

#include <list>
list<int> li;           // doubly circular list
forward_list<int> fl;   // singly circular list

Complete Implementation:

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

struct node {
    int data;
    struct node *next;
};
struct node *head;

void insertAtHead();
void insertAtTail();
void deleteFromHead();
void deleteFromTail();
void search();
void display();

int main() {
    int choice = 0;
    while (choice != 7) {
        printf("********* Main Menu *********\n");
        printf("Choose one option...\n");
        printf("===============================================\n");
        printf("1.Insert at beginning\n2.Insert at end\n");
        printf("3.Delete from beginning\n4.Delete from end\n");
        printf("5.Search for element\n6.Display\n7.Exit\n");
        printf("Enter your choice: \n");
        scanf("%d", &choice);

        switch (choice) {
            case 1: insertAtHead(); break;
            case 2: insertAtTail(); break;
            case 3: deleteFromHead(); break;
            case 4: deleteFromTail(); break;
            case 5: search(); break;
            case 6: display(); break;
            case 7: exit(0); break;
            default: printf("Please enter valid choice..\n");
        }
    }
    return 0;
}

void insertAtHead() {
    struct node *ptr, *temp;
    int item;
    ptr = (struct node *)malloc(sizeof(struct node));
    if (ptr == NULL) {
        printf("OVERFLOW");
    } else {
        printf("Enter node data: ");
        scanf("%d", &item);
        ptr->data = item;
        if (head == NULL) {
            head = ptr;
            ptr->next = head;
        } else {
            temp = head;
            while (temp->next != head) {
                temp = temp->next;
            }
            ptr->next = head;
            temp->next = ptr;
            head = ptr;
        }
        printf("node inserted\n");
    }
}

void insertAtTail() {
    struct node *ptr, *temp;
    int item;
    ptr = (struct node *)malloc(sizeof(struct node));
    if (ptr == NULL) {
        printf("OVERFLOW\n");
    } else {
        printf("Enter data: ");
        scanf("%d", &item);
        ptr->data = item;
        if (head == NULL) {
            head = ptr;
            ptr->next = head;
        } else {
            temp = head;
            while (temp->next != head) {
                temp = temp->next;
            }
            temp->next = ptr;
            ptr->next = head;
        }
        printf("node inserted\n");
    }
}

void deleteFromHead() {
    struct node *ptr;
    if (head == NULL) {
        printf("UNDERFLOW");
    } else if (head->next == head) {
        head = NULL;
        free(head);
        printf("node deleted\n");
    } else {
        ptr = head;
        while (ptr->next != head) {
            ptr = ptr->next;
        }
        ptr->next = head->next;
        free(head);
        head = ptr->next;
        printf("node deleted\n");
    }
}

void deleteFromTail() {
    struct node *ptr, *prev;
    if (head == NULL) {
        printf("UNDERFLOW");
    } else if (head->next == head) {
        head = NULL;
        free(head);
        printf("node deleted\n");
    } else {
        ptr = head;
        while (ptr->next != head) {
            prev = ptr;
            ptr = ptr->next;
        }
        prev->next = ptr->next;
        free(ptr);
        printf("node deleted\n");
    }
}

void search() {
    struct node *ptr;
    int item, i = 0, found = 1;
    ptr = head;
    if (ptr == NULL) {
        printf("Empty List\n");
    } else {
        printf("Enter item to search: \n");
        scanf("%d", &item);
        if (head->data == item) {
            printf("item found at position %d", i + 1);
            found = 0;
        } else {
            while (ptr->next != head) {
                if (ptr->data == item) {
                    printf("item found at position %d", i + 1);
                    found = 0;
                    break;
                } else {
                    found = 1;
                }
                i++;
                ptr = ptr->next;
            }
        }
        if (found != 0) {
            printf("Item not found\n");
        }
    }
}

void display() {
    struct node *ptr;
    ptr = head;
    if (head == NULL) {
        printf("nothing to print");
    } else {
        printf("Values:\n");
        while (ptr->next != head) {
            printf("%d\n", ptr->data);
            ptr = ptr->next;
        }
        printf("%d\n", ptr->data);
    }
}

Circular Doubly Linked List

Node Structure:

struct node {
    struct node *prev;
    int data;
    struct node *next;
};

STL Implementation:

#include <list>
list<int> cdll;

Complete Implementation:

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

struct node {
    struct node *prev;
    struct node *next;
    int data;
};
struct node *head;

void insertAtHead();
void insertAtTail();
void deleteFromHead();
void deleteFromTail();
void display();
void search();

int main() {
    int choice = 0;
    while (choice != 7) {
        printf("********* Main Menu *********\n");
        printf("Choose one option...\n");
        printf("===============================================\n");
        printf("1.Insert at beginning\n2.Insert at end\n");
        printf("3.Delete from beginning\n4.Delete from end\n");
        printf("5.Search\n6.Show\n7.Exit\n");
        printf("Enter your choice: \n");
        scanf("%d", &choice);

        switch (choice) {
            case 1: insertAtHead(); break;
            case 2: insertAtTail(); break;
            case 3: deleteFromHead(); break;
            case 4: deleteFromTail(); break;
            case 5: search(); break;
            case 6: display(); break;
            case 7: exit(0); break;
            default: printf("Please enter valid choice..\n");
        }
    }
    return 0;
}

void insertAtHead() {
    struct node *ptr, *temp;
    int item;
    ptr = (struct node *)malloc(sizeof(struct node));
    if (ptr == NULL) {
        printf("OVERFLOW");
    } else {
        printf("Enter value: ");
        scanf("%d", &item);
        ptr->data = item;
        if (head == NULL) {
            head = ptr;
            ptr->next = head;
            ptr->prev = head;
        } else {
            temp = head;
            while (temp->next != head) {
                temp = temp->next;
            }
            temp->next = ptr;
            ptr->prev = temp;
            head->prev = ptr;
            ptr->next = head;
            head = ptr;
        }
        printf("Node inserted\n");
    }
}

void insertAtTail() {
    struct node *ptr, *temp;
    int item;
    ptr = (struct node *)malloc(sizeof(struct node));
    if (ptr == NULL) {
        printf("OVERFLOW");
    } else {
        printf("Enter value: ");
        scanf("%d", &item);
        ptr->data = item;
        if (head == NULL) {
            head = ptr;
            ptr->next = head;
            ptr->prev = head;
        } else {
            temp = head;
            while (temp->next != head) {
                temp = temp->next;
            }
            temp->next = ptr;
            ptr->prev = temp;
            head->prev = ptr;
            ptr->next = head;
        }
    }
    printf("node inserted\n");
}

void deleteFromHead() {
    struct node *temp;
    if (head == NULL) {
        printf("UNDERFLOW");
    } else if (head->next == head) {
        head = NULL;
        free(head);
        printf("node deleted\n");
    } else {
        temp = head;
        while (temp->next != head) {
            temp = temp->next;
        }
        temp->next = head->next;
        head->next->prev = temp;
        free(head);
        head = temp->next;
    }
}

void deleteFromTail() {
    struct node *ptr;
    if (head == NULL) {
        printf("UNDERFLOW");
    } else if (head->next == head) {
        head = NULL;
        free(head);
        printf("node deleted\n");
    } else {
        ptr = head;
        if (ptr->next != head) {
            ptr = ptr->next;
        }
        ptr->prev->next = head;
        head->prev = ptr->prev;
        free(ptr);
        printf("node deleted\n");
    }
}

void display() {
    struct node *ptr;
    ptr = head;
    if (head == NULL) {
        printf("nothing to print");
    } else {
        printf("Values:\n");
        while (ptr->next != head) {
            printf("%d\n", ptr->data);
            ptr = ptr->next;
        }
        printf("%d\n", ptr->data);
    }
}

void search() {
    struct node *ptr;
    int item, i = 0, found = 1;
    ptr = head;
    if (ptr == NULL) {
        printf("Empty List\n");
    } else {
        printf("Enter item to search: \n");
        scanf("%d", &item);
        if (head->data == item) {
            printf("item found at position %d", i + 1);
            found = 0;
        } else {
            while (ptr->next != head) {
                if (ptr->data == item) {
                    printf("item found at position %d", i + 1);
                    found = 0;
                    break;
                } else {
                    found = 1;
                }
                i++;
                ptr = ptr->next;
            }
        }
        if (found != 0) {
            printf("Item not found\n");
        }
    }
}

Stacks

Array-Based Implementation

#include <stdio.h>

int stack[100], i, choice = 0, n, top = -1;

void push();
void pop();
void show();

int main() {
    printf("Enter number of elements in stack: ");
    scanf("%d", &n);
    printf("********* Stack operations using array *********");
    printf("----------------------------------------------\n");

    while (choice != 4) {
        printf("Choose one option...\n");
        printf("1.Push\n2.Pop\n3.Show\n4.Exit");
        printf("Enter choice: \n");
        scanf("%d", &choice);

        switch (choice) {
            case 1: push(); break;
            case 2: pop(); break;
            case 3: show(); break;
            case 4: printf("Exiting...."); break;
            default: printf("Please enter valid choice ");
        }
    }
    return 0;
}

void push() {
    int val;
    if (top == n) {
        printf("Overflow");
    } else {
        printf("Enter value: ");
        scanf("%d", &val);
        top = top + 1;
        stack[top] = val;
    }
}

void pop() {
    if (top == -1) {
        printf("Underflow");
    } else {
        top = top - 1;
        printf("Item popped");
    }
}

void show() {
    for (i = top; i >= 0; i--) {
        printf("%d\n", stack[i]);
    }
    if (top == -1) {
        printf("Stack is empty");
    }
}

Linked List-Based Implementation

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

void push();
void pop();
void display();

struct node {
    int val;
    struct node *next;
};
struct node *head;

int main() {
    int choice = 0;
    printf("********* Stack operations using linked list *********\n");
    printf("----------------------------------------------\n");

    while (choice != 4) {
        printf("Choose one option...\n");
        printf("1.Push\n2.Pop\n3.Show\n4.Exit");
        printf("Enter choice: \n");
        scanf("%d", &choice);

        switch (choice) {
            case 1: push(); break;
            case 2: pop(); break;
            case 3: display(); break;
            case 4: printf("Exiting...."); break;
            default: printf("Please enter valid choice ");
        }
    }
    return 0;
}

void push() {
    int val;
    struct node *ptr = (struct node *)malloc(sizeof(struct node));
    if (ptr == NULL) {
        printf("Cannot push element");
    } else {
        printf("Enter value: ");
        scanf("%d", &val);
        if (head == NULL) {
            ptr->val = val;
            ptr->next = NULL;
            head = ptr;
        } else {
            ptr->val = val;
            ptr->next = head;
            head = ptr;
        }
        printf("Item pushed");
    }
}

void pop() {
    int item;
    struct node *ptr;
    if (head == NULL) {
        printf("Underflow");
    } else {
        item = head->val;
        ptr = head;
        head = head->next;
        free(ptr);
        printf("Item popped: %d", item);
    }
}

void display() {
    struct node *ptr;
    ptr = head;
    if (ptr == NULL) {
        printf("Stack is empty\n");
    } else {
        printf("Stack elements:\n");
        while (ptr != NULL) {
            printf("%d\n", ptr->val);
            ptr = ptr->next;
        }
    }
}

Queues

Concept

A queue is an ordered list where insertions (enqueue) happen at the rear and deletions (dequeue) happen at the front.

Applications

• Waiting lists for shared resources (printers, disks, CPU)
• Asynchronous data transfer (pipes, file I/O, sockets)
• Buffers
• Interrupt handling in operating systems

Time Complexity

Complexity	Access	Search	Insert	Delete
Average	θ(n)	θ(n)	θ(1)	θ(1)
Worst	θ(n)	θ(n)	θ(1)	θ(1)

Array-Based Queue

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

#define MAXSIZE 5

void enqueue();
void dequeue();
void display();

int front = -1, rear = -1;
int queue[MAXSIZE];

int main() {
    int choice;
    while (choice != 4) {
        printf("************************* Main Menu *****************************\n");
        printf("=================================================================\n");
        printf("1.Insert element\n2.Delete element\n3.Display queue\n4.Exit\n");
        printf("Enter choice: ");
        scanf("%d", &choice);

        switch (choice) {
            case 1: enqueue(); break;
            case 2: dequeue(); break;
            case 3: display(); break;
            case 4: exit(0); break;
            default: printf("Enter valid choice??\n");
        }
    }
    return 0;
}

void enqueue() {
    int item;
    printf("\nEnter element: ");
    scanf("%d", &item);

    if (rear == MAXSIZE - 1) {
        printf("OVERFLOW\n");
        return;
    }
    if (front == -1 && rear == -1) {
        front = 0;
        rear = 0;
    } else {
        rear = rear + 1;
    }
    queue[rear] = item;
    printf("Value inserted");
}

void dequeue() {
    int item;
    if (front == -1 || front > rear) {
        printf("UNDERFLOW\n");
        return;
    } else {
        item = queue[front];
        if (front == rear) {
            front = -1;
            rear = -1;
        } else {
            front = front + 1;
        }
        printf("Value deleted: %d", item);
    }
}

void display() {
    int i;
    if (rear == -1) {
        printf("Empty queue\n");
    } else {
        printf("Queue elements:\n");
        for (i = front; i <= rear; i++) {
            printf("\n%d\n", queue[i]);
        }
    }
}

Linked List-Based Queue

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

struct node {
    int data;
    struct node *next;
};
struct node *front;
struct node *rear;

void enqueue();
void dequeue();
void display();

int main() {
    int choice;
    while (choice != 4) {
        printf("************************* Main Menu *****************************\n");
        printf("=================================================================\n");
        printf("1.Insert element\n2.Delete element\n3.Display queue\n4.Exit\n");
        printf("Enter choice: ");
        scanf("%d", &choice);

        switch (choice) {
            case 1: enqueue(); break;
            case 2: dequeue(); break;
            case 3: display(); break;
            case 4: exit(0); break;
            default: printf("Enter valid choice??\n");
        }
    }
    return 0;
}

void enqueue() {
    struct node *ptr;
    int item;

    ptr = (struct node *)malloc(sizeof(struct node));
    if (ptr == NULL) {
        printf("OVERFLOW\n");
        return;
    } else {
        printf("Enter value: \n");
        scanf("%d", &item);
        ptr->data = item;
        if (front == NULL) {
            front = ptr;
            rear = ptr;
            front->next = NULL;
            rear->next = NULL;
        } else {
            rear->next = ptr;
            rear = ptr;
            rear->next = NULL;
        }
    }
}

void dequeue() {
    struct node *ptr;
    if (front == NULL) {
        printf("UNDERFLOW\n");
        return;
    } else {
        ptr = front;
        front = front->next;
        free(ptr);
        printf("Item dequeued");
    }
}

void display() {
    struct node *ptr;
    ptr = front;
    if (front == NULL) {
        printf("Empty queue\n");
    } else {
        printf("Queue elements:\n");
        while (ptr != NULL) {
            printf("%d\n", ptr->data);
            ptr = ptr->next;
        }
    }
}

Circular Queue

In a circular queue, the last index wraps around to follow the first. The queue is full when front == -1 and rear == MAXSIZE - 1.

Time Complexity:

Operation	Complexity
Front	O(1)
Rear	O(1)
enQueue()	O(1)
deQueue()	O(1)

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

#define MAXSIZE 5

void enqueue();
void dequeue();
void display();

int front = -1, rear = -1;
int queue[MAXSIZE];

int main() {
    int choice;
    while (choice != 4) {
        printf("************************* Main Menu *****************************\n");
        printf("=================================================================\n");
        printf("1.Insert element\n2.Delete element\n3.Display queue\n4.Exit\n");
        printf("Enter choice: ");
        scanf("%d", &choice);

        switch (choice) {
            case 1: enqueue(); break;
            case 2: dequeue(); break;
            case 3: display(); break;
            case 4: exit(0); break;
            default: printf("Enter valid choice??\n");
        }
    }
    return 0;
}

void enqueue() {
    int item;
    printf("Enter element: ");
    scanf("%d", &item);

    if ((rear + 1) % MAXSIZE == front) {
        printf("OVERFLOW");
        return;
    } else if (front == -1 && rear == -1) {
        front = 0;
        rear = 0;
    } else if (rear == MAXSIZE - 1 && front != 0) {
        rear = 0;
    } else {
        rear = (rear + 1) % MAXSIZE;
    }
    queue[rear] = item;
    printf("Value inserted");
}

void dequeue() {
    int item;
    if (front == -1 && rear == -1) {
        printf("UNDERFLOW\n");
        return;
    } else if (front == rear) {
        front = -1;
        rear = -1;
    } else if (front == MAXSIZE - 1) {
        front = 0;
    } else {
        front = front + 1;
    }
    printf("Item dequeued");
}

void display() {
    int i;
    if (front == -1) {
        printf("Circular Queue is Empty!!!\n");
    } else {
        i = front;
        printf("Circular Queue Elements: \n");
        if (front <= rear) {
            while (i <= rear)
                printf("%d %d %d\n", queue[i++], front, rear);
        } else {
            while (i <= MAXSIZE - 1)
                printf("%d %d %d\n", queue[i++], front, rear);
            i = 0;
            while (i <= rear)
                printf("%d %d %d\n", queue[i++], front, rear);
        }
    }
}

Hash Tables

Concept

A hash table organizes data using a hash function to enable fast insertion and search operations. With a well-chosen hash function, hash tables achieve excellent performance for both operations.

Types

• Hash Set: Implements the set data structure to store unique values.
• Hash Map: Implements the map data structure to store key-value pairs.

Collision Resolution

Problem Analysis:

Ideally, a perfect one-to-one hash function would eliminate collisions. However, collisions are nearly inevitable in practice. For instance, using hash function y = x % 5, both 1987 and 2 map to bucket 2.

The problem relates to bucket capacity and the number of keys potentially mapping to the same bucket.

Open Addressing (Rebuilding):

When a collision occurs at address p = H(key), generate a new address p1. Continue generating addresses until finding an empty slot. The general rehashing function:

Hi = (H(key) + di) % m, where i = 1, 2, ..., n

Where H(key) is the hash function, m is the table size, and di is the increment sequence.

C++ STL Implementation

Hash Set:

#include <set>
set<int> s;
multiset<int> ms;
unordered_multiset<int> ums;

Hash Map:

#include <map>
map<int, int> m;
multimap<int, int> mm;
unordered_multimap<int, int> umm;

Disjoint Set Union (Union-Find)

Applications

Union-Find is considered one of the most elegant and concise data structures by competitive programmers. It manages disjoint sets and supports two primary operations:

• Union: Merge two disjoint sets into one.
• Find: Determine which set an element belongs to.

Core Operations

Initialization: Each element starts as its own set with parent pointing to itself.

Find: Recursively trace parent pointers to the root to determine set membership.

Union: Merge two sets by making one root's parent point to the other root.

Path Compression: During find operations, directly connect each visited node to the root, reducing future lookup time.

Implementation

class UnionFind {
public:
    vector<int> parent;

    UnionFind(int n) {
        parent.resize(n);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    int findRoot(int x) {
        if (x == parent[x]) return x;
        return parent[x] = findRoot(parent[x]);
    }

    void unite(int a, int b) {
        parent[findRoot(a)] = findRoot(b);
    }

    bool connected(int a, int b) {
        return findRoot(a) == findRoot(b);
    }
};

Trees

Characteristics

• Each node has a finite number of child nodes or none.
• Exactly one node serves as the root with no parent.
• Every non-root node has exactly one parent.
• Non-root nodes can have multiple disjoint subtrees.
• No cycles exist in a tree structure.

Terminology

• Ancestor: Any node on the path from root to the current node.
• Parent: Node containing child nodes.
• Child: Root node of a subtree.
• Root: Topmost node without a parent.
• Leaf: Node with zero children.
• Sibling: Nodes sharing the same parent.
• Degree: Number of children for a node.
• Tree Degree: Maximum degree among all nodes.
• Level: Root is level 0, children are level 1, etc.
• Depth: Path length from root to node (root depth = 0).
• Height: Longest path from node to a leaf (leaf height = 0).
• Forest: Collection of m (m ≥ 0) disjoint trees.
• Path: Sequence of consecutive edges.
• Key: Value stored in a node.

Binary Tree Types

• Strict/Proper Binary Tree: Every non-leaf has at least two children.
• Complete Binary Tree: All levels filled except possibly the last, with nodes left-aligned.
• Balanced Binary Tree (AVL): Height difference between subtrees ≤ 1.
• Binary Search Tree: Ordered binary tree where left < root < right.
• B-Tree: Self-balancing tree optimized for disk access, holding multiple keys per node.

Node Structure

struct treenode {
    int key;
    struct treenode *parent;
    struct treenode *firstChild;
    struct treenode *nextSibling;
};

Binary Tree Properties

1. Maximum nodes at level i: 2^(i-1) for i ≥ 1
2. Maximum nodes in tree of depth k: 2^k - 1 for k ≥ 1
3. Minimum height for n nodes: log2(n+1)
4. Relationship: n0 = n2 + 1 (leaf nodes = degree-2 nodes + 1)

Traversal Methods

Depth-First Search (DFS): Explores as deep as possible before backtracking. Three variants based on root-left-right order:

Traversal	Order
Preorder	Root → Left → Right
Inorder	Left → Root → Right
Postorder	Left → Right → Root

Breadth-First Search (BFS) / Level Order: Visits nodes level by level, typically implemented with a queue.

Difference Array

Concept

A difference array enables efficient range updates by storing differences between consecutive elements. It transforms O(n) range modifications into O(1) operations.

Construction

Given original array a, difference array d is constructed as:

1. d[0] = a[0]
2. For i from 1 to n-1: d[i] = a[i] - a[i-1]

Example: For a = [1, 2, 3, 4, 5], difference array d = [1, 1, 1, 1, 1]

Range Update Operation

To add k to range [l, r]:

1. d[l] += k
2. d[r + 1] -= k (if r + 1 is within bounds)

Example: Balloon Painting

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int MAXN = 100010;

int diff[MAXN], result[MAXN];
int x, y;

int main() {
    int n;
    while (scanf("%d", &n) && n) {
        memset(diff, 0, sizeof(diff));
        memset(result, 0, sizeof(result));

        for (int i = 1; i <= n; i++) {
            scanf("%d%d", &x, &y);
            diff[x]++;
            diff[y + 1]--;
        }

        for (int i = 1; i <= n; i++) {
            result[i] = result[i - 1] + diff[i];
        }

        for (int i = 1; i < n; i++) {
            printf("%d ", result[i]);
        }
        printf("%d\n", result[n]);
    }
    return 0;
}

Binary Indexed Tree (Fenwick Tree)

Concept

A Binary Indexed Tree (BIT) or Fenwick Tree efficiently handles dynamic prefix sum queries and updates. It achieves O(log n) time for both operations by leveraging binary representation.

Core Operations

Initialization: Start with a zero-filled array, then perform updates to construct the tree.

Point Update: Add a value to an element and update relevant tree nodes. Time complexity: O(log n).

Prefix Sum Query: Calculate sum from first element to position i. Time complexity: O(log n).

Example

Original array: a = [0, 0, 0, 0, 0, 0, 0, 0]

BIT = [0, 0, 0, 0, 0, 0, 0, 0]

Operation 1: Update a[3] += 5
  i = 3, BIT[3] += 5  -> BIT = [0, 0, 0, 5, 0, 0, 0, 0]
  i = 4, BIT[4] += 5  -> BIT = [0, 0, 0, 5, 5, 0, 0, 0]
  i = 8, BIT[8] += 5  -> BIT = [0, 0, 0, 5, 5, 0, 0, 5]

Operation 2: Query prefix sum query(3)
  i = 3, sum = 0 + BIT[3] = 5
  i = 2, sum = 5 + BIT[2] = 5
  i = 0, stop
  Result: query(3) = 5

Operation 3: Update a[5] += 2
  i = 5, BIT[5] += 2  -> BIT = [0, 0, 0, 5, 5, 2, 0, 5]
  i = 6, BIT[6] += 2  -> BIT = [0, 0, 0, 5, 5, 2, 2, 5]
  i = 8, BIT[8] += 2  -> BIT = [0, 0, 0, 5, 5, 2, 2, 7]

Segment Tree

Concept

A segment tree is a powerful data structure for frequent range queries and updates on arrays. Using divide-and-conquer, it efficiently handles operations like range sum, minimum, or maximum queries with O(log n) complexity.

Example

Given: temperatures = [23, 27, 30, 26, 24, 28, 29, 25]

Building: Each node stores the maximum temperature for its interval. The tree recursively splits the array in half.

Tree Structure:

                          [30]
                    /                  \
                [30]                      [29]
              /      \                  /      \
          [27]       [30]            [28]       [29]
          /   \      /   \          /   \       /   \
       [23] [27]  [30] [26]      [24] [28]  [29] [25]

Operation 1: Query range [1, 4] Find maximum from hours 2 to 5. Traverse the tree, combining partial results. Result: max(30, 28) = 30

Operation 2: Update position 2 to 32 Update leaf node, then propagate changes up the tree. New tree stores updated maximums.

Graphs

Terminology

• Order: Number of vertices in graph G
• Subgraph: G' where V' ⊆ V and E' ⊆ E
• Spanning Subgraph: Subgraph containing all vertices
• Induced Subgraph: Subgraph containing specified vertices and all edges between them
• Degree: Number of edges incident to vertex v, denoted d(v)
• In-degree/Out-degree: For directed graphs, edges entering/exiting a vertex
• Loop: Edge connecting a vertex to itself
• Path: Sequence of vertices connected by edges
• Simple Path: Path with no repeated vertices (except possibly start/end)
• Trail: Path with distinct edges
• Cycle: Closed path with distinct vertices except start/end
• Bridge: Edge whose removal disconnects the graph
• Adjacent: Two vertices connected by an edge

Graph Classification

• Directed: Edges have direction
• Undirected: Edges have no direction
• Connected: Path exists between every pair of vertices
• Complete: Every vertex connects to all others
• Weighted: Edges carry weight values

Representation

Adjacency Matrix: Square matrix where rows and columns represent vertices. M[i][j] = 1 indicates an edge between vertices i and j.

Adjacency List: Array of lists where each list contains neighbors of a vertex. Sum of list lengths equals twice the number of edges (undirected).

Graph Traversals

Breadth-First Search (BFS): Explores all neighbors at current depth before moving deeper. Uses a queue.

1. Initialize all vertices to ready state
2. Enqueue start vertex, mark as waiting
3. While queue not empty:
   a. Dequeue vertex N, process it
   b. Enqueue all waiting neighbors of N
4. Exit

Depth-First Search (DFS): Explores as far as possible along each branch before backtracking. Uses a stack.

1. Initialize all vertices to ready state
2. Push start vertex to stack, mark as waiting
3. While stack not empty:
   a. Pop vertex N, process it
   b. Push all ready neighbors of N
4. Exit