LAB 1: Stack using Array

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

typedef struct node {
    int id;
    struct node *prev;
    struct node *next;
} Node;

Node *head = NULL;

// 1. Insert at Beginning
void insBeg(int val) {
    Node *newN = (Node*)malloc(sizeof(Node));
    newN->id = val;
    newN->prev = NULL;
    newN->next = head;

    if (head != NULL) {
        head->prev = newN;
    }
    head = newN;
    printf("Song %d added at start.\n", val);
}

// 2. Insert at End
void insEnd(int val) {
    Node *newN = (Node*)malloc(sizeof(Node));
    newN->id = val;
    newN->next = NULL;

    if (head == NULL) {
        newN->prev = NULL;
        head = newN;
    } else {
        Node *temp = head;
        while (temp->next) temp = temp->next;
        temp->next = newN;
        newN->prev = temp;
    }
    printf("Song %d added at end.\n", val);
}

// 3. Delete by Song ID
void deleteID(int val) {
    if (head == NULL) {
        printf("Playlist is empty!\n");
        return;
    }

    Node *temp = head;
    // Find the node with the given ID
    while (temp != NULL && temp->id != val) {
        temp = temp->next;
    }

    if (temp == NULL) {
        printf("Song ID %d not found.\n", val);
        return;
    }

    // If node to be deleted is head
    if (temp == head) {
        head = temp->next;
    }
    
    // If there is a next node, update its prev pointer
    if (temp->next != NULL) {
        temp->next->prev = temp->prev;
    }
    
    // If there is a prev node, update its next pointer
    if (temp->prev != NULL) {
        temp->prev->next = temp->next;
    }

    free(temp);
    printf("Song %d removed from playlist.\n", val);
}

// 4. Display Forward
void dispForward() {
    Node *temp = head;
    printf("Playlist (Forward): ");
    while (temp) {
        printf("%d <-> ", temp->id);
        temp = temp->next;
    }
    printf("NULL\n");
}

// 5. Display Backward
void dispBackward() {
    if (head == NULL) return;
    Node *temp = head;
    // Go to the last node
    while (temp->next) temp = temp->next;
    
    printf("Playlist (Backward): ");
    while (temp) {
        printf("%d <-> ", temp->id);
        temp = temp->prev; // Move backward using prev pointer
    }
    printf("NULL\n");
}

// 6. Search for Song ID
void search(int val) {
    Node *temp = head;
    int pos = 1;
    while (temp) {
        if (temp->id == val) {
            printf("Song %d found at position %d.\n", val, pos);
            return;
        }
        temp = temp->next;
        pos++;
    }
    printf("Song %d not found.\n", val);
}

int main() {
    int ch, val;
    while (1) {
        printf("\n--- Playlist Menu ---\n");
        printf("1.InsBeg 2.InsEnd 3.DeleteID 4.DispForward 5.DispBackward 6.Search 7.Exit\nChoice: ");
        scanf("%d", &ch);
        switch (ch) {
            case 1: printf("ID: "); scanf("%d", &val); insBeg(val); break;
            case 2: printf("ID: "); scanf("%d", &val); insEnd(val); break;
            case 3: printf("ID to delete: "); scanf("%d", &val); deleteID(val); break;
            case 4: dispForward(); break;
            case 5: dispBackward(); break;
            case 6: printf("ID to search: "); scanf("%d", &val); search(val); break;
            case 7: exit(0);
        }
    }
    return 0;
}

LAB 2: Queue using Array

#include <stdio.h>

#define MAX 10

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

int isEmpty() { return (front == -1 || front > rear); }

int isFull() { return (front == MAX - 1); }

void enqueue(int x) {
  if (isFull()) {
    printf("Queue Overflow\n");
    return;
  }

  if (front == -1)
    front = 0;
  rear++;
  queue[rear] = x;
}

void dequeue() {
  if (isEmpty()) {
    printf("Queue Underflow\n");
    return;
  }

  printf("Removed: %d\n", queue[front]);
  front++;
}

void peek() {
  if (isEmpty()) {
    printf("Queue is Empty\n");
    return;
  }

  printf("Front element: %d\n", queue[front]);
}

void display() {
  int i;

  if (isEmpty()) {
    printf("Queue is empty\n");
    return;
  }
  printf("Elements: ");
  for (i = 0; i <= rear; i++) {
    printf("%d ", queue[i]);
  }
  printf("\n");
}

