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.

Hint: 1) Initial linked list is empty so insert first node of linked list and assign this address to head pointer of 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.

insert sorted doubly linked list

Here given code implementation process.

// Java Program 
// Insert node in sorted way 

// Define class of linked list Node
class LinkNode
{
    public int data;
    public LinkNode next;
    public LinkNode prev;
    public LinkNode(int data)
    {
        this.data = data;
        this.next = null;
        this.prev = null;
    }
}
public class DoublyLinkedList
{
    public LinkNode head;
    public DoublyLinkedList()
    {
        // Set inital value
        this.head = null;
    }
    // Insert Node at sorted order
    public void insert(int value)
    {
        // Create a dynamic node
        LinkNode node = new LinkNode(value);
        if (this.head == null)
        {
            // Add first node
            this.head = node;
            return;
        }
        if (this.head.data >= node.data)
        {
            // When need to add node at begining position
            this.head.prev = node;
            node.next = this.head;
            this.head = node;
        }
        else
        {
            LinkNode current = this.head;
            // 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()
    {
        if (this.head == null)
        {
            System.out.println("Empty Linked List");
        }
        else
        {
            System.out.print("Linked List Head to Tail :");
            // Get first node of linked list
            LinkNode temp = this.head;
            LinkNode last = null;
            // iterate linked list 
            while (temp != null)
            {
                // Display node value
                System.out.print("  " + temp.data);
                last = temp;
                // Visit to next node
                temp = temp.next;
            }
            System.out.print("\nLinked List Tail to Head :");
            // Get last node of linked list
            temp = last;
            // iterate linked list 
            while (temp != null)
            {
                // Display node value
                System.out.print("  " + temp.data);
                // Visit to prev node
                temp = temp.prev;
            }
        }
    }
    public static void main(String[] args)
    {
        DoublyLinkedList dll = new DoublyLinkedList();
        // 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();
    }
}
Sorted insertion in doubly linked list

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
struct LinkNode
{
    int data;
    struct LinkNode * next;
    struct LinkNode * prev;
};
struct DoublyLinkedList
{
    struct LinkNode * head;
};
struct DoublyLinkedList * newDLL()
{
    struct DoublyLinkedList * list = (struct DoublyLinkedList * )
    malloc(sizeof(struct DoublyLinkedList));
    list->head = NULL;
    return list;
}
// Insert Node at sorted order
void insert(struct DoublyLinkedList * dll, int value)
{
    // Create a dynamic node
    struct LinkNode * node = (struct LinkNode * ) malloc(sizeof(struct LinkNode));
    if (node == NULL)
    {
        printf("Memory overflow\n");
    }
    else
    {
        // Set node value
        node->next = NULL;
        node->prev = NULL;
        node->data = value;
        if (dll->head == NULL)
        {
            // Add first node
            dll->head = node;
            return;
        }
        if (dll->head->data >= node->data)
        {
            // When need to add node at begining position
            dll->head->prev = node;
            node->next = dll->head;
            dll->head = node;
        }
        else
        {
            struct LinkNode * current = dll->head;
            // 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
void display(struct DoublyLinkedList * dll)
{
    if (dll->head == NULL)
    {
        printf("Empty linked list");
    }
    else
    {
        printf("\nLinked List Head to Tail : ");
        struct LinkNode * temp = dll->head;
        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;
        }
        printf("\nLinked List Tail to Head :");
        // Get last node of linked list
        temp = last;
        // iterate linked list 
        while (temp != NULL)
        {
            // Display node value
            printf(" %d ", temp->data);
            // Visit to prev node
            temp = temp->prev;
        }
    }
}
int main()
{
    struct DoublyLinkedList * dll = newDLL();
    //Insert element of linked list
    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
class LinkNode
{
    public: int data;
    LinkNode *next;
    LinkNode *prev;
    LinkNode(int data)
    {
        this->data = data;
        this->next = NULL;
        this->prev = NULL;
    }
};
class DoublyLinkedList
{
    public: LinkNode *head;
    DoublyLinkedList()
    {
        this->head = NULL;
    }
    // Insert Node at sorted order
    void insert(int value)
    {
        // Create a dynamic node
        LinkNode *node = new LinkNode(value);
        if (this->head == NULL)
        {
            // Add first node
            this->head = node;
            return;
        }
        if (this->head->data >= node->data)
        {
            // When need to add node at begining position
            this->head->prev = node;
            node->next = this->head;
            this->head = node;
        }
        else
        {
            LinkNode *current = this->head;
            // 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()
    {
        if (this->head == NULL)
        {
            cout << "Empty Linked List" << endl;
        }
        else
        {
            cout << "Linked List Head to Tail :";
            // Get first node of linked list
            LinkNode *temp = this->head;
            LinkNode *last = NULL;
            // iterate linked list 
            while (temp != NULL)
            {
                // Display node value
                cout << "  " << temp->data;
                last = temp;
                // Visit to next node
                temp = temp->next;
            }
            cout << "\nLinked List Tail to Head :";
            // Get last node of linked list
            temp = last;
            // iterate linked list 
            while (temp != NULL)
            {
                // Display node value
                cout << "  " << temp->data;
                // Visit to prev node
                temp = temp->prev;
            }
        }
    }
};
int main()
{
    DoublyLinkedList *dll = new DoublyLinkedList();
    // 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
type LinkNode struct {
    data int
    next * LinkNode
    prev * LinkNode
}
func getLinkNode(data int) * LinkNode {
    var me *LinkNode = &LinkNode {}
    me.data = data
    me.next = nil
    me.prev = nil
    return me
}
type DoublyLinkedList struct {
    head * LinkNode
}
func getDoublyLinkedList() * DoublyLinkedList {
    var me *DoublyLinkedList = &DoublyLinkedList {}
    // Set inital value
    me.head = nil
    return me
}
// Insert Node at sorted order
func(this *DoublyLinkedList) insert(value int) {
    // Create a dynamic node
    var node * LinkNode = getLinkNode(value)
    if this.head == nil {
        // Add first node
        this.head = node
        return
    }
    if this.head.data >= node.data {
        // When need to add node at begining position
        this.head.prev = node
        node.next = this.head
        this.head = node
    } else {
        var current * LinkNode = this.head
        // 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
func(this DoublyLinkedList) display() {
    if this.head == nil {
        fmt.Println("Empty Linked List")
    } else {
        fmt.Print("Linked List Head to Tail :")
        // Get first node of linked list
        var temp * LinkNode = this.head
        var last * LinkNode = nil
        // iterate linked list 
        for (temp != nil) {
            // Display node value
            fmt.Print("  ", temp.data)
            last = temp
            // Visit to next node
            temp = temp.next
        }
        fmt.Print("\nLinked List Tail to Head :")
        // Get last node of linked list
        temp = last
        // iterate linked list 
        for (temp != nil) {
            // Display node value
            fmt.Print("  ", temp.data)
            // Visit to prev node
            temp = temp.prev
        }
    }
}
func main() {
    var dll * DoublyLinkedList = getDoublyLinkedList()
    // 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 class LinkNode
{
    public int data;
    public LinkNode next;
    public LinkNode prev;
    public LinkNode(int data)
    {
        this.data = data;
        this.next = null;
        this.prev = null;
    }
}
public class DoublyLinkedList
{
    public LinkNode head;
    public DoublyLinkedList()
    {
        // Set inital value
        this.head = null;
    }
    // Insert Node at sorted order
    public void insert(int value)
    {
        // Create a dynamic node
        LinkNode node = new LinkNode(value);
        if (this.head == null)
        {
            // Add first node
            this.head = node;
            return;
        }
        if (this.head.data >= node.data)
        {
            // When need to add node at begining position
            this.head.prev = node;
            node.next = this.head;
            this.head = node;
        }
        else
        {
            LinkNode current = this.head;
            // 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()
    {
        if (this.head == null)
        {
            Console.WriteLine("Empty Linked List");
        }
        else
        {
            Console.Write("Linked List Head to Tail :");
            // Get first node of linked list
            LinkNode temp = this.head;
            LinkNode last = null;
            // iterate linked list 
            while (temp != null)
            {
                // Display node value
                Console.Write("  " + temp.data);
                last = temp;
                // Visit to next node
                temp = temp.next;
            }
            Console.Write("\nLinked List Tail to Head :");
            // Get last node of linked list
            temp = last;
            // iterate linked list 
            while (temp != null)
            {
                // Display node value
                Console.Write("  " + temp.data);
                // Visit to prev node
                temp = temp.prev;
            }
        }
    }
    public static void Main(String[] args)
    {
        DoublyLinkedList dll = new DoublyLinkedList();
        // 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
class LinkNode
{
    public $data;
    public $next;
    public $prev;
    public  function __construct($data)
    {
        $this->data = $data;
        $this->next = NULL;
        $this->prev = NULL;
    }
}
class DoublyLinkedList
{
    public $head;
    public  function __construct()
    {
        $this->head = NULL;
    }
    // Insert Node at sorted order
    public  function insert($value)
    {
        // Create a dynamic node
        $node = new LinkNode($value);
        if ($this->head == NULL)
        {
            // Add first node
            $this->head = $node;
            return;
        }
        if ($this->head->data >= $node->data)
        {
            // When need to add node at begining position
            $this->head->prev = $node;
            $node->next = $this->head;
            $this->head = $node;
        }
        else
        {
            $current = $this->head;
            // 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()
    {
        if ($this->head == NULL)
        {
            print_r("Empty Linked List".
                "\n");
        }
        else
        {
            print_r("Linked List Head to Tail :");
            // Get first node of linked list
            $temp = $this->head;
            $last = NULL;
            // iterate linked list 
            while ($temp != NULL)
            {
                // Display node value
                print_r("  ".strval($temp->data));
                $last = $temp;
                // Visit to next node
                $temp = $temp->next;
            }
            print_r("\nLinked List Tail to Head :");
            // Get last node of linked list
            $temp = $last;
            // iterate linked list 
            while ($temp != NULL)
            {
                // Display node value
                print_r("  ".strval($temp->data));
                // Visit to prev node
                $temp = $temp->prev;
            }
        }
    }
    public static
    function main($args)
    {
        $dll = new DoublyLinkedList();
        // 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();
    }
}

DoublyLinkedList::main(array());

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
class LinkNode
{
    constructor(data)
    {
        this.data = data;
        this.next = null;
        this.prev = null;
    }
}
class DoublyLinkedList
{
    constructor()
    {
        this.head = null;
    }
    // Insert Node at sorted order
    insert(value)
    {
        // Create a dynamic node
        var node = new LinkNode(value);
        if (this.head == null)
        {
            // Add first node
            this.head = node;
            return;
        }
        if (this.head.data >= node.data)
        {
            // When need to add node at begining position
            this.head.prev = node;
            node.next = this.head;
            this.head = node;
        }
        else
        {
            var current = this.head;
            // 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()
    {
        if (this.head == null)
        {
            console.log("Empty Linked List");
        }
        else
        {
            process.stdout.write("Linked List Head to Tail :");
            // Get first node of linked list
            var temp = this.head;
            var last = null;
            // iterate linked list 
            while (temp != null)
            {
                // Display node value
                process.stdout.write("  " + temp.data);
                last = temp;
                // Visit to next node
                temp = temp.next;
            }
            process.stdout.write("\nLinked List Tail to Head :");
            // Get last node of linked list
            temp = last;
            // iterate linked list 
            while (temp != null)
            {
                // Display node value
                process.stdout.write("  " + temp.data);
                // Visit to prev node
                temp = temp.prev;
            }
        }
    }
}

function main()
{
    var dll = new DoublyLinkedList();
    // 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
class LinkNode :
    def __init__(self, data) :
        self.data = data
        self.next = None
        self.prev = None
    

class DoublyLinkedList :
    def __init__(self) :
        self.head = None
    
    #  Insert Node at sorted order
    def insert(self, value) :
        #  Create a dynamic node
        node = LinkNode(value)
        if (self.head == None) :
            #  Add first node
            self.head = node
            return
        
        if (self.head.data >= node.data) :
            #  When need to add node at begining position
            self.head.prev = node
            node.next = self.head
            self.head = node
        else :
            current = self.head
            #  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) :
        if (self.head == None) :
            print("Empty Linked List")
        else :
            print("Linked List Head to Tail :", end = "")
            #  Get first node of linked list
            temp = self.head
            last = None
            #  iterate linked list 
            while (temp != None) :
                #  Display node value
                print("  ", temp.data, end = "")
                last = temp
                #  Visit to next node
                temp = temp.next
            
            print("\nLinked List Tail to Head :", end = "")
            #  Get last node of linked list
            temp = last
            #  iterate linked list 
            while (temp != None) :
                #  Display node value
                print("  ", temp.data, end = "")
                #  Visit to prev node
                temp = temp.prev
            
        
    

def main() :
    dll = DoublyLinkedList()
    #  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
class LinkNode 
    # Define the accessor and reader of class LinkNode
    attr_reader :data, :next, :prev
    attr_accessor :data, :next, :prev
    def initialize(data) 
        self.data = data
        self.next = nil
        self.prev = nil
    end

end

class DoublyLinkedList 
    # Define the accessor and reader of class DoublyLinkedList
    attr_reader :head
    attr_accessor :head
    def initialize() 
        self.head = nil
    end

    #  Insert Node at sorted order
    def insert(value) 
        #  Create a dynamic node
        node = LinkNode.new(value)
        if (self.head == nil) 
            #  Add first node
            self.head = node
            return
        end

        if (self.head.data >= node.data) 
            #  When need to add node at begining position
            self.head.prev = node
            node.next = self.head
            self.head = node
        else
 
            current = self.head
            #  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() 
        if (self.head == nil) 
            print("Empty Linked List", "\n")
        else
 
            print("Linked List Head to Tail :")
            #  Get first node of linked list
            temp = self.head
            last = nil
            #  iterate linked list 
            while (temp != nil) 
                #  Display node value
                print("  ", temp.data)
                last = temp
                #  Visit to next node
                temp = temp.next
            end

            print("\nLinked List Tail to Head :")
            #  Get last node of linked list
            temp = last
            #  iterate linked list 
            while (temp != nil) 
                #  Display node value
                print("  ", temp.data)
                #  Visit to prev node
                temp = temp.prev
            end

        end

    end

end

def main() 
    dll = DoublyLinkedList.new()
    #  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
class LinkNode(var data: Int,
    var next: LinkNode,
        var prev: LinkNode)
{
    def this(data: Int)
    {
        this(data, null, null);
    }
}
class DoublyLinkedList(var head: LinkNode)
{
    def this()
    {
        this(null);
    }
    // Insert Node at sorted order
    def insert(value: Int): Unit = {
        // Create a dynamic node
        var node: LinkNode = new LinkNode(value);
        if (this.head == null)
        {
            // Add first node
            this.head = node;
            return;
        }
        if (this.head.data >= node.data)
        {
            // When need to add node at begining position
            this.head.prev = node;
            node.next = this.head;
            this.head = node;
        }
        else
        {
            var current: LinkNode = this.head;
            // 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 = {
        if (this.head == null)
        {
            println("Empty Linked List");
        }
        else
        {
            print("Linked List Head to Tail :");
            // Get first node of linked list
            var temp: LinkNode = this.head;
            var last: LinkNode = null;
            // iterate linked list 
            while (temp != null)
            {
                // Display node value
                print("  " + temp.data);
                last = temp;
                // Visit to next node
                temp = temp.next;
            }
            print("\nLinked List Tail to Head :");
            // Get last node of linked list
            temp = last;
            // iterate linked list 
            while (temp != null)
            {
                // Display node value
                print("  " + temp.data);
                // Visit to prev node
                temp = temp.prev;
            }
        }
    }
}
object Main
{
    def main(args: Array[String]): Unit = {
        var dll: DoublyLinkedList = new DoublyLinkedList();
        // 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
class LinkNode
{
    var data: Int;
    var next: LinkNode? ;
    var prev: LinkNode? ;
    init(_ data: Int)
    {
        self.data = data;
        self.next = nil;
        self.prev = nil;
    }
}
class DoublyLinkedList
{
    var head: LinkNode? ;
    init()
    {
        self.head = nil;
    }
    // Insert Node at sorted order
    func insert(_ value: Int)
    {
        // Create a dynamic node
        let node: LinkNode = LinkNode(value);
        if (self.head == nil)
        {
            // Add first node
            self.head = node;
            return;
        }
        if (self.head!.data >= node.data)
        {
            // When need to add node at begining position
            self.head!.prev = node;
            node.next = self.head;
            self.head = node;
        }
        else
        {
            var current: LinkNode? = self.head;
            // 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()
    {
        if (self.head == nil)
        {
            print("Empty Linked List");
        }
        else
        {
            print("Linked List Head to Tail :", terminator: "");
            // Get first node of linked list
            var temp: LinkNode? = self.head;
            var last: LinkNode? = nil;
            // iterate linked list 
            while (temp  != nil)
            {
                // Display node value
                print("  ", temp!.data, terminator: "");
                last = temp;
                // Visit to next node
                temp = temp!.next;
            }
            print("\nLinked List Tail to Head :", terminator: "");
            // Get last node of linked list
            temp = last;
            // iterate linked list 
            while (temp  != nil)
            {
                // Display node value
                print("  ", temp!.data, terminator: "");
                // Visit to prev node
                temp = temp!.prev;
            }
        }
    }
}
func main()
{
    let dll: DoublyLinkedList = DoublyLinkedList();
    // 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
class LinkNode
{
    var data: Int;
    var next: LinkNode ? ;
    var prev: LinkNode ? ;
    constructor(data: Int)
    {
        this.data = data;
        this.next = null;
        this.prev = null;
    }
}
class DoublyLinkedList
{
    var head: LinkNode ? ;
    constructor()
    {
        this.head = null;
    }
    // Insert Node at sorted order
    fun insert(value: Int): Unit
    {
        // Create a dynamic node
        val node: LinkNode = LinkNode(value);
        if (this.head == null)
        {
            // Add first node
            this.head = node;
            return;
        }
        if (this.head!!.data >= node.data)
        {
            // When need to add node at begining position
            this.head?.prev = node;
            node.next = this.head;
            this.head = node;
        }
        else
        {
            var current: LinkNode ? = this.head;
            // 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
    {
        if (this.head == null)
        {
            println("Empty Linked List");
        }
        else
        {
            print("Linked List Head to Tail :");
            // Get first node of linked list
            var temp: LinkNode ? = this.head;
            var last: LinkNode ? = null;
            // iterate linked list 
            while (temp != null)
            {
                // Display node value
                print("  " + temp.data);
                last = temp;
                // Visit to next node
                temp = temp.next;
            }
            print("\nLinked List Tail to Head :");
            // Get last node of linked list
            temp = last;
            // iterate linked list 
            while (temp != null)
            {
                // Display node value
                print("  " + temp.data);
                // Visit to prev node
                temp = temp.prev;
            }
        }
    }
}
fun main(args: Array < String > ): Unit
{
    val dll: DoublyLinkedList = DoublyLinkedList();
    // 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.

New Comment







© 2021, kalkicode.com, All rights reserved