Bubble Sort in Linked List by Swapping Nodes


In this blog, we will learn about bubble sort in linked list. The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of linked lists can be a huge plus point in a coding interview.

Bubble Sort by Swapping Nodes in Linked List

In this problem, we are given a singly linked list. We have to sort this list using bubble sort.

Note: The bubble sort will be applied on nodes instead of values i.e., We have to swap the nodes instead of values.

Understand the Bubble Sorting

Let’s try to understand the problem statement with the help of examples by referring the best websites to learn coding.

Suppose the given list is 5 → 1 → 4 → 2 → 8.

  • According to the problem statement, we have to sort the given list using bubble sort.
  • What do we usually do? We usually swap the node data. But here, we have to swap the nodes and not their data.
  • In the first step, suppose we have to swap 5 and 1. So, we will swap the nodes and not their data. So, the linked list after the first step will be 1 → 5 → 4 → 2 → 8. In this way, swapping will happen, and our final sorted linked list will be 1 → 2 → 4 → 5 → 8

Input:

Output:

Explanation: As we can see, the given singly linked list has been sorted.

This question is not a very complex one. We have to apply a normal bubble sort on the list. The only difference is that instead of swapping the data of adjacent nodes, we will swap the nodes. Let us have a glance at the approach.

Approach and Algorithm of bubble sort in linked list

Swap() function

In the swap() function, we will see how we can swap two adjacent nodes.

  • Let the two adjacent nodes be p1 and p2.
  • Now we will create 2 pointers ptr1 and ptr2, and will make ptr1 point to p1 and ptr2 point to p2.
  • Next, we will create a pointer temp, and will make it point to the next of ptr2.
  • We will make the next of ptr2 point to ptr1 and next of ptr1 point to temp.
  • In this way, following the above steps, the two adjacent nodes p1 and p2 will get swapped.

Dry Run (Swap() function)

BubbleSort()

In this method, we will see how to perform Bubble Sort on the linked list.

  • First, we need the count of the number of nodes in the list. The count can be found with a single list traversal.
  • Now, the first loop is going to run from 0 to count-1.
  • Inside the first loop, we will create a node pointer h that will point to the head and a variable swapped, initializing it with 0.
  • The nested loop will run from 0 to count-i-1.
  • Inside the nested loop, we will check if the adjacent elements are following ascending order or not.
    • If any pair of adjacent nodes are not following the ascending order, we will swap the nodes and the value of swapped will become 1.
  • After the above, if condition, we will increment the h.
  • Now, after the inner loop, if the value of the variable swapped remains 0, it means that the list is sorted, and we will break the loop. Otherwise we will continue with the loop.

Dry Run of Bubble sort

Code Implementation of bubble sort in linked list

#include <stdio.h>
#include <stdlib.h>
  
/* structure for a node */
struct Node {
    int data;
    struct Node* next;
} Node;
  
/*Function to swap the nodes */
struct Node* swap(struct Node* ptr1, struct Node* ptr2)
{
    struct Node* tmp = ptr2->next;
    ptr2->next = ptr1;
    ptr1->next = tmp;
    return ptr2;
}
  
/* Function to sort the list */
int bubbleSort(struct Node** head, int count)
{
    struct Node** h;
    int i, j, swapped;
  
    for (i = 0; i <= count; i++) {
  
        h = head;
        swapped = 0;
  
        for (j = 0; j < count - i - 1; j++) {
  
            struct Node* p1 = *h;
            struct Node* p2 = p1->next;
  
            if (p1->data > p2->data) {
  
                /* update the link after swapping */
                *h = swap(p1, p2);
                swapped = 1;
            }
  
            h = &(*h)->next;
        }
  
        /* break if the loop ended without any swap */
        if (swapped == 0)
            break;
    }
}
  
/* Function to print the list */
void printList(struct Node* n)
{
    while (n != NULL) {
        printf("%d -> ", n->data);
        n = n->next;
    }
    printf("\n");
}
  
/* Function to insert a struct Node
   at the beginning of a linked list */
