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

// Create a node
struct Node {
  int data;
  struct Node* next;
};

// Insert at the beginning
void insertAtBeginning(struct Node** head_ref, int new_data) {
  // Allocate memory to a node
  struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

  // Insert the data
  new_node->data = new_data;

  // Set the next pointer of the new node to the current head
  new_node->next = (*head_ref);

  // Move head to the new node
  (*head_ref) = new_node;
}

// Insert a node after a given node
void insertAfter(struct Node* prev_node, int new_data) {
  // Check if the previous node is NULL
  if (prev_node == NULL) {
    printf("The given previous node cannot be NULL");
    return;
  }

  // Allocate memory to a new node
  struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

  // Insert the data
  new_node->data = new_data;

  // Adjust the pointers to insert the new node
  new_node->next = prev_node->next;
  prev_node->next = new_node;
}

// Insert at the end
void insertAtEnd(struct Node** head_ref, int new_data) {
  // Allocate memory to a new node
  struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

  // Assign the data to the new node
  new_node->data = new_data;

  // Set the next pointer of the new node to NULL
  new_node->next = NULL;

  // Check if the linked list is empty
  if (*head_ref == NULL) {
    // If the linked list is empty, make the new node the head
    *head_ref = new_node;
    return;
  }

  // Traverse to the last node
  struct Node* last = *head_ref;
  while (last->next != NULL)
    last = last->next;

  // Set the next pointer of the last node to the new node
  last->next = new_node;
}

// Delete a node
void deleteNode(struct Node** head_ref, int key) {
  // Store the head node
  struct Node* temp = *head_ref;
  struct Node* prev = NULL;

  // Check if the head node itself holds the key
  if (temp != NULL && temp->data == key) {
    // Change the head
    *head_ref = temp->next;

    // Free the old head
    free(temp);
    return;
  }

  // Search for the key to be deleted
  while (temp != NULL && temp->data != key) {
    prev = temp;
    temp = temp->next;
  }

  // If the key was not present in the linked list
  if (temp == NULL)
    return;

  // Unlink the node from the linked list
  prev->next = temp->next;

  // Free the memory allocated for the node
  free(temp);
}

// Search for a node
int searchNode(struct Node** head_ref, int key) {
  // Start from the head node
  struct Node* current = *head_ref;

  // Traverse the linked list
  while (current != NULL) {
    // If the key is found, return 1
    if (current->data == key)
      return 1;

    // Move to the next node
    current = current->next;
  }

  // Key not found
  return 0;
}

// Sort the linked list in ascending order
void sortLinkedList(struct Node** head_ref) {
  // Initialize current and index nodes
  struct Node* current = *head_ref;
  struct Node* index = NULL;

  // Temporary variable for swapping data
  int temp;

  // Check if the linked list is empty or has only one node
  if (head_ref == NULL)
    return;

  // Perform bubble sort on the linked list
  while (current != NULL) {
    // Set the index node to the node next to the current node
    index = current->next;

    while (index != NULL) {
      // Swap the data if the current node's data is greater than the index node's data
      if (current->data > index->data) {
        temp = current->data;
        current->data = index->data;
        index->data = temp;
      }

      // Move to the next index node
      index = index->next;
    }

    // Move to the next current node
    current = current->next;
  }
}

// Print the linked list
void printList(struct Node* node) {
  while (node != NULL) {
    printf(" %d ", node->data);
    node = node->next;
  }
}

// Driver program
int main() {
  // Initialize the head node
  struct Node* head = NULL;

  // Insert nodes into the linked list
  insertAtEnd(&head, 1);
  insertAtBeginning(&head, 2);
  insertAtBeginning(&head, 3);
  insertAtEnd(&head, 4);
  insertAfter(head->next, 5);

  printf("Linked list: ");
  printList(head);

  printf("\nAfter deleting an element: ");
  deleteNode(&head, 3);
  printList(head);

  int item_to_find = 3;
  if (searchNode(&head, item_to_find)) {
    printf("\n%d is found", item_to_find);
  } else {
    printf("\n%d is not found", item_to_find);
  }

  // Sort the linked list
  sortLinkedList(&head);
  printf("\nSorted List: ");
  printList(head);

  return 0;
}