Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem statement
1.2.
Sample Examples
2.
Approach
2.1.
Algorithm
2.2.
Java code
2.2.1.
Complexity analysis
3.
Frequently Asked Questions
3.1.
What is a double-linked list?
3.2.
What is the difference between single and doubly linked lists?
3.3.
How do you create a doubly-linked list?
4.
Conclusion
Last Updated: Mar 27, 2024
Easy

Sorted insert in a doubly-linked list with head and tail pointers

Author Ashish Sharma
0 upvote

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; 
             } 
   } 
}
You can also try this code with Online Java Compiler
Run Code

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.

Frequently Asked Questions

What is a double-linked list?

A Doubly Linked List is a Data Structure, a variation of the Linked Lists, where traversal is possible in both directions, forward and backward, easily compared to the singly linked Lists.

What is the difference between single and doubly linked lists?

Both Single List and doubly Link List are a Link List. An especially linked list contains data and a link for the next node. While in a double-linked list, each node includes a link to the previous node.

How do you create a doubly-linked list?

First of all, define a class that contains two nodes: the head node and the tail node.

  • Initially, the head and tail should point to null.
  • Define a new 'current' node that will point to the head.
  • Print the current node data until the current node points to the null.
  • The current node will point to the next node in the list for each loop iteration.

Conclusion

In this article, we have discussed how to insert in a sorted doubly linked list with O(n) time complexity. We have discussed its optimal approach and we have also discussed the complexities of that approach. 

After reading about the sorted insert in a doubly LinkedList with head and tail pointers, are you not feeling excited to read/explore more articles on the topic of file systems? Don't worry; Coding Ninjas has you covered. To learn, see Operating SystemUnix File SystemFile System Routing, and File Input/Output.

Recommended Problems -

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem 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!

Live masterclass