void insertAtTheBegin(struct Node** start_ref, int data)
{
    struct Node* ptr1
        = (struct Node*)malloc(sizeof(struct Node));
  
    ptr1->data = data;
    ptr1->next = *start_ref;
    *start_ref = ptr1;
}
  
// Driver Code
int main()
{
    int arr[] = { 78, 20, 10, 32, 1, 5 };
    int list_size, i;
  
    /* start with empty linked list */
    struct Node* start = NULL;
    list_size = sizeof(arr) / sizeof(arr[0]);
  
    /* Create linked list from the array arr[] */
    for (i = 0; i < list_size; i++)
        insertAtTheBegin(&start, arr[i]);
  
    /* print list before sorting */
    printf("Linked list before sorting\n");
    printList(start);
  
    /* sort the linked list */
    bubbleSort(&start, list_size);
  
    /* print list after sorting */
    printf("Linked list after sorting\n");
    printList(start);
  
    return 0;
}
#include <iostream>
using namespace std;

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

struct Node* swap(struct Node* ptr1, struct Node* ptr2)
{
    struct Node* tmp = ptr2->next;
    ptr2->next = ptr1;
    ptr1->next = tmp;
    return ptr2;
}

int bubbleSort(struct Node** head, int count)
{
    struct Node** h;
    int i, j, swapped;
  
    for (i = 0; i <  count; i++)
    {
  
        h = head;
        swapped = 0;
  
        for (j = 0; j < count  - i -1; j++) 
        {
  
            struct Node* p1 = *h;
            struct Node* p2 = p1->next;
  
            if (p1->data > p2->data)
            {

                *h = swap(p1, p2);
                swapped = 1;
            }
  
            h = &(*h)->next;
        }

        if (swapped == 0)
            break;
    }
}

void printList(struct Node* n)
{
    while (n != NULL)
    {
        cout << n->data << " -> ";
        n = n->next;
    }
    cout << endl;
}

void insertAtTheBegin(struct Node** start_ref, int data)
{
    struct Node* ptr1
        = (struct Node*)malloc(sizeof(struct Node));
  
    ptr1->data = data;
    ptr1->next = *start_ref;
    *start_ref = ptr1;
}

int main()
{
    int arr[] = { 8, 2, 4, 1, 5 };
    int list_size, i;

    struct Node* start = NULL;
    list_size = sizeof(arr) / sizeof(arr[0]);

    for (i = 0; i < list_size; i++)
        insertAtTheBegin(&start, arr[i]);

    cout <<"Linked list before sorting\n";
    printList(start);

    bubbleSort(&start, list_size);

    cout <<"Linked list after sorting\n";
    printList(start);
  
    return 0;
}

//Bubble Sort For Linked List
//By using get higher node
public class LinkedList {

  static class Node {
    int data;
    Node next;
  }
  public Node head;
  //Class constructors
  LinkedList() {
    head = null;
  }
  //insert element
  public void insert(int value) {
    //Create  node
    Node node = new Node();
    node.data = value;
    node.next = null;
    if (head == null) head = node;
    else {
      Node temp = head;
      //find last node
      while (temp.next != null) {
        temp = temp.next;
      }
      temp.next = node;
    }

  }
  //Display all Linked List elements
  public void display() {
    if (head != null) {

      Node temp = head;
      while (temp != null) {
        System.out.print("  " + temp.data);
        temp = temp.next;
      }
    } else {
      System.out.println("Empty Linked list");
    }
  }
  //perform bubble sort in single linked list
  public void bubbleSort() {

    if (head != null) {

      Node current = null,
        new_head = null,
        move_node = null,
        prev = null;

      while (head != null) {
        prev = null;
        current = head;
        move_node = head;
        while (current != null) {

          //When current node value is grator than previous node
          if (current.next != null && current.next.data > move_node.data) {
            //Swap node values
            move_node = current.next;
            prev = current;

          }
          current = current.next;
        }
        if (move_node == head) {
          head = (head).next;
        }

        if (prev != null) {
          prev.next = move_node.next;
        }
        move_node.next = new_head;
        new_head = move_node;
      }
      //make new head
      head = new_head;

    } else {
      System.out.println("Empty Linked list");
    }
  }

