Bubble Sort for Linked List by Swapping nodes

Last Updated : 31 Aug, 2024

Given a singly linked list, sort it using bubble sort by swapping nodes.

Examples:

Input: 5 -> 1 -> 32 -> 10 -> 78
Output: 1 -> 5 -> 10 -> 32 -> 78

Input: 20 -> 4 -> 3
Output: 3 -> 4 -> 20

Approach:

To apply Bubble Sort to a linked list, we need to traverse the list multiple times, comparing adjacent nodes and swapping their positions by adjusting their links if the current node’s data is greater than the next. During each pass, the largest unsorted element moves to its correct position at the end of the list. This process continues until no more swaps are needed, indicating that the list is sorted.

Below is the implementation of the above approach:

C++

// C++ program to sort Linked List 
// using Bubble Sort

#include <iostream>
using namespace std;

class Node {
  public:
    int data;
    Node *next;
    Node(int x) {
        data = x;
        next = nullptr;
    }
};

// Function to get the length
// of the linked list
int getLength(Node *head) {
    int len = 0;
    Node *curr = head;
    while (curr != nullptr) {
        len++;
        curr = curr->next;
    }
    return len;
}

// Function to perform bubble sort on 
// the linked list
Node *bubbleSort(Node *head) {
    Node *currNode = head;
    int len = getLength(head);
    int itr = 0;
    bool swapped;

    // Iterating over the whole linked list
    while (itr < len) {
        Node *traverseNode = head;
        Node *prevNode = head;
        swapped = false;

        while (traverseNode->next) {

            // Temporary pointer to store the next
            // pointer of traverseNode
            Node *ptr = traverseNode->next;
            if (traverseNode->data > ptr->data) {
                swapped = true;
                if (traverseNode == head) {

                    // Performing swap operations and
                    // updating the head of the linked list
                    traverseNode->next = ptr->next;
                    ptr->next = traverseNode;
                    prevNode = ptr;
                    head = prevNode;
                }
                else {

                    // Performing swap operation
                    traverseNode->next = ptr->next;
                    ptr->next = traverseNode;
                    prevNode->next = ptr;
                    prevNode = ptr;
                }
                continue;
            }
            prevNode = traverseNode;
            traverseNode = traverseNode->next;
        }

        // If no swap occurred, break the loop
        if (!swapped) {
            break;
        }

        ++itr;
    }

    // Returning the head of the linked list
    return head;
}

void printList(Node *curr) {
    while (curr != nullptr) {
        cout << curr->data << " ";
        curr = curr->next;
    }
}

int main() {
      
      // Create a hard-coded linked list:
    // 5 -> 1 -> 32 -> 10 -> 78
    Node *head = new Node(5);
    head->next = new Node(1);
    head->next->next = new Node(32);
    head->next->next->next = new Node(10);
    head->next->next->next->next = new Node(78);
  
    head = bubbleSort(head);
    printList(head);

    return 0;
}

// C program to sort Linked List
// using Bubble Sort

#include <stdlib.h>

struct Node {
    int data;
    struct Node *next;
};

// Function to get the length of the linked list
int getLength(struct Node *head) {
    int len = 0;
    struct Node *curr = head;
    while (curr != NULL) {
        len++;
        curr = curr->next;
    }
    return len;
}

// Function to perform bubble sort on the linked list
struct Node *bubbleSort(struct Node *head) {
    struct Node *currNode = head;
    int len = getLength(head);
    int itr = 0;
    int swapped;

    // Iterating over the whole linked list
    while (itr < len) {
        struct Node *traverseNode = head;
        struct Node *prevNode = head;
        swapped = 0;

        while (traverseNode->next != NULL) {

            // Temporary pointer to store the next
            // pointer of traverseNode
            struct Node *ptr = traverseNode->next;
            if (traverseNode->data > ptr->data) {
                swapped = 1;
                if (traverseNode == head) {

                    // Performing swap operations and
                    // updating the head of the linked list
                    traverseNode->next = ptr->next;
                    ptr->next = traverseNode;
                    prevNode = ptr;
                    head = prevNode;
                }
                else {

                    // Performing swap operation
                    traverseNode->next = ptr->next;
                    ptr->next = traverseNode;
                    prevNode->next = ptr;
                    prevNode = ptr;
                }
                continue;
            }
            prevNode = traverseNode;
            traverseNode = traverseNode->next;
        }

        // If no swap occurred, break the loop
        if (!swapped) {
            break;
        }

        ++itr;
    }

    // Returning the head of the linked list
    return head;
}

