# Bubble Sort On Doubly Linked List

Sorting a linked list can be troublesome sometimes, but there are multiple algorithms to do so easily. A bubble sort might not be the most efficient one for sorting a Linked List but it does give us one of the most simple solutions to the problem.
Bubble sort for the doubly linked list is similar to single list just we also have to update the previous pointer.
Suppose we have a doubly-linked list as 3 4 5 2 1
Then after bubble sort, we will have 1 2 3 4 5

### Approach

The idea is similar to what we do in arrays, we keep on checking the adjacent elements and swap the elements if the first element is greater than the next element. We keep on doing this till all the elements are arranged in ascending order.

### Algorithm

• We use a do-while loop and a swap variable to denote if we want to swap the elements or not
• Traverse the Doubly Linked List and if for a current element if the next element is greater than the current element then swap the two nodes by changing their pointers and mark swap = 1
• We keep on doing this till we get all the elements in the list in sorted order.

Code Implementation

### Bubble Sort On Doubly Linked List

```#include
using namespace std;
struct Node {
int data;
Node* prev;
Node* next;
};
void insertAtTheBegin(struct Node **start_ref, int data)
{
struct Node *ptr1 = new Node;
ptr1->data = data;
ptr1->next = *start_ref;
if (*start_ref != NULL)
(*start_ref)->prev = ptr1;
*start_ref = ptr1;
}
void display(struct Node *start)
{
struct Node *temp = start;
cout << endl;
while (temp!=NULL)
{
cout << temp->data << " ";
temp = temp->next;
}
}
void bubbleSort(struct Node *start)
{
int swapp, i;
struct Node *ptr1;
struct Node *lptr = NULL;
if (start == NULL)
return;

do
{
swapp = 0;
ptr1 = start;

while (ptr1->next != lptr)
{
if (ptr1->data > ptr1->next->data)
{
swap(ptr1->data, ptr1->next->data);
swapp = 1;
}
ptr1 = ptr1->next;
}
lptr = ptr1;
}
while (swapp);
}

int main()
{
int arr[] = {3, 4, 5, 2, 1};
int list_size, i;
list_size = sizeof(arr)/sizeof(arr);
struct Node *start = NULL;
for (i = 0; i< list_size; i++)
insertAtTheBegin(&start, arr[i]);
bubbleSort(start);
display(start);
return 0;
}
```
```class PrepBytes
{
static class Node
{
int data;
Node prev;
Node next;
};
static Node pushatbegin( Node start_ref, int data)
{
Node ptr1 = new Node();
ptr1.data = data;
ptr1.next = start_ref;
if (start_ref != null)
(start_ref).prev = ptr1;
start_ref = ptr1;
return start_ref;
}
static void display( Node start)
{
Node temp = start;
System.out.println();
while (temp != null)
{
System.out.print( temp.data + " ");
temp = temp.next;
}
}
static Node bubbleSort( Node start)
{
int swapp, i;
Node ptr1;
Node lptr = null;
if (start == null)
return null;

do
{
swapp = 0;
ptr1 = start;

while (ptr1.next != lptr)
{
if (ptr1.data > ptr1.next.data)
{
int t = ptr1.data;
ptr1.data = ptr1.next.data;
ptr1.next.data = t;
swapp = 1;
}
ptr1 = ptr1.next;
}
lptr = ptr1;
}
while (swapp != 0);
return start;
}
public static void main(String args[])
{
int arr[] = {3, 4, 5 ,2 ,1};
int i;
Node start = null;
for (i = 0; i < 5; i++)
start=pushatbegin(start, arr[i]);
start = bubbleSort(start);
display(start);
}
}
```

Output: 1 2 3 4 5

Space Complexity: O(1), no extra space is used.

This blog tried to explain the bubble sort algorithm on a doubly-linked list by modifying the node pointer and walkthrough the approach and algorithm along with the code implementation in various languages. To practice more such problems on Linked List you can check out PrepBytes - Linked-list