int main() {
  int ch, x;

  while (1) {
    printf("1. Enqueue\n");
    printf("2. Dequeue\n");
    printf("3. Peek\n");
    printf("4. Display\n");
    printf("5. isEmpty\n");
    printf("6. isFull\n");
    printf("7. Exit\n");
    printf("Enter your choice: ");
    scanf("%d", &ch);

    switch (ch) {
    case 1: {
      printf("Enter element: ");
      scanf("%d", &x);
      enqueue(x);
      break;
    }

    case 2: {
      dequeue();
      break;
    }

    case 3: {
      peek();
      break;
    }

    case 4: {
      display();
      break;
    }

    case 5: {
      if (isEmpty())
        printf("Queue is empty\n");
      else
        printf("Queue is not empty\n");
      break;
    }

    case 6: {
      if (isFull())
        printf("Queue is full\n");
      else
        printf("Queue is not full\n");
      break;
    }

    case 7: {
      return 0;
    }

    default: {
      printf("Invalid choice. Please try again.");
    }
    }
  }
}

LAB 3: Singly Linked List

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

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

Node *head = NULL;
int count = 0;

void countNodes() { printf("Total nodes: %d\n", count); }

void create(int n) {
  int x;
  for (int i = 0; i < n; i++) {
    printf("Enter data: ");
    scanf("%d", &x);
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = x;
    newNode->next = NULL;

    if (!head) {
      head = newNode;
    } else {
      Node *temp = head;
      while (temp->next) {
        temp = temp->next;
      }
      temp->next = newNode;
    }
    count++;
  }
}

void insertBegin(int x) {
  Node *newNode = (Node *)malloc(sizeof(Node));
  newNode->data = x;
  newNode->next = head;
  head = newNode;
  count++;
  countNodes();
}

void insertEnd(int x) {
  Node *newNode = (Node *)malloc(sizeof(Node));
  newNode->data = x;
  newNode->next = NULL;

  if (!head) {
    head = newNode;
  } else {
    Node *temp = head;
    while (temp->next) {
      temp = temp->next;
    }
    temp->next = newNode;
  }
  count++;
  countNodes();
}

void deleteBegin() {
  if (!head)
    return;
  Node *temp = head;
  head = head->next;
  free(temp);
  count--;
  countNodes();
}

void deleteEnd() {
  if (!head)
    return;
  if (!head->next) {
    free(head);
    head = NULL;
  } else {
    Node *temp = NULL;
    while (temp->next->next) {
      temp = temp->next;
    }
    free(temp->next);
    temp->next = NULL;
  }
  count--;
  countNodes();
}

void search(int key) {
  int pos = 1;
  Node *temp = head;
  while (temp) {
    if (temp->data == key) {
      printf("Key '%d' found at position %d\n", key, pos);
    }
    temp = temp->next;
    pos++;
  }
  printf("Key '%d' not found.\n", key);
}

void display() {
  Node *temp = head;
  while (temp) {
    printf("%d -> ", temp->data);
    temp = temp->next;
  }
  printf("NULL\n");
}

int main() {
  int ch, x, n;

  while (1) {
    printf("1. Create List\n");
    printf("2. Insert at Beginning\n");
    printf("3. Insert at End\n");
    printf("4. Delete at Beginning\n");
    printf("5. Delete at End\n");
    printf("6. Search for an element\n");
    printf("7. Display all elements\n");
    printf("8. Total count of nodes\n");
    printf("9. Exit\n");
    printf("Enter your choice: ");
    scanf("%d", &ch);

    switch (ch) {
    case 1: {
      printf("Enter number of nodes: ");
      scanf("%d", &n);
      create(n);
      break;
    }

    case 2: {
      printf("Enter data: ");
      scanf("%d", &x);
      insertBegin(x);
      break;
    }

    case 3: {
      printf("Enter data: ");
      scanf("%d", &x);
      insertEnd(x);
      break;
    }

    case 4: {
      deleteBegin();
      break;
    }

    case 5: {
      deleteEnd();
      break;
    }

    case 6: {
      printf("Enter search element: ");
      scanf("%d", &x);
      search(x);
      break;
    }

    case 7: {
      display();
      break;
    }

    case 8: {
      countNodes();
      break;
    }

    case 9: {
      return 0;
    }

    default: {
      printf("Invalid choice. Please try again.\n");
    }
    }
  }
}

LAB 4: Stack using Linked List

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

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

Node *top = NULL;
int count = 0;

void countNodes() { printf("Stack size: %d\n", count); }

int isEmpty() { return top == NULL; }

