Insert value in sorted way of doubly linked list

There are three possible position to insert new node of linked list. inserting beginning position , inserting node at end of linked list and inserting node at specified position of between two nodes. There is all situation are used to sorted insertion in doubly linked list.

2) In other case linked list are not empty then find linked list node which are greater than newly inserted nodes. In this situation are three possibility.

a) When if first node is largest then add this node to front of linked list and on head pointer are assign the reference of this new node. This is situation of insert node at beginning.

b) If there is not find any big node of new inserted node in existing linked list then this node are inserted on last position of linked list. This is situation of insert node at end position.

c) If insert node is found in intermediate position, then add this node of this position.

Note that doubly linked list every node are two pointer fields that pointer are hold the reference of next and previous node address. When inserting new node that is also stratified this properties.

Suppose we are inserted the following (5,3,11,4,6,1,8,12) node in a sequence.

Here given code implementation process.

``````// Java Program
// Insert node in sorted way

// Define class of linked list Node
{
public int data;
{
this.data = data;
this.next = null;
this.prev = null;
}
}
{
{
// Set inital value
}
// Insert Node at sorted order
public void insert(int value)
{
// Create a dynamic node
{
return;
}
{
// When need to add node at begining position
}
else
{
// Find position to add new node
while (current != null && current.next != null &&
current.next.data <= value)
{
current = current.next;
}
// insert new node between the nodes
node.next = current.next;
if (current.next != null)
{
// When next node exists
current.next.prev = node;
}
node.prev = current;
current.next = node;
}
}
// Display node element of doubly linked list
public void display()
{
{
}
else
{
// Get first node of linked list
while (temp != null)
{
// Display node value
System.out.print("  " + temp.data);
last = temp;
// Visit to next node
temp = temp.next;
}
// Get last node of linked list
temp = last;
while (temp != null)
{
// Display node value
System.out.print("  " + temp.data);
// Visit to prev node
temp = temp.prev;
}
}
}
public static void main(String[] args)
{
// Insert following linked list nodes
dll.insert(5);
dll.insert(3);
dll.insert(11);
dll.insert(4);
dll.insert(6);
dll.insert(1);
dll.insert(8);
dll.insert(12);
dll.display();
}
}``````

Output

``````Linked List Head to Tail :  1  3  4  5  6  8  11  12
Linked List Tail to Head :  12  11  8  6  5  4  3  1``````
``````// C Program
// Insert value in sorted way
#include <stdio.h>
//For malloc function
#include <stdlib.h>

//Create structure
{
int data;
};
{
};
{
return list;
}
// Insert Node at sorted order
void insert(struct DoublyLinkedList * dll, int value)
{
// Create a dynamic node
if (node == NULL)
{
printf("Memory overflow\n");
}
else
{
// Set node value
node->next = NULL;
node->prev = NULL;
node->data = value;
{
return;
}
{
// When need to add node at begining position
}
else
{
// Find position to add new node
while (current != NULL && current->next != NULL && current->next->data <= value)
{
current = current->next;
}
// insert new node between the nodes
node->next = current->next;
if (current->next != NULL)
{
current->next->prev = node;
}
node->prev = current;
current->next = node;
}
}
}
// Display element of Node
{
{
}
else
{
struct LinkNode * last = NULL;
//Traverse doubly linked list from front to rear
while (temp != NULL)
{
//print node value
printf("%d  ", temp->data);
last = temp;
temp = temp->next;
}
// Get last node of linked list
temp = last;
while (temp != NULL)
{
// Display node value
printf(" %d ", temp->data);
// Visit to prev node
temp = temp->prev;
}
}
}
int main()
{
struct DoublyLinkedList * dll = newDLL();
insert(dll, 5);
insert(dll, 3);
insert(dll, 11);
insert(dll, 4);
insert(dll, 6);
insert(dll, 1);
insert(dll, 8);
insert(dll, 12);
//display all node
display(dll);
return 0;
}``````