void printList(struct Node *curr) {
    while (curr != NULL) {
        printf("%d ", curr->data);
        curr = curr->next;
    }
}

struct Node *createNode(int x) {
    struct Node *newNode = 
      (struct Node *)malloc(sizeof(struct Node));
    newNode->data = x;
    newNode->next = NULL;
    return newNode;
}

int main() {
  
      // Create a hard-coded linked list:
    // 5 -> 1 -> 32 -> 10 -> 78
    struct Node *head = createNode(5);
    head->next = createNode(1);
    head->next->next = createNode(32);
    head->next->next->next = createNode(10);
    head->next->next->next->next = createNode(78);

    head = bubbleSort(head);
    printList(head);

    return 0;
}

Java

// Java program to sort Linked List
// using Bubble Sort

class Node {
    int data;
    Node next;

    Node(int x) {
        data = x;
        next = null;
    }
}

public class GfG {

    // Function to get the length of the linked list
    static int getLength(Node head) {
        int len = 0;
        Node curr = head;
        while (curr != null) {
            len++;
            curr = curr.next;
        }
        return len;
    }

    // Function to perform bubble sort on 
      // the linked list
    static Node bubbleSort(Node head) {
        Node currNode = head;
        int len = getLength(head);
        int itr = 0;
        boolean swapped;

        // Iterating over the whole linked list
        while (itr < len) {
            Node traverseNode = head;
            Node prevNode = head;
            swapped = false;

            while (traverseNode.next != null) {

                // Temporary pointer to store the next
                // pointer of traverseNode
                Node ptr = traverseNode.next;
                if (traverseNode.data > ptr.data) {
                    swapped = true;
                    if (traverseNode == head) {

                        // Performing swap operations and
                        // updating the head of the linked
                        // list
                        traverseNode.next = ptr.next;
                        ptr.next = traverseNode;
                        prevNode = ptr;
                        head = prevNode;
                    }
                    else {

                        // Performing swap operation
                        traverseNode.next = ptr.next;
                        ptr.next = traverseNode;
                        prevNode.next = ptr;
                        prevNode = ptr;
                    }
                    continue;
                }
                prevNode = traverseNode;
                traverseNode = traverseNode.next;
            }

            // If no swap occurred, break the loop
            if (!swapped) {
                break;
            }

            itr++;
        }

        // Returning the head of the linked list
        return head;
    }

    static void printList(Node curr) {
        while (curr != null) {
            System.out.print(curr.data + " ");
            curr = curr.next;
        }
    }

    public static void main(String[] args) {
      
          // Create a hard-coded linked list:
        // 5 -> 1 -> 32 -> 10 -> 78
        Node head = new Node(5);
        head.next = new Node(1);
        head.next.next = new Node(32);
        head.next.next.next = new Node(10);
        head.next.next.next.next = new Node(78);

        head = bubbleSort(head);
        printList(head);
    }
}

Python

# Python program to sort Linked List
# using Bubble Sort
class Node:
    def __init__(self, x):
        self.data = x
        self.next = None

# Function to get the length of the linked list
def get_length(head):
    length = 0
    curr = head
    while curr is not None:
        length += 1
        curr = curr.next
    return length

# Function to perform bubble sort
# on the linked list
def bubble_sort(head):
    currNode = head
    length = get_length(head)
    itr = 0

    # Iterating over the whole linked list
    while itr < length:
        traverseNode = head
        prevNode = head
        swapped = False

        while traverseNode.next:
          
            # Temporary pointer to store the next
            # pointer of traverseNode
            ptr = traverseNode.next
            if traverseNode.data > ptr.data:
                swapped = True
                if traverseNode == head:

                    # Performing swap operations and
                    # updating the head of the linked list
                    traverseNode.next = ptr.next
                    ptr.next = traverseNode
                    prevNode = ptr
                    head = prevNode
                else:

                    # Performing swap operation
                    traverseNode.next = ptr.next
                    ptr.next = traverseNode
                    prevNode.next = ptr
                    prevNode = ptr
                continue
            prevNode = traverseNode
            traverseNode = traverseNode.next

        # If no swap occurred, break the loop
        if not swapped:
            break

        itr += 1

    # Returning the head of the linked list
    return head


def print_list(curr):
    while curr is not None:
        print(curr.data, end=" ")
        curr = curr.next


if __name__ == "__main__":
  
      # Create a hard-coded linked list:
    # 5 -> 1 -> 32 -> 10 -> 78
    head = Node(5)
    head.next = Node(1)
    head.next.next = Node(32)
    head.next.next.next = Node(10)
    head.next.next.next.next = Node(78)

    head = bubble_sort(head)
    print_list(head)

