Last Updated: Mar 27, 2024
Difficulty: Medium

# Insertion sort for doubly linked list

## 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 *tail;
Node()
{
this->tail = nullptr;
}
// Insert new node at end position
void insert(int value)
{
// Creating a new node
NewNode *node = new NewNode(value);
{
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()
{
{
cout << "Empty Linked List" << endl;
}
else
{
// Get first node of linked list
while (temp != nullptr)
{
// Displaying node value
cout << " " << temp->data;
// Visiting next node
temp = temp->next;
}
// Getting last node of linked list
temp = this->tail;
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 *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()
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";
newLL->print();
// Sorting the linked list using insertion sort
newLL->Sort();
cout<<endl;
cout << "Doubly linked list after sorting";
newLL->print();
return 0;
}``````

Input

``n= 8, list = {2, 4, 9, 8, 3, 5, 1, 6} ``

Output

``````Number of elements in linked list: 8

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

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.

### What is a doubly-linked list?

A double-linked list is a linked data structure made up of nodes, which sequentially link records. There are three fields in each node: two link fields and one data field.

### What are the drawbacks of using a doubly-linked list?

It doesn't provide random access to elements. When compared to singly-linked lists, operations take a longer time due to the overhead of handling extra pointers.

### What is the use of a doubly-linked list?

It's used to handle data, implement undo-redo features, build most recently used and least recently used caches, and build diverse data structures like hash tables and stacks.

## Conclusion

In this article, we have analyzed insertion sort for doubly-linked lists such that elements of the linked lists are arranged in ascending order. We have gone insertion sort approach to solving the problem; we have also discussed its algorithm, C++ code, and also space and time complexity.

After reading about the insertion sort, are you not feeling excited to read/explore more articles on the topic of array and data structures and algorithms? Don't worry; Coding Ninjas has you covered. To learn, see Data Structures and AlgorithmsCompetitive Programming.

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Operating SystemUnix File SystemFile System RoutingFile Input/Output.JavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But suppose you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Topics covered
1.
Introduction
1.1.
Problem statement
1.2.
Examples
2.
Algorithm
2.1.
C++ code
2.1.1.
Complexity analysis
3.