Skip to main content

Bubble Sort For a Linked List

Perform on Bubble sort in Given linked list, There are many possible solution of this problem.

Method 1: This is very simplest solution of this problem. compared the current node value to all other remaining nodes of linked list. When current node value is smaller then swap the node values by higher element. So this method is based on swapping node element values.

Suppose we are inserted the following (7, 50, 9, 42, 5, 15) node in a sequence.

Bubble sort in linked list

Here given code implementation process.

Method 2: In this process use two linked list. One is form of given linked list and second is an empty linked list. Find largest node element to first linked list and separate this node and add to front of second linked list. Repeat this step until first linked list is not empty. Note that this is not actual bubble sort that is a way to achieve bubble sort.

//C Program
//Bubble Sort For Linked List
//By using get higher node
#include<stdio.h>
#include <stdlib.h> //for malloc function

//create structure
struct Node{
  int data;
  struct Node*next;
};
//function prototype
void insert(struct Node**,int);
void display(struct Node*);
void bubble_sort(struct Node**);
//insert Node element
void insert(struct Node**head,int value){
  //Create dynamic node
  struct Node*node=(struct Node*)malloc(sizeof(struct Node));
  if(node==NULL){
    printf("Memory overflow\n");
  }else{
    node->data=value;
    node->next=NULL;
    if(*head==NULL){
      *head=node;
    }else{
      struct Node*temp=*head;
      //find last node
      while(temp->next!=NULL){
        temp=temp->next;
      }
      //add node at last possition
      temp->next=node;
    }
  }
}
//Display element of Node
void display(struct Node*temp){
  
  if(temp==NULL){
    printf("Empty linked list");
  }
  while(temp!=NULL){
    printf("%d  ",temp->data);
    temp=temp->next;
  }
}
//perform bubble sort in single linked list
void bubble_sort(struct Node**head){

  if(*head!=NULL){

    struct 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{
    printf("Empty linked list");
  }
}
int main(){
  //create node pointer
  struct Node*head=NULL;
  //insert element of linked list

  insert(&head,7);
  insert(&head,50);
  insert(&head,9);
  insert(&head,42);
  insert(&head,5);
  insert(&head,15);
  printf("Before sort : ");
  //display all node
  display(head);

  bubble_sort(&head);

  printf("\nAfter sort  : ");
  display(head);
  return 0;
}

Output

Before sort : 7  50  9  42  5  15  
After sort  : 5  7  9  15  42  50
//C++ Program 
//Bubble Sort For Linked List
//By using get higher node
#include<iostream>
using namespace std;

//create structure
struct Node{
  int data;
  struct Node*next;
};
class LinkedList{
  Node*head;//head node
  public:
    LinkedList();
    void insert(int);
    void display();
    void bubble_sort();
};
LinkedList::LinkedList(){
  head=NULL;
}
//insert node at end of linked list
void LinkedList::insert(int value){
    //Create dynamic node
  struct Node*node=new Node;
  if(node==NULL){
    cout<<"Memory overflow\n";
  }else{
    node->data=value;
    node->next=NULL;
    if(head==NULL){
      //base condition
      head=node;
    }else{
      Node*temp=head;
      while(temp->next!=NULL){
        temp=temp->next;
      }
      //add newly node at last
      temp->next=node;
    }
  }
}
//display all node value in linked list
void LinkedList:: display(){
  if(head==NULL){
    cout<<"Empty linked list";
  }
  else{
    Node*temp=head;
   
    while(temp!=NULL){
      //print node value
      cout<<temp->data<<"  ";
      temp=temp->next;
    }
  }

}
//perform bubble sort in single linked list
void LinkedList:: bubble_sort(){

  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{
    cout<<"Empty linked list"<<endl;
  }
}
int main(){
 
  //create object
  LinkedList obj;
  //insert element of linked list
  obj.insert(7);
  obj.insert(50);
  obj.insert(9);
  obj.insert(42);
  obj.insert(5);
  obj.insert(15);
  cout<<"Before sort : ";
  //display all node
  obj.display();

  obj.bubble_sort();
  
  cout<<"\nAfter sort  : ";
  obj.display();
  return 0;
}

Output

Before sort : 7  50  9  42  5  15  
After sort  : 5  7  9  15  42  50
//Java Program
//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();
  }
}

Output

Before sort :   7  50  9  42  5  15
After sort  :   5  7  9  15  42  50
#Python Program
#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

Before sort : 
7 50 9 42 5 15 
After sort  : 
5 7 9 15 42 50
//C# Program
//Bubble Sort For Linked List
//By using get higher node
using System;
//node class
public class Node{
  public  int data;
  public  Node next;
}
class Program
{
  Node head;
  public Program(){
    head=null;
  }
  //insert node of linked list
  public void insert(int data){
    Node newNode=new Node();
    newNode.data=data;
    newNode.next=null;
    if(head==null) head=newNode;
    else{
      Node temp=head;
      //get last node
      while(temp.next!=null){
        temp=temp.next;
      }
      //add new node
      temp.next=newNode;
    }
  }
  //display linked list nodes value
  public void display(){
    if(head==null){
      Console.Write("Empty List");
    }else{
      Node temp=head;
      while(temp!=null){
        Console.Write("  {0}",temp.data);
        temp=temp.next;
      }

    }
  }
  //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{
      Console.WriteLine("Empty Linked list"); 
    }
  }

  static void Main()
  {
    Program obj=new Program();
    obj.insert(7);
    obj.insert(50);
    obj.insert(9);
    obj.insert(42);
    obj.insert(5);
    obj.insert(15);
    Console.Write("Before sort : "); 

    //display all node
    obj.display();

    obj.bubbleSort();
    Console.Write("\nAfter sort  : "); 

    obj.display();
  }
}

Output

Before sort :   7  50  9  42  5  15
After sort  :   5  7  9  15  42  50
Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment