## Introduction

The linked list is one of the most essential and fundamental data structures which is widely used. It is a linear data structure and is heavily used in implementing operating systems. __Sorting__ is an important application, and we must learn how to sort a linked list. Let us look at how to perform bubble sort and merge sort on a linked list.

## Bubble Sort

**Approach**

__Bubble Sort__ is one of the most popular and naive sorting algorithms. In this technique, we find the maximum element from the unsorted part and place it at its correct position, at the end of the unsorted part. We repeatedly do it for every element.

So in case of sorting a linked list, for each element, we traverse through the entire unsorted part of the linked list. Initially, the entire array is unsorted, and gradually we sort it by increasing its size in every iteration.

**Program**

```
#include <iostream>
using namespace std;
// Linked list node class.
class Node
{
public:
int data;
Node *next;
Node(int data)
{
this->data = data;
this->next = NULL;
}
};
// Function to sort the linked list.
Node *bubbleSort(Node *head)
{
Node *temp1 = head, *temp2;
while (temp1 != NULL)
{
temp2 = head;
// Finding the largest element in the unsorted part.
// We put it at the end of the unsorted part.
while (temp2->next != NULL)
{
if (temp2->data > temp2->next->data)
{
int temp = temp2->data;
temp2->data = temp2->next->data;
temp2->next->data = temp;
}
temp2 = temp2->next;
}
temp1 = temp1->next;
}
return head;
}
// Function to take user input and create the linked list.
Node *takeinput()
{
int data;
cin >> data;
Node *head = NULL, *tail = NULL;
while (data != -1)
{
Node *newnode = new Node(data);
if (head == NULL)
{
head = newnode;
tail = newnode;
}
else
{
tail->next = newnode;
tail = newnode;
}
cin >> data;
}
return head;
}
// Function to print the linked list.
void print(Node *head)
{
Node *temp = head;
while (temp != NULL)
{
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
int main()
{
// Taking user input. (ELements before -1 are considered to be data of the linked list).
Node *head = takeinput();
// Calling 'bubbleSort()' function to sort the linked list.
head = bubbleSort(head);
// Printing the linked list.
print(head);
}
```

**Input**

`5 4 3 2 1 -1`

**Output**

`1 2 3 4 5 `

### Complexities

**O(N * N),** ‘N’ is the size of the linked list.

The bubble sort uses two nested loops to sort an array. In each iteration, the largest element gets placed in the right position. Each iteration takes **O(N)** time in the worst case. Thus overall, it takes **O(N * N) **time.

T(N) = i=1n-1i

**O(1)**We declare only a few variables. Thus the space complexity is constant.