Table of contents
1.
Introduction
2.
Doubly Linked List
3.
Problem Statement
3.1.
Sample Examples
3.2.
Approach for Solving
3.3.
Dry-Run
4.
Implementation in C++
4.1.
Complexity
5.
Frequently Asked Question
5.1.
What is the Time Complexity and Space Complexity?
5.2.
What is Sorting?
5.3.
What is Bubble Sort?
5.4.
What is the Time and Space Complexity of the Bubble sort?
5.5.
When does Bubble sort have a Time Complexity of O(n) and Space Complexity of O(1)?
6.
Conclusion
Last Updated: Mar 27, 2024
Medium

Bubble Sort on Doubly Linked List

Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

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. 

Introduction image

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.

Doubly Linked List image

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,

input doubly linked list image

Output

After sorting the doubly linked list looks like this,

output doubly linked list image

Input

N=4,

input doubly linked list image

Output

After sorting the doubly linked list looks like this,

output doubly linked list image

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,

Doubly Linked List image

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-1 image

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-2 image

Step-3 

Again repeating the above process,

step-3 image

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.

Also see, Rabin Karp Algorithm

Implementation in C++

#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;
}
You can also try this code with Online C++ Compiler
Run Code

 

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.

We hope this article has helped you in some way, and if you liked our article, do upvote our article and help other ninjas grow.  You can refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingSystem Design, and many more!

Recommended Readings:

Recommended Problems -

Head to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences and interview bundles, follow guided paths for placement preparations, and much more!

Live masterclass