  public static void main(String[] args) {

    LinkedList obj = new LinkedList();
    //insert element of linked list
    obj.insert(7);
    obj.insert(50);
    obj.insert(9);
    obj.insert(42);
    obj.insert(5);
    obj.insert(15);
    System.out.print("Before sort : ");

    //display all node
    obj.display();

    obj.bubbleSort();
    System.out.print("\nAfter sort  : ");

    obj.display();
  }
}

#Bubble Sort For Linked List
#By using get higher node
class Node:
    def __init__(self,data):
        self.data=data
        self.next=None

#Create Class Linked    
class Linked:
    def __init__(self):
        #Assign default value
        self.head=None

    #insert new node to linked list  
    def insert(self,data):
        node=Node(data)
        node.next=None
        if self.head==None:
            self.head=node
        else:
            temp=self.head
            while temp.next!=None:
                temp=temp.next
            #add node    
            temp.next=node

    def display(self):
        if(self.head==None):
            print("Empty Linked List")
            return

        temp=self.head
       
        while(temp!=None):
          print(temp.data,end=" ")
          temp=temp.next
    
    #perform bubble sort in single linked list
    def bubbleSort(self):

        if(self.head!=None):

          current=None
          new_head=None
          move_node=None
          prev=None

          while(self.head!=None):
            prev=None
            current=self.head
            move_node=self.head
            while(current!=None):

              #When current node value is grator than previous node
              if(current.next!=None and  current.next.data>move_node.data):
                #Swap node values
                move_node=current.next
                prev=current

              
              current=current.next
            
            if(move_node==self.head):
              self.head=(self.head).next
            

            if(prev!=None):
              prev.next=move_node.next
            
            move_node.next=new_head
            new_head=move_node
          
          #make new head
          self.head=new_head
          

        else:
           print("Empty Linked list")


def main():
    #Create Object of class Linked
    obj=Linked()
    #insert element of linked list
    obj.insert(7)
    obj.insert(50)
    obj.insert(9)
    obj.insert(42)
    obj.insert(5)
    obj.insert(15)
    print("Before sort : ")
    
    #display all node
    obj.display()

    obj.bubbleSort()
    print("\nAfter sort  : ")

    obj.display()
if __name__=="__main__":
    main()

Output

Linked list before sorting
5 -> 1 -> 4 -> 2 -> 8 ->
Linked list after sorting
1 -> 2 -> 4 -> 5 -> 8 ->

Time Complexity: O(n2), as a nested traversal, is needed.

Conclusion
The bubble can be easily applied to any data structure. In this, the swap function may vary according to the data structure but the algorithm of bubble sort will remain the same. Therefore, In the above article, we have tried to explain bubble sort using linked list.

Related Articles
Doubly circular linked list in data structure Application of doubly linked list
Applications of linked list Singly linked list vs doubly linked list
Advantages and disadvantages of linked list Doubly linked list all operations in C
Binary search in linked list Student management system using linked list
Deletion in doubly linked list Delete the middle node of a linked list
Polynomial addition using linked list Find max value and min value in linked list
Insert a node at a specific position in a linked list Swap nodes in linked list
Add two numbers represented by linked lists Find starting point of loop in linked list
Merge sort linked list Delete a node from linked list at a given position
Remove duplicates from unsorted linked list Reverse a linked list in Python

FAQs

  1. What is the time complexity of bubble sort?
  2. The time complexity of bubble sort is O(N^2), In the 1st iteration there are N-1 comparisons and in the 2nd iteration there are N-2 iterations therefore in the Nth iteration there will be 1 comparison, so the total number of comparisons is N(N-1)/2 i.e. O(N^2).

  3. What is the time complexity of the swap function?
  4. The time complexity of the swap function is constant O(1) as the swap function consists of 3 operations.

  5. Can we use the linked list for sorting?
  6. Yes, merge sort is preferred for sorting the linked list.

  7. Is sorting a linked list efficient?
  8. The efficiency of sorting algorithms totally depends on the type of data that needs to be sorted, i.e. the length of the linked list and the operations to be performed on the list.

Leave a Reply

Your email address will not be published. Required fields are marked *