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.
3.1.
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

Prerna Tiwari
0 upvote

## 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.

### 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;

{
public:
int data;

{
this->data = data;
this->next = nullptr;
this->prev = nullptr;
}
};

{
public:

{
this->tail = nullptr;
}

// Insert new node at last position
void insert(int value)
{
// Creating a 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()
{

{
cout << "Linked List is empty" << endl;
}
else
{
cout << "Head to Tail elements :";

while (temp != nullptr)
{

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

temp = temp->next;
}

temp = this->tail;

while (temp != nullptr)
{

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

temp = temp->prev;
}
}
}
void sortBiotonicList()
{
{

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

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

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()
{

// 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;
}``````

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

### 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