Output

``````Linked List Head to Tail : 1  3  4  5  6  8  11  12
Linked List Tail to Head : 12  11  8  6  5  4  3  1``````
``````// Include header file
#include <iostream>
using namespace std;
// C++ Program
// Insert node in sorted way

// Define class of linked list Node
{
public: int data;
{
this->data = data;
this->next = NULL;
this->prev = NULL;
}
};
{
{
}
// Insert Node at sorted order
void insert(int value)
{
// Create a dynamic node
{
return;
}
{
// When need to add node at begining position
}
else
{
// Find position to add new node
while (current != NULL && current->next != NULL &&
current->next->data <= value)
{
current = current->next;
}
// insert new node between the nodes
node->next = current->next;
if (current->next != NULL)
{
// When next node exists
current->next->prev = node;
}
node->prev = current;
current->next = node;
}
}
// Display node element of doubly linked list
void display()
{
{
cout << "Empty Linked List" << endl;
}
else
{
// Get first node of linked list
while (temp != NULL)
{
// Display node value
cout << "  " << temp->data;
last = temp;
// Visit to next node
temp = temp->next;
}
// Get last node of linked list
temp = last;
while (temp != NULL)
{
// Display node value
cout << "  " << temp->data;
// Visit to prev node
temp = temp->prev;
}
}
}
};
int main()
{
// Insert following linked list nodes
dll->insert(5);
dll->insert(3);
dll->insert(11);
dll->insert(4);
dll->insert(6);
dll->insert(1);
dll->insert(8);
dll->insert(12);
dll->display();
return 0;
}``````

Output

``````Linked List Head to Tail :  1  3  4  5  6  8  11  12
Linked List Tail to Head :  12  11  8  6  5  4  3  1``````
``````package main
import "fmt"
// Go Program
// Insert node in sorted way
// Define class of linked list Node
data int
}
me.data = data
me.next = nil
me.prev = nil
return me
}
}
// Set inital value
return me
}
// Insert Node at sorted order
// Create a dynamic node
return
}
// When need to add node at begining position
} else {
// Find position to add new node
for (current != nil && current.next != nil &&
current.next.data <= value) {
current = current.next
}
// insert new node between the nodes
node.next = current.next
if current.next != nil {
// When next node exists
current.next.prev = node
}
node.prev = current
current.next = node
}
}
// Display node element of doubly linked list
} else {
// Get first node of linked list
var last * LinkNode = nil
for (temp != nil) {
// Display node value
fmt.Print("  ", temp.data)
last = temp
// Visit to next node
temp = temp.next
}
// Get last node of linked list
temp = last
for (temp != nil) {
// Display node value
fmt.Print("  ", temp.data)
// Visit to prev node
temp = temp.prev
}
}
}
func main() {
// Insert following linked list nodes
dll.insert(5)
dll.insert(3)
dll.insert(11)
dll.insert(4)
dll.insert(6)
dll.insert(1)
dll.insert(8)
dll.insert(12)
dll.display()
}``````

Output

``````Linked List Head to Tail :  1  3  4  5  6  8  11  12
Linked List Tail to Head :  12  11  8  6  5  4  3  1``````
``````// Include namespace system
using System;
// Csharp Program
// Insert node in sorted way

