Example: Linked List Bubble Sort in C

// Linked List Bubble Sort
#include <stdio.h>
#include <stdlib.h> // For malloc

// Define the structure for a linked list node
struct Node {
    int data;
    struct Node* next;
};

// Function to create a new node
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("Memory allocation failed!\n");
        exit(EXIT_FAILURE);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Function to insert a node at the end of the list
void insertEnd(struct Node** head_ref, int data) {
    struct Node* newNode = createNode(data);
    if (*head_ref == NULL) {
        *head_ref = newNode;
        return;
    }
    struct Node* last = *head_ref;
    while (last->next != NULL) {
        last = last->next;
    }
    last->next = newNode;
}

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

// Function to sort the linked list using Bubble Sort (by swapping data)
void bubbleSortLinkedList(struct Node* head) {
    int swapped;
    struct Node* ptr1;
    struct Node* lptr = NULL;

    // Check for empty list
    if (head == NULL)
        return;

    do {
        swapped = 0;
        ptr1 = head;

        while (ptr1->next != lptr) {
            if (ptr1->data > ptr1->next->data) {
                // Swap data
                int temp = ptr1->data;
                ptr1->data = ptr1->next->data;
                ptr1->next->data = temp;
                swapped = 1;
            }
            ptr1 = ptr1->next;
        }
        lptr = ptr1; // Mark current end of sorted portion
    } while (swapped);
}

int main() {
    // Step 1: Initialize an empty linked list
    struct Node* head = NULL;

    // Step 2: Insert elements into the list
    insertEnd(&head, 10);
    insertEnd(&head, 30);
    insertEnd(&head, 20);
    insertEnd(&head, 50);
    insertEnd(&head, 40);

    // Step 3: Print the original list
    printf("Original list: ");
    printList(head);

    // Step 4: Sort the linked list using Bubble Sort
    bubbleSortLinkedList(head);

    // Step 5: Print the sorted list
    printf("Sorted list (Bubble Sort): ");
    printList(head);

    // Step 6: Free allocated memory (important to prevent memory leaks)
    struct Node* current = head;
    struct Node* next_node;
    while (current != NULL) {
        next_node = current->next;
        free(current);
        current = next_node;
    }
    head = NULL; // Prevent dangling pointer

    return 0;
}