Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Approach
2.1.
Implementation in Java
2.1.1.
Time Complexity
2.1.2.
Space Complexity
3.
Frequently Asked Questions
3.1.
What is a doubly-linked list?
3.2.
What is the real-life implementation of a doubly-linked list?
3.3.
What is a circular linked list?
3.4.
Why is it that deletion is faster in a doubly-linked list?
4.
Conclusion
Last Updated: Mar 27, 2024
Easy

Sort the bitonic Doubly Linked List

Author Prerna Tiwari
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

A Doubly Linked List is a type of linked list with three components at each node. *prev - previous node's address, data - data item, and *next - next node's address. A doubly linked list that is strictly increasing or strictly decreasing is also called a bitonic doubly linked list.

 

Representation of Doubly linked list

Problem Statement

We are given a bitonic doubly linked list, and our task is to sort the given doubly linked list.

Sample Examples

Input

3→7→12→17→15→10→8→6→4

Output

3→4→6→7→8→10→12→15→17

Input

14→16→18→17→15→12→-3

Output

-3→12→14→15→16→17→18

Approach

The approach to this problem is a simple and a bit intuitive:

  1. First, we will find the node in the bitonic doubly list that is smaller than the node before it. We will make that node the current node. 
     
  2. If no such node exists, the bitonic doubly linked list has already been sorted. 
     
  3. Otherwise, we will divide the bitonic linked list into two lists, one starting from the head node and going down to the current node, and the other starting from the current node and going down to the end of the list. 
     
  4. Now, the second list will be reversed. 
     
  5. After reversing the second list we will merge both the list. 
     
  6. The resulting merged list is the necessary sorted doubly linked list.

Implementation in Java

#include <iostream>
using namespace std;

class NodeLinker
{
public:
    int data;
    NodeLinker *next;
    NodeLinker *prev;

    NodeLinker(int data)
    {
        this->data = data;
        this->next = nullptr;
        this->prev = nullptr;
    }
};

class DoublyLinkedList
{
public:
    NodeLinker *head;
    NodeLinker *tail;

    DoublyLinkedList()
    {
        this->head = nullptr;
        this->tail = nullptr;
    }

    // Insert new node at last position
    void insert(int value)
    {
        // Creating a node
        NodeLinker *node = new NodeLinker(value);

        if (this->head == nullptr)
        {
            // Adding first node
            this->head = node;
            this->tail = node;

            return;
        }
        // Adding node at end position
        this->tail->next = node;
        node->prev = this->tail;

        // Get new last node

        this->tail = node;
    }

    // Display node element of DLL
    void display()
    {

        if (this->head == nullptr)
        {
            cout << "Linked List is empty" << endl;
        }
        else
        {
            cout << "Head to Tail elements :";

            NodeLinker *temp = this->head;

            while (temp != nullptr)
            {

                cout << "  " << temp->data;

                temp = temp->next;
            }
            cout << "\nLinked List Tail to Head :";

            temp = this->tail;

            while (temp != nullptr)
            {

                cout << "  " << temp->data;

                temp = temp->prev;
            }
        }
    }
    // Sorting biotonic linked list
    void sortBiotonicList()
    {
        if (this->head != nullptr)
        {

            NodeLinker *front = this->head;
            NodeLinker *last = nullptr;

            if (this->tail->data < front->data)
            {

                this->head = this->tail;
                this->tail = this->tail->prev;
                this->tail->next = nullptr;
                this->head->prev = nullptr;
                this->head->next = front;
                front->prev = this->head;
            }

            while (front != nullptr && this->tail != nullptr && front != this->tail)
            {
                if (this->tail->data < front->data)
                {

                    last = this->tail;

                    this->tail = this->tail->prev;
                    this->tail->next = last->next;

                    if (last->next != nullptr)
                    {

                        last->next->prev = this->tail;
                    }
                    last->prev = front->prev;

                    if (front->prev != nullptr)
                    {
                        front->prev->next = last;
                    }
                    last->next = front;
                    front->prev = last;
                }

                else
                {

                    front = front->next;
                }
            }
        }

        else
        {
            cout << "Empty linked list" << endl;
        }
    }
};

int main()
{

    DoublyLinkedList *dll = new DoublyLinkedList();

    // Insert following linked list elements

    dll->insert(4);
    dll->insert(6);
    dll->insert(8);
    dll->insert(13);
    dll->insert(11);
    dll->insert(7);
    dll->insert(5);
    dll->insert(2);
    dll->insert(-3);
    cout << "\nBefore sorting" << endl;

    dll->display();
    dll->sortBiotonicList();

    cout << "\nAfter sorting" << endl;
    dll->display();

    return 0;
}
You can also try this code with Online C++ Compiler
Run Code

Input 

Before sorting
Head to Tail elements :  4  6  8  13  11  7  5  2  -3
Linked List Tail to Head :  -3  2  5  7  11  13  8  6  4

Output

After sorting
Head to Tail elements :  -3  2  4  5  6  7  8  11  13
Linked List Tail to Head :  13  11  8  7  6  5  4  2  -3

Time Complexity

The above approach has an O(n) time complexity, where n is the total number of nodes in the doubly linked list.

Space Complexity

Since we are not using any extra, the above approach has an O(1) space complexity. 

Recommended Topic, Floyds Algorithm and Rabin Karp Algorithm

Frequently Asked Questions

What is a doubly-linked list?

A Doubly Linked List is a type of linked list that allows easy navigation in both forward and backward directions as it has an extra pointer prev which points to the previous node.

What is the real-life implementation of a doubly-linked list?

  • A music player with forward and back buttons.
  • Redo and undo operations
  • The browser cache, which allows you to navigate between pages, is another good example of a doubly linked list.
  • LRU caching

What is a circular linked list?

Circular Linked List is a singly Linked List, where the last node of a singly Linked List contains a pointer to a node that points to the first node (head node) of the Linked List.

Why is it that deletion is faster in a doubly-linked list?

If we know which cell to remove ahead of time, the doubly-linked list allows us to do so in time O(1), whereas a singly-linked list would take time O(2) (n). If we don't know the cell ahead of time, the answer is O(n) in both cases.

Conclusion

We have to sort the bitonic doubly linked list in this article. We started with introducing the bitonic doubly linked list, after that we explained the problem statement with some sample examples, and in the end, we discussed the implementation of the problem in C++ with the complexities of that implementation.

We hope that this blog has helped you enhance your knowledge regarding the problem of sorting the bitonic doubly linked list and if you would like to learn more, check out our other articles on our platform Coding Ninjas Studio.

For peeps out there who want to learn more about Data Structures, Algorithms, Power programming, JavaScript, or any other upskilling, please refer to guided paths on Coding Ninjas Studio. Enroll in our courses, go for mock tests, solve problems available, and interview puzzles. Also, you can put your attention towards interview stuff- interview experiences and an interview bundle for placement preparations. 

Do upvote our blog to help other ninjas grow. 

Happy Coding!

Live masterclass