void push(int x) {
  Node *newNode = (Node *)malloc(sizeof(Node));
  if (!newNode) {
    printf("Stack Overflow\n");
    return;
  }
  newNode->data = x;
  newNode->next = top;
  top = newNode;
  count++;
  printf("Pushed %d\n", x);
  countNodes();
}

void pop() {
  if (isEmpty()) {
    printf("Stack Underflow\n");
    return;
  }
  Node *temp = top;
  int popped = temp->data;
  top = top->next;
  free(temp);
  count--;
  printf("Popped %d\n", popped);
  countNodes();
}

void peek() {
  if (isEmpty()) {
    printf("Stack is empty.\n");
  } else {
    printf("Top element: %d\n", top->data);
  }
}

void display() {
  if (isEmpty()) {
    printf("Stack is empty\n");
    return;
  }
  Node *temp = top;
  printf("Stack: ");
  while (temp) {
    printf("%d -> ", temp->data);
    temp = temp->next;
  }
  printf("NULL\n");
}

int main() {
  int ch, x;
  while (1) {
    printf("1. Push\n");
    printf("2. Pop\n");
    printf("3. Peek\n");
    printf("4. isEmpty\n");
    printf("5. Display\n");
    printf("6. Exit\n");
    printf("Enter your choice: ");
    scanf("%d", &ch);

    switch (ch) {
    case 1: {
      printf("Enter value: ");
      scanf("%d", &x);
      push(x);
      break;
    }

    case 2: {
      pop();
      break;
    }

    case 3: {
      peek();
      break;
    }

    case 4: {
      if (isEmpty())
        printf("Stack is empty\n");
      else
        printf("Stack is not empty.\n");
      break;
    }

    case 5: {
      display();
      break;
    }

    case 6: {
      return 0;
    }

    default: {
      printf("Invalid choice.\n");
    }
    }
  }
}

LAB 5: Queue using Linked List

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

typedef struct node {
  int token;
  struct node *next;
} Node;

Node *front = NULL;
Node *rear = NULL;

void addCustomer(int t) {
  Node *newNode = (Node *)malloc(sizeof(Node));
  if (!newNode) {
    printf("System Memory full!\n");
    return;
  }
  newNode->token = t;
  newNode->next = NULL;

  if (rear == NULL) {
    front = rear = newNode;
  } else {
    rear->next = newNode;
    rear = newNode;
  }
  printf("Token %d added to the queue.\n", t);
}

void serveCustomer() {
  if (front == NULL) {
    printf("No customers in queue.\n");
    return;
  }
  Node *temp = front;
  printf("Serving Customer with token: %d\n", temp->token);

  front = front->next;

  if (front == NULL) {
    rear = NULL;
  }

  free(temp);
}

void viewNext() {
  if (front == NULL) {
    printf("No customers in queue.\n");
  } else {
    printf("Next customer to be served: Token  %d\n", front->token);
  }
}

void display() {
  if (front == NULL) {
    printf("No customers in queue.\n");
    return;
  }
  Node *temp = front;
  while (temp) {
    printf("%d ", temp->token);
    temp = temp->next;
  }
  printf("\n");
}

int main() {
  int ch, token;

  while (1) {
    printf("Customer Service Token Management System.\n");
    printf("1. Add Customer (Enqueue)\n");
    printf("2. Serve Customer (Dequeue)\n");
    printf("3. View Next Customer (Peek)\n");
    printf("4. Display all waiting customers\n");
    printf("5. Exit\n");
    printf("Enter your choice: ");
    scanf("%d", &ch);

    switch (ch) {
    case 1: {
      printf("Enter token number: ");
      scanf("%d", &token);
      addCustomer(token);
      break;
    }

    case 2: {
      serveCustomer();
      break;
    }

    case 3: {
      viewNext();
      break;
    }

    case 4: {
      display();
      break;
    }

    case 5: {
      printf("Exiting system...\n");
      return 0;
    }

    default: {
      printf("Invalid choice. Please try again\n");
    }
    }
  }
}

LAB 6: Doubly Linked List

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

typedef struct node {
  int id;
  struct node *prev;
  struct node *next;
} Node;

Node *head = NULL;

// 1. Insert at Beginning
void insBeg(int val) {
  Node *newN = (Node *)malloc(sizeof(Node));
  newN->id = val;
  newN->prev = NULL;
  newN->next = head;

  if (head != NULL) {
    head->prev = newN;
  }
  head = newN;
  printf("Song %d added at start.\n", val);
}

