Introduction
In this article, we will discuss a famous problem of Doubly Linked List. The problem is of sorted insert in a doubly-linked list with head and tail pointers. A doubly linked list is a Data Structure containing a set of sequentially linked data called nodes. Each node is divided into two link fields(points to the next or previously linked nodes) and one data field.
Problem statement
The problem is to create a doubly linked list by inserting the nodes so that the doubly linked list remains in the sorted order. We need to maintain the pointers, head pointer(points to the first node of the doubly linked list), and tail pointer(points to the last node of the doubly linked list).
Sample Examples
Input
Output
Input
Output
In the above example, we are sorting the doubly linked list by swapping the elements of the list in increasing order.
Recommended Topic, Floyds Algorithm
Approach
The approach to solving this problem is a bit intuitive, we will first insert the nodes one by one to make a doubly linked list. Then we will check if the head is pointing to null or not if it is then the node that we have inserted will become the first node of the doubly linked list. Whenever we will insert a node, we will check if the node has a lesser value than the head node if it is then we will swap these nodes to make the list in ascending order. Now, if the inserted node has a greater value then we will make that node the head node. We will perform these checks for every node and accordingly, we will insert the node. When all the nodes are inserted, then we will print the nodes.
Algorithm
- The linked list is empty, so insert the first node of the linked list and assign this address to the head pointer of the linked list.
- In some cases, the linked lists are not empty, and you find the linked list nodes larger than the recently added nodes. In these cases, there are three possible scenarios which are as follows:
- If the first node is large, add this node in front of the linked list, and the head pointer will point to this new node. This is the state of the node insertion at the beginning.
- If the first node is not large, then this node is added to the last linked nodes. This is the state of placing a node in the end.
- If the inserted node is located in the center, then add this node to this position.
Java code
import java.io.*;
import java.util.*;
// A linked list node
class Node
{
int data;
Node prev, next;
}
class codingninjas3
{
static Node front, back;
static void insert(int keynode)
{
Node temp = new Node();
temp.data = keynode;
temp.next = null;
// If we have to insert the first node in doubly linked list
if (front == null)
{
front = temp;
back = temp;
front.prev = null;
return;
}
// If node to be insetailed has value less
// than first node
if (temp.data < front.data)
{
temp.prev = null;
front.prev = temp;
temp.next = front;
front = temp;
return;
}
// If node to be insetailed has value more
// than last node
if (temp.data > back.data)
{
temp.prev = back;
back.next =temp;
back = temp;
return;
}
// Find the node before which we need to
// insert p.
Node x = front.next;
while (x.data < temp.data)
x = x.next;
// Insert new node before temp
(x.prev).next = temp;
temp.prev = x.prev;
x.prev = temp;
temp.next = x;
}
// Driver code
public static void main(String args[])
{ int size=0;
front = back = null;
Scanner sc=new Scanner(System.in);
System.out.println("enter the size of the linked list");
size=sc.nextInt();
System.out.println("enter the elements of doubly linked list");
for(int i=0;i<size;i++){
int num=sc.nextInt();
insert(num);
}
System.out.println("printing doublylinked list in a sorted manner after insertion");
// printList(head);
while (front != null)
{
System.out.print(front.data + " ");
front = front.next;
}
}
}
Output
Complexity analysis
Time complexity
O(N), where n is a total number of nodes that require the node's traversal in a sorted doubly linked list.
Space complexity
O(1) will be the space complexity of inserting the nodes in a sorted doubly linked list.