In this blog, we will discuss bubble sort, but it will be on a doubly linked list. Bubble Sort is the most easiest and naive algorithm. It is simple to implement using an array but will it be a challenge when we will have to implement it on a Doubly Linked List? Letâ€™s find out.

The problem statement is clear, so before we jump onto the explanation part, let us first have a look at what exactly a doubly linked list is.

Doubly Linked List

A doubly linked list is a data structure that consists of a collection of nodes, where each node contains a value and references to both the next and previous nodes in the list. This allows for efficient traversal in both directions (i.e., forward and backward) through the list, as well as insertion and deletion of elements at any position. The first and last nodes typically have a null reference for the next and previous nodes, respectively.

Problem Statement

We are given a doubly linked list of N nodes, and our objective is to sort the doubly linked list using bubble sort.

Sample Examples

Input

N=6,

Output

After sorting the doubly linked list looks like this,

Input

N=4,

Output

After sorting the doubly linked list looks like this,

Approach for Solving

We will use the same approach as what we use for an array data structure.

We will keep track of adjacent elements

If it's found to be less than the present element then we will swap both elements.

We will repeat the above step until we get a doubly linked list where no further swaps are possible.

Dry-Run

Consider the doubly linked list given below,

We have to sort the doubly linked list using bubble sort so letâ€™s start,

Step 1

We will traverse the doubly linked list and we will compare the adjacent elements if the value of ptr1 is greater than ptr2 then it means that ptr1 is having a larger element so we will swap the data, this is would be the same as bubble sort. (ptr1 is the current element and ptr2 is the next element of the linked list)

Step-2

We will repeat the above step-1 till there is no such pair of adjacent elements in the doubly linked list where the value of ptr1 is greater than ptr2.

Step-3

Again repeating the above process,

Step-4

In this step, we will see that the doubly linked list has already been sorted. So we will terminate our process and print the doubly linked list.

#include <iostream>
using namespace std;
class Node
{
public:
int data;
Node *next;
Node *prev;
Node(int data)
{
this->data = data;
this->next = NULL;
this->prev = NULL;
}
};
class bubble_sort_DLL
{
public:
Node *head;
Node *tail;
bubble_sort_DLL()
{
this->head = NULL;
this->tail = NULL;
}
// function to add a node in doubly linked list
void addNode(int data)
{
Node *newNode = new Node(data);
if (head == NULL)
{
head = tail = newNode;
}
else
{
tail->next = newNode;
newNode->prev = tail;
tail = newNode;
}
}
// function to print the doubly linked list
void print_DLL()
{
Node *curr = head;
if (curr == NULL)
{
std::cout << "The Linked list is found to be empty, Please add some data." << std::endl;
}
while (curr != NULL)
{
std::cout << curr->data << " ";
curr = curr->next;
}
}
// function to perform bubble sort on the doubly linked list
void bubble()
{
if (head == NULL)
return;
// to check if DLL has been sorted or not
bool flag = false;
// to represent the pair of adjacent elements
Node *ptr1, *ptr2;
// if flag becomes true , it means that the DLL has been sorted
while (!flag)
{
flag = true;
ptr1 = head;
ptr2 = head->next;
while (ptr2)
{
// if value is greater than swap the values
if (ptr1->data > ptr2->data)
{
swap(ptr1->data, ptr2->data);
flag = false;
}
// move to next pointers
ptr2 = ptr2->next;
ptr1 = ptr1->next;
}
}
}
};
int main()
{
bubble_sort_DLL dll;
dll.addNode(3);
dll.addNode(9);
dll.addNode(7);
dll.addNode(2);
dll.addNode(15);
cout << "The doubly linked list which we have to sort: " << endl;
dll.print_DLL();
dll.bubble();
cout << endl
<< "The doubly linked list after the sorting: " << endl;
dll.print_DLL();
return 0;
}

Output

The doubly linked list which we have to sort:
3 9 7 2 15
The doubly linked list after the sorting:
2 3 7 9 15

Complexity

The Time Complexity of the code is O(N^2) because for the first time, we are performing n-1 iteration, in next we have n-2 iteration, we have n-3 iteration, we proceed (n-1)+(n-2)+(n-3)+....+3+2+1 total iterations, we have (n-1)*(n-1+1)/2 =(n-1)*n/2=n^2 times we have to iterate, where n is the number of nodes in the Linked List.

Now about Space Complexity, we are not using any other space other than constant time-space. We are doing operations on the same linked list. We are just using a constant variable of O(1) times for swapping elements. The Space Complexity is O(1).

Frequently Asked Question

What is the Time Complexity and Space Complexity?

Time Complexity is O(N^2), and Space Complexity is O(1).

What is Sorting?

Order data in an increasing or decreasing fashion according to some linear relationship among the data items.

What is Bubble Sort?

Bubble Sort is the most straightforward sorting algorithm that repeatedly swaps the adjacent elements.

What is the Time and Space Complexity of the Bubble sort?

Best Time Complexity O(n), Average Time Complexity O(n^2), Worst Time Complexity O(n^2), Space Complexity O(1).

When does Bubble sort have a Time Complexity of O(n) and Space Complexity of O(1)?

When the list is already sorted, we have a Time Complexity of O(n) on performing Bubble sort.

Conclusion

In this blog, we discuss the sorting algorithm; in the doubly linked list data structure, we understand the concept using the code and the Dry-Run. We came up with Bubble Sort complexity in different cases as Best Time Complexity O(n), Average Time Complexity O(n^2), Worst Time Complexity O(n^2), and Space Complexity O(1). We discuss the Time and Space Complexity of sorting the doubly linked list as O(N^2) and O(1), respectively.