// Define class of linked list Node
{
public int data;
{
this.data = data;
this.next = null;
this.prev = null;
}
}
{
{
// Set inital value
}
// Insert Node at sorted order
public void insert(int value)
{
// Create a dynamic node
{
return;
}
{
// When need to add node at begining position
}
else
{
// Find position to add new node
while (current != null && current.next != null && current.next.data <= value)
{
current = current.next;
}
// insert new node between the nodes
node.next = current.next;
if (current.next != null)
{
// When next node exists
current.next.prev = node;
}
node.prev = current;
current.next = node;
}
}
// Display node element of doubly linked list
public void display()
{
{
}
else
{
// Get first node of linked list
while (temp != null)
{
// Display node value
Console.Write("  " + temp.data);
last = temp;
// Visit to next node
temp = temp.next;
}
// Get last node of linked list
temp = last;
while (temp != null)
{
// Display node value
Console.Write("  " + temp.data);
// Visit to prev node
temp = temp.prev;
}
}
}
public static void Main(String[] args)
{
// Insert following linked list nodes
dll.insert(5);
dll.insert(3);
dll.insert(11);
dll.insert(4);
dll.insert(6);
dll.insert(1);
dll.insert(8);
dll.insert(12);
dll.display();
}
}``````

Output

``````Linked List Head to Tail :  1  3  4  5  6  8  11  12
Linked List Tail to Head :  12  11  8  6  5  4  3  1``````
``````<?php
// Php Program
// Insert node in sorted way
// Define class of linked list Node
{
public \$data;
public \$next;
public \$prev;
public  function __construct(\$data)
{
\$this->data = \$data;
\$this->next = NULL;
\$this->prev = NULL;
}
}
{
public  function __construct()
{
}
// Insert Node at sorted order
public  function insert(\$value)
{
// Create a dynamic node
{
return;
}
{
// When need to add node at begining position
}
else
{
// Find position to add new node
while (\$current != NULL && \$current->next != NULL && \$current->next->data <= \$value)
{
\$current = \$current->next;
}
// insert new node between the nodes
\$node->next = \$current->next;
if (\$current->next != NULL)
{
// When next node exists
\$current->next->prev = \$node;
}
\$node->prev = \$current;
\$current->next = \$node;
}
}
// Display node element of doubly linked list
public  function display()
{
{
"\n");
}
else
{
// Get first node of linked list
\$last = NULL;
while (\$temp != NULL)
{
// Display node value
print_r("  ".strval(\$temp->data));
\$last = \$temp;
// Visit to next node
\$temp = \$temp->next;
}
// Get last node of linked list
\$temp = \$last;
while (\$temp != NULL)
{
// Display node value
print_r("  ".strval(\$temp->data));
// Visit to prev node
\$temp = \$temp->prev;
}
}
}
public static
function main(\$args)
{
// Insert following linked list nodes
\$dll->insert(5);
\$dll->insert(3);
\$dll->insert(11);
\$dll->insert(4);
\$dll->insert(6);
\$dll->insert(1);
\$dll->insert(8);
\$dll->insert(12);
\$dll->display();
}
}

Output

``````Linked List Head to Tail :  1  3  4  5  6  8  11  12
Linked List Tail to Head :  12  11  8  6  5  4  3  1``````
``````// Node JS Program
// Insert node in sorted way

// Define class of linked list Node
{
constructor(data)
{
this.data = data;
this.next = null;
this.prev = null;
}
}
{
constructor()
{
}
// Insert Node at sorted order
insert(value)
{
// Create a dynamic node
{
return;
}
{
// When need to add node at begining position
}
else
{
// Find position to add new node
while (current != null && current.next != null && current.next.data <= value)
{
current = current.next;
}
// insert new node between the nodes
node.next = current.next;
if (current.next != null)
{
// When next node exists
current.next.prev = node;
}
node.prev = current;
current.next = node;
}
}
// Display node element of doubly linked list
display()
{
{
}
else
{
// Get first node of linked list
var last = null;
while (temp != null)
{
// Display node value
process.stdout.write("  " + temp.data);
last = temp;
// Visit to next node
temp = temp.next;
}
// Get last node of linked list
temp = last;
while (temp != null)
{
// Display node value
process.stdout.write("  " + temp.data);
// Visit to prev node
temp = temp.prev;
}
}
}
}