// 2. Insert at End
void insEnd(int val) {
  Node *newN = (Node *)malloc(sizeof(Node));
  newN->id = val;
  newN->next = NULL;

  if (head == NULL) {
    newN->prev = NULL;
    head = newN;
  } else {
    Node *temp = head;
    while (temp->next)
      temp = temp->next;
    temp->next = newN;
    newN->prev = temp;
  }
  printf("Song %d added at end.\n", val);
}

// 3. Delete by Song ID
void deleteID(int val) {
  if (head == NULL) {
    printf("Playlist is empty!\n");
    return;
  }

  Node *temp = head;
  // Find the node with the given ID
  while (temp != NULL && temp->id != val) {
    temp = temp->next;
  }

  if (temp == NULL) {
    printf("Song ID %d not found.\n", val);
    return;
  }

  // If node to be deleted is head
  if (temp == head) {
    head = temp->next;
  }

  // If there is a next node, update its prev pointer
  if (temp->next != NULL) {
    temp->next->prev = temp->prev;
  }

  // If there is a prev node, update its next pointer
  if (temp->prev != NULL) {
    temp->prev->next = temp->next;
  }

  free(temp);
  printf("Song %d removed from playlist.\n", val);
}

// 4. Display Forward
void dispForward() {
  Node *temp = head;
  printf("Playlist (Forward): ");
  while (temp) {
    printf("%d <-> ", temp->id);
    temp = temp->next;
  }
  printf("NULL\n");
}

// 5. Display Backward
void dispBackward() {
  if (head == NULL)
    return;
  Node *temp = head;
  // Go to the last node
  while (temp->next)
    temp = temp->next;

  printf("Playlist (Backward): ");
  while (temp) {
    printf("%d <-> ", temp->id);
    temp = temp->prev; // Move backward using prev pointer
  }
  printf("NULL\n");
}

// 6. Search for Song ID
void search(int val) {
  Node *temp = head;
  int pos = 1;
  while (temp) {
    if (temp->id == val) {
      printf("Song %d found at position %d.\n", val, pos);
      return;
    }
    temp = temp->next;
    pos++;
  }
  printf("Song %d not found.\n", val);
}

int main() {
  int ch, val;
  while (1) {
    printf("\n--- Playlist Menu ---\n");
    printf("1.InsBeg 2.InsEnd 3.DeleteID 4.DispForward 5.DispBackward 6.Search "
           "7.Exit\nChoice: ");
    scanf("%d", &ch);
    switch (ch) {
    case 1:
      printf("ID: ");
      scanf("%d", &val);
      insBeg(val);
      break;
    case 2:
      printf("ID: ");
      scanf("%d", &val);
      insEnd(val);
      break;
    case 3:
      printf("ID to delete: ");
      scanf("%d", &val);
      deleteID(val);
      break;
    case 4:
      dispForward();
      break;
    case 5:
      dispBackward();
      break;
    case 6:
      printf("ID to search: ");
      scanf("%d", &val);
      search(val);
      break;
    case 7:
      exit(0);
    }
  }
  return 0;
}

LAB 7: Binary Search

#include <stdio.h>

