C++ Program To Sort Linked List In Ascending Order

Sorting a linked list is a fundamental operation in data structures, crucial for organizing dynamic data efficiently. In this article, you will learn various C++ programming approaches to sort a singly linked list in ascending order.

Problem Statement

Linked lists, unlike arrays, store elements non-contiguously, making traditional array-based sorting algorithms like quicksort or heapsort challenging due to the lack of random access. The problem is to rearrange the nodes of a linked list such that their data values are in ascending order, modifying the pointers rather than just swapping data, for optimal performance and true linked list manipulation. This is important for maintaining ordered data collections in scenarios where elements are frequently added or removed, such as priority queues or task schedulers.

Example

Consider an unsorted linked list: 5 -> 2 -> 8 -> 1 -> 4 -> NULL. After sorting it in ascending order, the list should become: 1 -> 2 -> 4 -> 5 -> 8 -> NULL.

Background & Knowledge Prerequisites

To understand the solutions presented, readers should have a basic understanding of:

• C++ fundamental syntax and concepts (variables, loops, functions).
• Pointers and dynamic memory allocation (new, delete).
• The concept of a singly linked list (nodes, head, next pointers).
• Basic algorithm analysis (time and space complexity).

No special setup is required beyond a standard C++ compiler (like g++).

Use Cases

Sorting a linked list is valuable in several practical scenarios:

• Priority Queues: Maintaining a sorted list of tasks or items based on their priority, where the highest priority item is always at the head.
• Task Scheduling: Arranging tasks in an operating system or application based on execution time, deadline, or resource requirements.
• Database Indexing: While often using more complex structures, a sorted linked list can form a component of simpler in-memory indexing systems.
• Managing Ordered Data: Any application that requires dynamic insertion and deletion of elements while maintaining sorted order, such as a contact list sorted by name or a product catalog sorted by price.
• Undo/Redo Functionality: Storing a history of actions in a sorted manner based on timestamps, allowing for efficient navigation through states.

Solution Approaches

Approach 1: Insertion Sort (by changing links)

This approach iterates through the linked list, taking one element at a time and inserting it into its correct position within the already sorted part of the list. This involves manipulating the next pointers to achieve the sort.

• One-line summary: Build a sorted list by iteratively inserting elements from the unsorted list into their correct position in the sorted sublist.

// Linked List Insertion Sort
#include <iostream>
#include <cstddef> // For NULL

using namespace std;

// Node structure for the linked list
struct Node {
    int data;
    Node* next;

    Node(int val) : data(val), next(NULL) {}
};

// Function to insert a new node into a sorted list
Node* sortedInsert(Node* sortedHead, Node* newNode) {
    // Case 1: If sorted list is empty or newNode's data is smaller than head
    if (sortedHead == NULL || newNode->data <= sortedHead->data) {
        newNode->next = sortedHead;
        return newNode;
    } else {
        // Case 2: Traverse the sorted list to find the correct position
        Node* current = sortedHead;
        while (current->next != NULL && current->next->data < newNode->data) {
            current = current->next;
        }
        newNode->next = current->next;
        current->next = newNode;
        return sortedHead; // Head remains the same
    }
}

// Function to sort a linked list using Insertion Sort
Node* insertionSort(Node* head) {
    Node* sortedHead = NULL; // Head of the sorted list
    Node* current = head;    // Pointer to traverse the original list

    while (current != NULL) {
        Node* nextNode = current->next; // Store next node before modifying current
        sortedHead = sortedInsert(sortedHead, current);
        current = nextNode;
    }
    return sortedHead;
}

// Function to print the linked list
void printList(Node* head) {
    Node* temp = head;
    while (temp != NULL) {
        cout << temp->data << " -> ";
        temp = temp->next;
    }
    cout << "NULL" << endl;
}

int main() {
    // Step 1: Create an unsorted linked list
    Node* head = new Node(5);
    head->next = new Node(2);
    head->next->next = new Node(8);
    head->next->next->next = new Node(1);
    head->next->next->next->next = new Node(4);

    cout << "Original list: ";
    printList(head);

    // Step 2: Sort the linked list using Insertion Sort
    head = insertionSort(head);

    cout << "Sorted list (Insertion Sort): ";
    printList(head);

    // Step 3: Clean up memory (Important for linked lists)
    while (head != NULL) {
        Node* temp = head;
        head = head->next;
        delete temp;
    }

    return 0;
}

Run

• Sample output:

Original list: 5 -> 2 -> 8 -> 1 -> 4 -> NULL
    Sorted list (Insertion Sort): 1 -> 2 -> 4 -> 5 -> 8 -> NULL

• Stepwise explanation:

1. Define a Node structure with data and a next pointer.
2. Implement sortedInsert(Node* sortedHead, Node* newNode): This helper function takes a new node and inserts it into its correct position in an already sorted linked list, returning the (possibly new) head of the sorted list.
3. Implement insertionSort(Node* head):

• Initialize sortedHead to NULL. This will be the head of our new sorted list.
• Iterate through the original head list using a current pointer.
• In each iteration, take current (which is a node from the original list) and call sortedInsert to place it into the sortedHead list.
• Advance current to the next node in the original list.
• After processing all nodes, sortedHead will point to the head of the completely sorted list.