function main()
{
// Insert following linked list nodes
dll.insert(5);
dll.insert(3);
dll.insert(11);
dll.insert(4);
dll.insert(6);
dll.insert(1);
dll.insert(8);
dll.insert(12);
dll.display();
}
main();``````

Output

``````Linked List Head to Tail :  1  3  4  5  6  8  11  12
Linked List Tail to Head :  12  11  8  6  5  4  3  1``````
``````#  Python 3 Program
#  Insert node in sorted way

#  Define class of linked list Node
def __init__(self, data) :
self.data = data
self.next = None
self.prev = None

def __init__(self) :

#  Insert Node at sorted order
def insert(self, value) :
#  Create a dynamic node
return

#  When need to add node at begining position
else :
#  Find position to add new node
while (current != None and current.next != None and
current.next.data <= value) :
current = current.next

#  insert new node between the nodes
node.next = current.next
if (current.next != None) :
#  When next node exists
current.next.prev = node

node.prev = current
current.next = node

#  Display node element of doubly linked list
def display(self) :
else :
#  Get first node of linked list
last = None
while (temp != None) :
#  Display node value
print("  ", temp.data, end = "")
last = temp
#  Visit to next node
temp = temp.next

#  Get last node of linked list
temp = last
while (temp != None) :
#  Display node value
print("  ", temp.data, end = "")
#  Visit to prev node
temp = temp.prev

def main() :
#  Insert following linked list nodes
dll.insert(5)
dll.insert(3)
dll.insert(11)
dll.insert(4)
dll.insert(6)
dll.insert(1)
dll.insert(8)
dll.insert(12)
dll.display()

if __name__ == "__main__": main()``````

Output

``````Linked List Head to Tail :   1   3   4   5   6   8   11   12
Linked List Tail to Head :   12   11   8   6   5   4   3   1``````
``````#  Ruby Program
#  Insert node in sorted way

#  Define class of linked list Node
attr_accessor :data, :next, :prev
def initialize(data)
self.data = data
self.next = nil
self.prev = nil
end

end

def initialize()
end

#  Insert Node at sorted order
def insert(value)
#  Create a dynamic node
return
end

#  When need to add node at begining position
else

#  Find position to add new node
while (current != nil && current.next != nil &&
current.next.data <= value)
current = current.next
end

#  insert new node between the nodes
node.next = current.next
if (current.next != nil)
#  When next node exists
current.next.prev = node
end

node.prev = current
current.next = node
end

end

#  Display node element of doubly linked list
def display()
else

#  Get first node of linked list
last = nil
while (temp != nil)
#  Display node value
print("  ", temp.data)
last = temp
#  Visit to next node
temp = temp.next
end

#  Get last node of linked list
temp = last
while (temp != nil)
#  Display node value
print("  ", temp.data)
#  Visit to prev node
temp = temp.prev
end

end

end

end

def main()
#  Insert following linked list nodes
dll.insert(5)
dll.insert(3)
dll.insert(11)
dll.insert(4)
dll.insert(6)
dll.insert(1)
dll.insert(8)
dll.insert(12)
dll.display()
end

main()``````

Output

``````Linked List Head to Tail :  1  3  4  5  6  8  11  12
Linked List Tail to Head :  12  11  8  6  5  4  3  1``````
``````// Scala Program
// Insert node in sorted way

