Program for sort a linked list |Data Structure in C|

Introduction

     Linked lists provide a dynamic and flexible data structure for storing and managing data. In this blog post, we delve into a C program that not only creates a linked list but also employs the Bubble Sort algorithm to arrange the elements in ascending order. This exploration combines linked list operations and sorting algorithms, offering insights into practical programming scenarios.  

Code

    
     
    #include<stdio.h>
    #include<alloc.h>
    
    void main() {
        struct node {
            int data;
            struct node *next;
        } *start = NULL;
    
        struct node *newnode, *temp, *q, *r;
        char ch;
        int n, i, j, current;
        clrscr();
    
        // Linked List Creation
        do {
            newnode = (struct node*)malloc(sizeof(struct node));
            printf("\nEnter the node data: ");
            scanf("%d", &newnode->data);
    
            if (start == NULL) {
                start = newnode;
                start->next = NULL;
            } else {
                newnode->next = start;
                start = newnode;
            }
    
            printf("Add more (y/n)? ");
            ch = getch();
        } while ((ch == 'y') || (ch == 'Y'));
    
        // Display Original Linked List
        printf("\nThe linked list is\n");
        for (temp = start, n = 1; temp != NULL; temp = temp->next, n++)
            printf("%d->", temp->data);
        printf("NULL");
    
        n--;
    
        // Bubble Sort Algorithm
        for (i = 0; i < n - 1; i++) {
            q = start;
            r = q->next;
    
            for (j = 0; j < (n - i - 1); j++) {
                if (q->data > r->data) {
                    current = q->data;
                    q->data = r->data;
                    r->data = current;
                }
                q = q->next;
                r = r->next;
            }
        }
    
        // Display Sorted Linked List
        printf("\nThe sorted linked list is\n");
        for (temp = start; temp != NULL; temp = temp->next)
            printf("%d->", temp->data);
        printf("NULL");
    
        getch();
    }
       
     

Output

    Enter the node data: 5
    Add more (y/n)? y

    Enter the node data: 8
    Add more (y/n)? y

    Enter the node data: 3
    Add more (y/n)? n

    The linked list is
    3->8->5->NULL

    The sorted linked list is
    3->5->8->NULL
       

Explanation

1. Header Files:

The program includes the standard input/output header <stdio.h> and the memory allocation header <alloc.h>.

2. Structure Definition:

The node structure represents each element in the linked list. It contains an integer data and a pointer next to the next node.

3. Main Function:

The main function serves as the program's entry point.

4. Linked List Creation:

Users input elements to be added to the linked list.

A new node is created and added to the beginning of the list.

5. Bubble Sort Algorithm:

The Bubble Sort algorithm is employed to sort the linked list in ascending order.

Nested loops traverse the list, comparing and swapping adjacent elements as needed.

6. Display Original and Sorted Linked Lists:

The program displays the original linked list before sorting.

Conclusion

     This C program demonstrates the synergy between linked list operations and the Bubble Sort algorithm, providing a practical example of data manipulation and sorting. Users can input elements, witness the creation of a linked list, and observe the sorting process. Feel free to run the program with different sets of elements to see how Bubble Sort efficiently organizes the linked list in ascending order. This example serves as a valuable introduction to sorting algorithms applied to linked lists. Happy coding!