// C# program to sort Linked List
// using Bubble Sort

using System;

class Node {
    public int data;
    public Node next;

    public Node(int x) {
        data = x;
        next = null;
    }
}

class GfG {

    // Function to get the length of the linked list
    static int GetLength(Node head) {
        int len = 0;
        Node curr = head;
        while (curr != null) {
            len++;
            curr = curr.next;
        }
        return len;
    }

    // Function to perform bubble sort
      // on the linked list
    static Node BubbleSort(Node head) {
        int len = GetLength(head);
        int itr = 0;
        bool swapped;

        // Iterating over the whole linked list
        while (itr < len) {
            Node traverseNode = head;
            Node prevNode = head;
            swapped = false;

            while (traverseNode.next != null) {

                // Temporary pointer to store the next
                // pointer of traverseNode
                Node ptr = traverseNode.next;
                if (traverseNode.data > ptr.data) {
                    swapped = true;
                    if (traverseNode == head) {

                        // Performing swap operations and
                        // updating the head of the linked
                        // list
                        traverseNode.next = ptr.next;
                        ptr.next = traverseNode;
                        prevNode = ptr;
                        head = prevNode;
                    }
                    else {

                        // Performing swap operation
                        traverseNode.next = ptr.next;
                        ptr.next = traverseNode;
                        prevNode.next = ptr;
                        prevNode = ptr;
                    }
                    continue;
                }
                prevNode = traverseNode;
                traverseNode = traverseNode.next;
            }

            // If no swap occurred, break the loop
            if (!swapped) {
                break;
            }

            itr++;
        }

        // Returning the head of the linked list
        return head;
    }

    static void PrintList(Node curr) {
        while (curr != null) {
            Console.Write(curr.data + " ");
            curr = curr.next;
        }
    }

    public static void Main(string[] args) {
      
          // Create a hard-coded linked list:
        // 5 -> 1 -> 32 -> 10 -> 78
        Node head = new Node(5);
        head.next = new Node(1);
        head.next.next = new Node(32);
        head.next.next.next = new Node(10);
        head.next.next.next.next = new Node(78);
      
        head = BubbleSort(head);
        PrintList(head);
    }
}

JavaScript

// JavaScript program to sort Linked List
// using Bubble Sort

class Node {
    constructor(x) {
        this.data = x;
        this.next = null;
    }
}

// Function to get the length
// of the linked list
function getLength(head) {
    let len = 0;
    let curr = head;
    while (curr !== null) {
        len++;
        curr = curr.next;
    }
    return len;
}

// Function to perform bubble 
// sort on the linked list
function bubbleSort(head) {
    let currNode = head;
    let len = getLength(head);
    let itr = 0;
    let swapped;

    // Iterating over the whole linked list
    while (itr < len) {
        let traverseNode = head;
        let prevNode = head;
        swapped = false;

        while (traverseNode.next !== null) {

            // Temporary pointer to store the next
            // pointer of traverseNode
            let ptr = traverseNode.next;
            if (traverseNode.data > ptr.data) {
                swapped = true;
                if (traverseNode === head) {

                    // Performing swap operations and
                    // updating the head of the linked list
                    traverseNode.next = ptr.next;
                    ptr.next = traverseNode;
                    prevNode = ptr;
                    head = prevNode;
                }
                else {

                    // Performing swap operation
                    traverseNode.next = ptr.next;
                    ptr.next = traverseNode;
                    prevNode.next = ptr;
                    prevNode = ptr;
                }
                continue;
            }
            prevNode = traverseNode;
            traverseNode = traverseNode.next;
        }

        // If no swap occurred, break the loop
        if (!swapped) {
            break;
        }

        itr++;
    }

    // Returning the head of the linked list
    return head;
}

function printList(curr) {
    while (curr !== null) {
        console.log(curr.data + " ");
        curr = curr.next;
    }
}

// Create a hard-coded linked list:
// 5 -> 1 -> 32 -> 10 -> 78
let head = new Node(5);
head.next = new Node(1);
head.next.next = new Node(32);
head.next.next.next = new Node(10);
head.next.next.next.next = new Node(78);

head = bubbleSort(head);
printList(head);

Output

1 5 10 32 78

Time complexity: O(n^2) , where n is the number of nodes in the Linked List.
Auxiliary space: O(1)

Sorting Strings using Bubble Sort

kalaikarthick

Improve

Article Tags :

Practice Tags :

Bubble Sort for Linked List by Swapping nodes

Similar Reads

Bubble Sort in different languages

Visualization of Bubble Sort

What kind of Experience do you want to share?