// Define class of linked list Node
{
def this(data: Int)
{
this(data, null, null);
}
}
{
def this()
{
this(null);
}
// Insert Node at sorted order
def insert(value: Int): Unit = {
// Create a dynamic node
{
return;
}
{
// When need to add node at begining position
}
else
{
// Find position to add new node
while (current != null && current.next != null &&
current.next.data <= value)
{
current = current.next;
}
// insert new node between the nodes
node.next = current.next;
if (current.next != null)
{
// When next node exists
current.next.prev = node;
}
node.prev = current;
current.next = node;
}
}
// Display node element of doubly linked list
def display(): Unit = {
{
}
else
{
// Get first node of linked list
while (temp != null)
{
// Display node value
print("  " + temp.data);
last = temp;
// Visit to next node
temp = temp.next;
}
// Get last node of linked list
temp = last;
while (temp != null)
{
// Display node value
print("  " + temp.data);
// Visit to prev node
temp = temp.prev;
}
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
// Insert following linked list nodes
dll.insert(5);
dll.insert(3);
dll.insert(11);
dll.insert(4);
dll.insert(6);
dll.insert(1);
dll.insert(8);
dll.insert(12);
dll.display();
}
}``````

Output

``````Linked List Head to Tail :  1  3  4  5  6  8  11  12
Linked List Tail to Head :  12  11  8  6  5  4  3  1``````
``````// Swift 4 Program
// Insert node in sorted way

// Define class of linked list Node
{
var data: Int;
init(_ data: Int)
{
self.data = data;
self.next = nil;
self.prev = nil;
}
}
{
init()
{
}
// Insert Node at sorted order
func insert(_ value: Int)
{
// Create a dynamic node
{
return;
}
{
// When need to add node at begining position
}
else
{
// Find position to add new node
while (current  != nil && current!.next  != nil &&
current!.next!.data <= value)
{
current = current!.next;
}
// insert new node between the nodes
node.next = current!.next;
if (current!.next  != nil)
{
// When next node exists
current!.next!.prev = node;
}
node.prev = current;
current!.next = node;
}
}
// Display node element of doubly linked list
func display()
{
{
}
else
{
// Get first node of linked list
while (temp  != nil)
{
// Display node value
print("  ", temp!.data, terminator: "");
last = temp;
// Visit to next node
temp = temp!.next;
}
// Get last node of linked list
temp = last;
while (temp  != nil)
{
// Display node value
print("  ", temp!.data, terminator: "");
// Visit to prev node
temp = temp!.prev;
}
}
}
}
func main()
{
// Insert following linked list nodes
dll.insert(5);
dll.insert(3);
dll.insert(11);
dll.insert(4);
dll.insert(6);
dll.insert(1);
dll.insert(8);
dll.insert(12);
dll.display();
}
main();``````

Output

``````Linked List Head to Tail :   1   3   4   5   6   8   11   12
Linked List Tail to Head :   12   11   8   6   5   4   3   1``````
``````// Kotlin Program
// Insert node in sorted way

// Define class of linked list Node
{
var data: Int;
constructor(data: Int)
{
this.data = data;
this.next = null;
this.prev = null;
}
}
{
constructor()
{
}
// Insert Node at sorted order
fun insert(value: Int): Unit
{
// Create a dynamic node
{
return;
}
{
// When need to add node at begining position
}
else
{
// Find position to add new node
while (current != null && current.next != null &&
current.next!!.data <= value)
{
current = current.next;
}
// insert new node between the nodes
node.next = current?.next;
if (current?.next != null)
{
// When next node exists
current.next?.prev = node;
}
node.prev = current;
current?.next = node;
}
}
// Display node element of doubly linked list
fun display(): Unit
{
{
}
else
{
// Get first node of linked list
var last: LinkNode ? = null;
while (temp != null)
{
// Display node value
print("  " + temp.data);
last = temp;
// Visit to next node
temp = temp.next;
}
// Get last node of linked list
temp = last;
while (temp != null)
{
// Display node value
print("  " + temp.data);
// Visit to prev node
temp = temp.prev;
}
}
}
}
fun main(args: Array < String > ): Unit
{
// Insert following linked list nodes
dll.insert(5);
dll.insert(3);
dll.insert(11);
dll.insert(4);
dll.insert(6);
dll.insert(1);
dll.insert(8);
dll.insert(12);
dll.display();
}``````

Output

``````Linked List Head to Tail :  1  3  4  5  6  8  11  12
Linked List Tail to Head :  12  11  8  6  5  4  3  1``````

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.