Introduction
This article will explain insertion sort for a doubly-linked list; moving on, we will see its algorithm in detail with its C++ code, and at last, we will see its space and time complexity. First, we need to know what a doubly-linked list is?
A doubly linked list is a linked data structure that consists of a group of sequentially connected entries called nodes. There are three fields in each node: two link fields and one data field.
Problem statement
We are given a doubly-linked list in this problem, and we must use insertion sort to sort the linked list in ascending order. In this program, we will create a doubly linked list and sort nodes of the list in ascending order.
Examples
Input
n=4, list[] ={9, 1, 5, 2}
We want to sort the linked list in ascending order.
Output
n=4, list[]={1, 2, 5, 9}
Input
n=5, list[]={3, 9, 10, 6, 5}
Output
n=5, list[]={3, 5, 6, 9, 10}
Recommended Topic, Floyds Algorithm and Rabin Karp Algorithm
Algorithm
1. Firstly, we will Create a Node class that represents a list node. It will have three properties: data, previous (pointing to the previous node), and next (pointing to the next node).
2. Create a new class that will create a doubly linked list with two nodes: head and tail. The head and tail at the beginning point to null.
3. The function addNode() operates as explained below to add a node to the list:
1. A newly added node will be pointed by both the head pointer and tail pointer.
2. The previous of the head and the next pointer of the tail will point to null.
3. If the head pointer is not null, then the new node will be added to the end of the list.
4. The previous of the new node will point to the tail.
5. The new node will take on the role of the new tail.
6. ThThe next pointer in Tail's chain will be null.
4. sortList() function sorts the list's nodes in ascending order:
1. Create a node that points to the head.
2. Create a new node index that points to the node adjacent to the existing one.
3. Compare the current and index node's data.
4. Swap the data between them if the current data is greater than the index data.
5. Current value will point to current→next, and index value will point to index→next.
6. Carry on in this manner until the full list has been sorted.
5. display() function displays every node present in the list:
1. Create a fresh node called 'current' that points to the head.
2. Print current→data until it reaches null.
3. In each iteration, the current will point to the next node in the list.
C++ code
// Include header file
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
// Defining new node
class NewNode
{
public:
int data;
NewNode *next;
NewNode *prev;
NewNode(int data)
{
this->data = data;
this->next = nullptr;
this->prev = nullptr;
}
};
class Node
{
public:
NewNode *head;
NewNode *tail;
Node()
{
this->head = nullptr;
this->tail = nullptr;
}
// Insert new node at end position
void insert(int value)
{
// Creating a new node
NewNode *node = new NewNode(value);
if (this->head == nullptr)
{
// Adding first node
this->head = node;
this->tail = node;
return;
}
// Adding node at last position
this->tail->next = node;
node->prev = this->tail;
this->tail = node;
}
// Displaying node element of doubly linked list
void print()
{
if (this->head == nullptr)
{
cout << "Empty Linked List" << endl;
}
else
{
cout << "\nLinked List Head to Tail :";
// Get first node of linked list
NewNode *temp = this->head;
// iterate linked list
while (temp != nullptr)
{
// Displaying node value
cout << " " << temp->data;
// Visiting next node
temp = temp->next;
}
cout << "\nLinked List Tail to Head :";
// Getting last node of linked list
temp = this->tail;
// iterate linked list
while (temp != nullptr)
{
// Display node value
cout << " " << temp->data;
// Visiting to previous node
temp = temp->prev;
}
cout << "\n";
}
}
// Swapping value of given nodes
void swapData(NewNode *first, NewNode *second)
{
int value = first->data;
first->data = second->data;
second->data = value;
}
// Sort elements using insertion sort
void Sort()
{
// Getting first node
NewNode *front = this->head;
NewNode *back = nullptr;
while (front != nullptr)
{
// Getting next node
back = front->next;
// Updating node value when consecutive nodes are not sorted
while (back != nullptr &&
back->prev != nullptr &&
back->data < back->prev->data)
{
// Changed node data
this->swapData(back, back->prev);
// Visiting previous node
back = back->prev;
}
// Visiting next node
front = front->next;
}
}
};
int main()
{ // Initializing new double-linked
Node *newLL = new Node();
// Insert element of linked list
cout << " Number of elements in linked list:" << endl;
int n;
cin >> n;
cout << n << endl;
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
newLL->insert(x);
}
cout << "Doubly linked list before sorting";
// printing unsorted linked list
newLL->print();
// Sorting the linked list using insertion sort
newLL->Sort();
cout<<endl;
cout << "Doubly linked list after sorting";
// printing sorted linked list
newLL->print();
return 0;
}
Input
n= 8, list = {2, 4, 9, 8, 3, 5, 1, 6}
Output
Number of elements in linked list: 8
Doubly linked list Before sorting:
Linked List Head to Tail : 2 4 9 8 3 5 1 6
Linked List Tail to Head : 6 1 5 3 8 9 4 2
Doubly linked list after sorting:
Linked List Head to Tail: 1 2 3 4 5 6 8 9
Linked List Tail to Head: 9 8 6 5 4 3 2 1
Complexity analysis
Time complexity
Insertion Sort has an O(N^2) time complexity and is faster than other methods when the data set is almost sorted.
Space complexity
Insertion sort has space complexity O(1) as we are not using any dedicated data structure for storage.
85+ registered 