void binarySearch(int arr[], int n, int key, int order) {
  int low = 0, high = n - 1, mid;
  int found = 0;

  while (low <= high) {
    mid = (low + high) / 2;

    if (arr[mid] == key) {
      printf("\nElement '%d' found at position %d\n", arr[mid], mid);
      printf("Low: %d, High: %d", low, high);
      return;
    }

    if ((order == 1 && key < arr[mid]) || (order == 2 && key > arr[mid])) {
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  printf("Element not found.\n");
  printf("Low: %d, High: %d", low, high);
}

int main() {
  int arr[10], n, key, order;

  printf("1. Ascending\n");
  printf("2. Descending\n");
  printf("Enter the order: ");
  scanf("%d", &order);

  printf("Enter the number of elements: ");
  scanf("%d", &n);
  printf("Enter %d elements: ", n);
  for (int i = 0; i < n; i++) {
    scanf("%d", &arr[i]);
  }

  printf("Enter search key: ");
  scanf("%d", &key);

  binarySearch(arr, n, key, order);

  return 0;
}

LAB 8: Insertion Sort

#include <stdio.h>

void insertionSort(int arr[], int n) {
  int i, j, key, shifts = 0;

  for (i = 1; i < n; i++) {
    key = arr[i];
    j = i - 1;

    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j = j - 1;
      shifts++;
    }
    arr[j + 1] = key;

    printf("\nPass %d: ", i);
    for (int k = 0; k < n; k++) {
      printf("%d ", arr[k]);
    }
  }
  printf("\nTotal passes: %d", n - 1);
  printf("\nTotal shifts: %d\n", shifts);
}

int main() {
  int arr[10], n;

  printf("Enter number of elements: ");
  scanf("%d", &n);

  printf("Enter %d values: ", n);
  for (int i = 0; i < n; i++) {
    scanf("%d", &arr[i]);
  }

  printf("\nOriginal Array: ");
  for (int i = 0; i < n; i++) {
    printf("%d ", arr[i]);
  }

  insertionSort(arr, n);

  return 0;
}

LAB 9: Merge Sort

#include <stdio.h>

int totalComparisons = 0;
int totalMerges = 0;

void display(int arr[], int n) {
  for (int i = 0; i < n; i++)
    printf("%d ", arr[i]);
  printf("\n");
}

void merge(int arr[], int low, int mid, int high, int n, int choice) {
  int i = low, j = mid + 1, k = 0;
  int temp[high - low + 1];

  printf("\nMerging range [%d to %d]: ", low, high);

  while (i <= mid && j <= high) {
    totalComparisons++;
    int condition;

    if (choice == 1) // Ascending
      condition = (arr[i] <= arr[j]);
    else // Descending
      condition = (arr[i] >= arr[j]);

    if (condition) {
      temp[k++] = arr[i++];
    } else {
      temp[k++] = arr[j++];
    }
  }

  while (i <= mid)
    temp[k++] = arr[i++];
  while (j <= high)
    temp[k++] = arr[j++];

  // Copy temp back to original array
  for (i = low, k = 0; i <= high; i++, k++) {
    arr[i] = temp[k];
  }

  totalMerges++;
  display(arr, n);
}

void mergeSort(int arr[], int low, int high, int n, int choice) {
  if (low < high) {
    int mid = low + (high - low) / 2;

    mergeSort(arr, low, mid, n, choice);
    mergeSort(arr, mid + 1, high, n, choice);

    merge(arr, low, mid, high, n, choice);
  }
}

int main() {
  int n, arr[50], choice;

  printf("1. Ascending\n2. Descending\nEnter choice: ");
  scanf("%d", &choice);

  printf("Enter number of elements: ");
  scanf("%d", &n);

  printf("Enter %d elements: ", n);
  for (int i = 0; i < n; i++)
    scanf("%d", &arr[i]);

  printf("\nInitial Array: ");
  display(arr, n);

  mergeSort(arr, 0, n - 1, n, choice);

  printf("\n--- Final Statistics ---");
  printf("\nTotal Comparisons: %d", totalComparisons);
  printf("\nTotal Merge Operations: %d", totalMerges);

  printf("\n\nSorted Array: ");
  display(arr, n);

  return 0;
}

LAB 10: Quick Sort

#include <stdio.h>

int comparisons = 0;
int swaps = 0;
int recursiveCalls = 0;

void swap(int *a, int *b) {
  int temp = *a;
  *a = *b;
  *b = temp;
  swaps++;
}

void display(int arr[], int n) {
  for (int i = 0; i < n; i++)
    printf("%d ", arr[i]);
  printf("\n");
}

int partition(int arr[], int low, int high, int n) {
  int pivot = arr[high]; // Choosing the last element as pivot
  printf("\nChosen Pivot: %d", pivot);

  int i = (low - 1);

  for (int j = low; j <= high - 1; j++) {
    comparisons++;
    if (arr[j] < pivot) {
      i++;
      swap(&arr[i], &arr[j]);
    }
  }
  swap(&arr[i + 1], &arr[high]);

  printf("\nArray after partition: ");
  display(arr, n);

  return (i + 1);
}

void quickSort(int arr[], int low, int high, int n) {
  if (low < high) {
    recursiveCalls++;
    int pi = partition(arr, low, high, n);

    quickSort(arr, low, pi - 1, n);
    quickSort(arr, pi + 1, high, n);
  }
}

int main() {
  int n, arr[50];

  printf("Enter number of elements: ");
  scanf("%d", &n);

  printf("Enter %d integers: ", n);
  for (int i = 0; i < n; i++)
    scanf("%d", &arr[i]);

  printf("\nOriginal Array: ");
  display(arr, n);

  quickSort(arr, 0, n - 1, n);

  printf("\nTotal Comparisons: %d", comparisons);
  printf("\nTotal Swaps: %d", swaps);
  printf("\nTotal Recursive Calls: %d", recursiveCalls);

  printf("\n\nSorted Array: ");
  display(arr, n);

  return 0;
}