# Bubble Sort On Linked List

“** Bubble Sort On Linked List**” is one of the basic problem based on the linked list data structure and sorting algorithm. Here, we are given a linked list and our task is sort the elements of given linked list in ascending order using bubble sort.

**Example:**

Linked List Before Sorting: Linked List: 19 -> 17 -> 15 -> 18 -> 16 Linked List After Sorting: Linked List: 15 -> 16 -> 17 -> 18 -> 19

**C++ Program to perform bubble sort on linked list** **is as follows:**

```
/* C++ Program to perform bubble sort on linked list */
#include<iostream>
using namespace std;
/* Structure of Node of the Linked List */
struct node
{
int data;
struct node *next;
};
/* Function to Insert Node at the End of the Linked List */
void insert_end(struct node **head, int ele)
{
/* Creating a Node */
struct node *new_node;
new_node = (struct node*)malloc(sizeof(struct node));
new_node->data = ele;
new_node->next = NULL;
/* Check whether the linked list is empty or not */
/* If Linked List is empty, then new node will become head of the linked list */
if(*head == NULL)
{
*head = new_node;
return;
}
/* If Linked List is not empty, then traverse the complete linked list and point the
pointer of last node of the linked list to the new node of the linked list */
struct node *temp = NULL;
temp = (*head);
while(temp->next != NULL)
temp=temp->next;
temp->next = new_node;
}
/* Function to Sort the Linked List using Bubble Sort */
void bubbleSort(struct node *head)
{
struct node *temp1;
struct node *temp2;
for(temp1 = head; temp1!=NULL; temp1=temp1->next)
{
for(temp2 = temp1->next; temp2!=NULL; temp2=temp2->next)
{
if(temp1->data > temp2->data)
{
int temp = temp1->data;
temp1->data = temp2->data;
temp2->data = temp;
}
}
}
}
/* Function to Print the Linked List */
void print(struct node *head)
{
struct node *p = head;
while(p!=NULL)
{
cout<<p->data<<" ";
p=p->next;
}
}
int main()
{
struct node *head;
head = NULL;
/* Inserting Some Nodes of the Linked List */
insert_end(&head,4);
insert_end(&head,3);
insert_end(&head,2);
insert_end(&head,1);
cout<<"The linked list elements before sorting:\n";
print(head);
bubbleSort(head);
cout<<"\n The linked list elements after sorting:\n";
print(head);
}
```

The linked list elements before sorting: 4 3 2 1 The linked list elements after sorting: 1 2 3 4OUTPUT:

**Related Posts:**

**Detect a Loop in a Linked List.****Find the Length of the Loop present in the Linked List.****Detect and Remove Loop from a Linked List.****Segregate Even and Odd Nodes of the Linked List.****Delete Complete Linked List.****Delete Nth Node of the Linked List.****Delete without head pointer of the Linked List.****Delete All Occurrences of particular node of the Linked List.****Delete Alternate Nodes of the Linked List.****Delete every ‘N’ Nodes After ‘M’ Nodes of the Linked List.****Remove Duplicate Nodes from an Unsorted Linked List.****Remove Duplicate Nodes from a Sorted Linked List.****Find Union and Intersection of Two Linked List.****Merge Two Sorted Linked List.****Insert a New Node at the Sorted Linked List.****Reverse a Linked List.****Reverse a Linked List Using Stack.****Printing Linked List in Reverse Order without actually reversing the Linked List.****Swap Adjacent Elements of the Linked List.****Count All Occurrences of a Particular Node in a Linked List.**