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:
-
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.
-
If no such node exists, the bitonic doubly linked list has already been sorted.
-
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.
-
Now, the second list will be reversed.
-
After reversing the second list we will merge both the list.
- 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;
}
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