1. In main, create an example unsorted list, print it, sort it using insertionSort, and print the sorted list.
2. Include memory cleanup to prevent leaks.

Approach 2: Merge Sort (by changing links)

Merge Sort is a divide-and-conquer algorithm that is highly efficient for linked lists. It works by recursively dividing the list into two halves, sorting each half, and then merging the sorted halves.

• One-line summary: Recursively divide the linked list into sublists until each contains only one element, then repeatedly merge the sublists to produce new sorted sublists until there is only one sorted list remaining.

// Linked List Merge Sort
#include <iostream>
#include <cstddef> // For NULL

using namespace std;

// Node structure for the linked list
struct Node {
    int data;
    Node* next;

    Node(int val) : data(val), next(NULL) {}
};

// Function to merge two sorted linked lists
Node* mergeTwoSortedLists(Node* list1, Node* list2) {
    // Base cases
    if (list1 == NULL) return list2;
    if (list2 == NULL) return list1;

    Node* result = NULL;

    // Pick either list1 or list2, and recurse
    if (list1->data <= list2->data) {
        result = list1;
        result->next = mergeTwoSortedLists(list1->next, list2);
    } else {
        result = list2;
        result->next = mergeTwoSortedLists(list1, list2->next);
    }
    return result;
}

// Function to find the middle of a linked list
Node* getMiddle(Node* head) {
    if (head == NULL) return head;

    Node* slow = head;
    Node* fast = head->next; // Start fast one ahead

    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

// Function to sort a linked list using Merge Sort
Node* mergeSort(Node* head) {
    // Base case: if head is NULL or has only one node
    if (head == NULL || head->next == NULL) {
        return head;
    }

    // Step 1: Find the middle of the list to divide it into two halves
    Node* middle = getMiddle(head);
    Node* nextOfMiddle = middle->next; // Store the head of the second half

    // Step 2: Break the link to split the list into two halves
    middle->next = NULL;

    // Step 3: Recursively sort the two halves
    Node* left = mergeSort(head);
    Node* right = mergeSort(nextOfMiddle);

    // Step 4: Merge the sorted halves
    Node* sortedList = mergeTwoSortedLists(left, right);

    return sortedList;
}

// Function to print the linked list
void printList(Node* head) {
    Node* temp = head;
    while (temp != NULL) {
        cout << temp->data << " -> ";
        temp = temp->next;
    }
    cout << "NULL" << endl;
}

int main() {
    // Step 1: Create an unsorted linked list
    Node* head = new Node(5);
    head->next = new Node(2);
    head->next->next = new Node(8);
    head->next->next->next = new Node(1);
    head->next->next->next->next = new Node(4);
    head->next->next->next->next->next = new Node(9); // Added one more for odd length

    cout << "Original list: ";
    printList(head);

    // Step 2: Sort the linked list using Merge Sort
    head = mergeSort(head);

    cout << "Sorted list (Merge Sort): ";
    printList(head);

    // Step 3: Clean up memory
    while (head != NULL) {
        Node* temp = head;
        head = head->next;
        delete temp;
    }

    return 0;
}

Run

• Sample output:

Original list: 5 -> 2 -> 8 -> 1 -> 4 -> 9 -> NULL
    Sorted list (Merge Sort): 1 -> 2 -> 4 -> 5 -> 8 -> 9 -> NULL

• Stepwise explanation:

1. Define a Node structure.
2. Implement mergeTwoSortedLists(Node* list1, Node* list2): This recursive helper function takes two already sorted linked lists and merges them into a single sorted list.
3. Implement getMiddle(Node* head): Uses the slow and fast pointer technique to find the middle node of a linked list. The slow pointer moves one step at a time, while fast moves two steps. When fast reaches the end, slow is at the middle.
4. Implement mergeSort(Node* head):

• Base Case: If the list is empty or has only one node, it's already sorted, so return head.
• Divide: Find the middle of the list using getMiddle. Split the list into two halves by setting middle->next = NULL.
• Conquer: Recursively call mergeSort on both halves (left and right).
• Combine: Call mergeTwoSortedLists to merge the sorted left and right halves into a single sorted list.
• Return the head of the newly merged, sorted list.

1. In main, create an example unsorted list, print it, sort it using mergeSort, and print the sorted list.
2. Include memory cleanup.

Conclusion

Sorting a linked list efficiently is a classic problem in data structures. While simple approaches like bubble sort can be adapted, algorithms such as Insertion Sort and Merge Sort provide more robust and performant solutions by directly manipulating node pointers. Insertion Sort is intuitive for smaller lists, while Merge Sort offers superior average and worst-case time complexity, making it ideal for larger datasets.

Summary

• Linked lists require specific sorting algorithms due to their non-contiguous memory allocation and lack of random access.
• Insertion Sort for linked lists works by iteratively building a sorted sublist. It has a time complexity of O(N^2) but a space complexity of O(1).
• Merge Sort for linked lists uses a divide-and-conquer strategy, splitting the list, sorting halves recursively, and then merging them. It achieves an optimal time complexity of O(N log N) and space complexity of O(log N) due to the recursion stack.
• Choosing the right sorting algorithm depends on factors like list size, required performance, and implementation complexity.
• Always remember to deallocate memory after dynamic linked list operations to prevent memory leaks.