C Program To Sort Linked List In Ascending Order
ADVERTISEMENTS
A linked list is a fundamental data structure, but its dynamic nature can make operations like sorting seem challenging. In this article, you will learn how to sort a singly linked list in ascending order using C programming, exploring both simpler and more efficient approaches.
Problem Statement
A linked list consists of a sequence of nodes, where each node contains data and a pointer to the next node in the sequence. Unlike arrays, linked lists do not store elements in contiguous memory locations, making direct indexing impossible. The problem at hand is to reorder the nodes of an unsorted singly linked list such that their data elements are arranged in ascending numerical order. This operation is crucial for efficient data retrieval, database management, and maintaining ordered collections in various applications.
Example
Consider an unsorted linked list:
10 -> 30 -> 20 -> 50 -> 40 -> NULL
After sorting this linked list in ascending order, it should look like this:
10 -> 20 -> 30 -> 40 -> 50 -> NULL
Background & Knowledge Prerequisites
To effectively understand and implement linked list sorting, readers should be familiar with:
- C Programming Basics: Understanding of variables, loops (
for,while), conditional statements (if-else), functions, and basic input/output. - Pointers: A strong grasp of pointer declaration, dereferencing, and pointer arithmetic (though less critical for basic linked list operations than for arrays).
- Dynamic Memory Allocation: Knowledge of
malloc()andfree()for allocating and deallocating memory at runtime. - Linked List Data Structure:
- Defining a
structfor a node (data and next pointer). - Creating new nodes.
- Traversing a linked list.
- Inserting and deleting nodes (basic understanding).
Use Cases or Case Studies
Sorting linked lists is a common operation with various practical applications:
- Database Record Management: When records are stored as nodes in a linked list, sorting them by ID, name, or date allows for faster searches and structured presentation.
- Operating System Process Scheduling: Processes might be organized in a linked list and sorted by priority or arrival time to determine execution order.
- Music Playlists or File Explorers: Maintaining an ordered list of songs by title, artist, or files by name, type, or size.
- Implementing Other Data Structures: Building ordered sets, priority queues, or certain types of trees often requires elements to be sorted.
- Event Scheduling Systems: Sorting events by their timestamps to process them chronologically.
Solution Approaches
We will explore two distinct approaches to sort a singly linked list: a simpler Bubble Sort that swaps data within nodes, and a more efficient Merge Sort that manipulates node pointers.
Approach 1: Bubble Sort (Swapping Node Data)
Bubble Sort is one of the simplest sorting algorithms. For a linked list, it involves repeatedly stepping through the list, comparing adjacent node data, and swapping them if they are in the wrong order. This approach modifies the data fields of the nodes, leaving the node structure itself unchanged.
One-line summary: Compares adjacent node data elements and swaps them until the list is sorted.
// 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;
}Sample Output:
Original list: 10 -> 30 -> 20 -> 50 -> 40 -> NULL
Sorted list (Bubble Sort): 10 -> 20 -> 30 -> 40 -> 50 -> NULLStepwise explanation:
- Node Structure: A
struct Nodeis defined with an integerdataand anextpointer to anotherNode. - Helper Functions:
createNode,insertEnd, andprintListare provided to build and display the linked list. bubbleSortLinkedList(struct Node* head):
- It uses two nested loops (effectively,
do-whilefor outer pass andwhilefor inner pass) to iterate through the list. -
swappedflag tracks if any swaps occurred in a pass. If no swaps, the list is sorted. -
lptrpoints to the last node that has already been placed in its correct position, optimizing subsequent passes. - In the inner loop,
ptr1traverses from the beginning tolptr. - Adjacent node data (
ptr1->dataandptr1->next->data) are compared. Ifptr1->datais greater, theirdatavalues are swapped using a temporary variable. - The process repeats until a full pass occurs with no swaps.
Approach 2: Merge Sort (Node Manipulation)
Merge Sort is a more efficient, divide-and-conquer sorting algorithm. For linked lists, it's particularly well-suited because it sorts by rearranging next pointers rather than swapping data, which can be more efficient in terms of memory operations. It works by dividing the list into two halves, recursively sorting each half, and then merging the sorted halves.
One-line summary: Divides the list into two halves, recursively sorts them, then merges the two sorted halves into a single sorted list by adjusting pointers.
// Linked List Merge 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 split the list into two halves.
// If the list has an odd number of nodes, the first list will have one more node.
void splitList(struct Node* source, struct Node** frontRef, struct Node** backRef) {
struct Node* fast;
struct Node* slow;
slow = source;
fast = source->next; // Start fast one step ahead
// Advance 'fast' by two nodes, and 'slow' by one node
while (fast != NULL) {
fast = fast->next;
if (fast != NULL) {
slow = slow->next;
fast = fast->next;
}
}
// 'slow' is now at the middle, so split it in two.
*frontRef = source;
*backRef = slow->next;
slow->next = NULL; // Terminate the first half
}
// Function to merge two sorted linked lists
struct Node* mergeSortedLists(struct Node* a, struct Node* b) {
struct Node* result = NULL;
// Base cases
if (a == NULL)
return b;
if (b == NULL)
return a;
// Pick either 'a' or 'b', and recur
if (a->data <= b->data) {
result = a;
result->next = mergeSortedLists(a->next, b);
} else {
result = b;
result->next = mergeSortedLists(a, b->next);
}
return result;
}
// Function to sort a linked list using Merge Sort
void mergeSortLinkedList(struct Node** headRef) {
struct Node* head = *headRef;
struct Node* a;
struct Node* b;
// Base case : if head is NULL or has only one node
if ((head == NULL) || (head->next == NULL)) {
return;
}
// Split head into 'a' and 'b' sublists
splitList(head, &a, &b);
// Recursively sort the sublists
mergeSortLinkedList(&a);
mergeSortLinkedList(&b);
// Merge the two sorted sublists
*headRef = mergeSortedLists(a, b);
}
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);
insertEnd(&head, 5); // Add an extra element for more robust testing
// Step 3: Print the original list
printf("Original list: ");
printList(head);
// Step 4: Sort the linked list using Merge Sort
mergeSortLinkedList(&head);
// Step 5: Print the sorted list
printf("Sorted list (Merge Sort): ");
printList(head);
// Step 6: Free allocated memory
struct Node* current = head;
struct Node* next_node;
while (current != NULL) {
next_node = current->next;
free(current);
current = next_node;
}
head = NULL;
return 0;
}Sample Output:
Original list: 10 -> 30 -> 20 -> 50 -> 40 -> 5 -> NULL
Sorted list (Merge Sort): 5 -> 10 -> 20 -> 30 -> 40 -> 50 -> NULLStepwise explanation:
- Node Structure & Helper Functions: Similar
Nodestructure and basic list operations (createNode,insertEnd,printList) are used. mergeSortLinkedList(struct NodeheadRef):** This is the main recursive function.
- Base Case: If the list is empty or has only one node, it's already sorted, so return.
- Splitting: It calls
splitListto divide the current list (head) into two halves,aandb.splitListuses afastandslowpointer approach to find the middle of the list. - Recursive Sort: It recursively calls
mergeSortLinkedListon bothaandbto sort them independently. - Merging: Once
aandbare sorted, it callsmergeSortedListsto combine them into a single sorted list, and the head of this merged list is assigned back to*headRef.
splitList(struct Node* source, struct NodefrontRef, struct Node backRef):
- Takes the source list and two pointers to store the heads of the two resulting sublists.
- Uses two pointers,
slowandfast.slowmoves one step at a time, andfastmoves two steps. - When
fastreaches the end of the list,slowwill be at the middle. - The list is split by setting
slow->next = NULL, separating the first half from the second.
mergeSortedLists(struct Node* a, struct Node* b):
- Takes two already sorted linked lists (
aandb) as input. - Base Cases: If one list is empty, return the other.
- Recursive Merging: Compares the data of the current nodes
aandb. The node with the smaller data becomes theresult's head, and itsnextpointer is set to the result of recursively merging the rest of its list with the other list. This efficiently builds the merged list by adjustingnextpointers.
Conclusion
Sorting a linked list is a common problem in computer science with various solutions. We've explored two key methods:
- Bubble Sort (Data Swapping): Simple to implement but generally inefficient for large lists due to its
O(n^2)time complexity. It works by swappingdatavalues within nodes. - Merge Sort (Node Manipulation): A more robust and efficient algorithm for linked lists, offering
O(n log n)time complexity. It sorts by carefully rearrangingnextpointers, which is often preferred for linked lists as it avoids costly data movements.
While Bubble Sort might be easier to grasp for beginners, Merge Sort is the recommended approach for practical applications involving linked lists due to its superior performance characteristics, especially as the list size grows.
Summary
- A linked list is a sequence of data elements, each connected to the next via a pointer.
- Sorting a linked list involves reordering its nodes based on their data values (e.g., in ascending order).
- Bubble Sort can be applied by repeatedly comparing and swapping data in adjacent nodes. It's conceptually simple but less efficient (
O(n^2)). - Merge Sort is a highly efficient algorithm (
O(n log n)) for linked lists. It works by dividing the list, recursively sorting sublists, and then merging them by adjustingnextpointers. - Merge Sort is generally preferred for linked list sorting due to its efficiency and the nature of pointer manipulation being less costly than data swapping for large records.
- Understanding pointers, dynamic memory allocation, and recursion are crucial prerequisites for implementing advanced linked list sorting algorithms like Merge Sort.