Java Program for Insertion in Doubly Linked List

March 25, 2022

Insertion in a Doubly Linked List in Java

Lets have a look at the Java Program to Insert in a Doubly Linked List in Java. We will explore all the methods and positions to do insertion

In a doubly Linked List insertion can be done at the following positions –

At the beginning
At the end
After a given node

We will write the code for all the above cases. Let’s understand each one by one first.

Doubly Linked List Structure

Below is how node class is defined –

// Node Class
class Node{
    int data;
    Node next, prev;

    Node(int x) // parameterized constructor
    {
        data = x;
        next = null; 
        prev = null;     
    }
}

For Insertion in the Beginning of the List

Change the address in the Head of the list to the address of the New Node.
The previous of the New Node will point to null since it is the first node of the list.
The next of the New Node will point to the previous initial node of the list.

public void insertBeginning(int data)
{
    // Creating newNode memory & assigning data value
    Node freshNode = new Node(data);

    freshNode.next = head;
    freshNode.prev = null;

    // if DLL had already >=1 nodes
    if(head !=null)
        head.prev = freshNode;

    // changing head to this
    head = freshNode;
}

For Insertion in the End

Change the address in the Last Node of the list to the address of the New Node.
The previous of the New Node will point to the Previously Last Node of the list.
The next of the New Node will point to Null since the new node is the Last Node.

public void insertEnd(int data) {
    // Creating newNode memory & assigning data value
    Node freshNode = new Node(data);

    // assign data
    // since this will be the last node its next will be NULL
    freshNode.next = null;

    //if we are entering the first node
    if (head == null) {
        head = freshNode;
        freshNode.prev = null;
        return;
    }

    Node last = head;

    // traverse to the current last node
    while (last.next != null)
        last = last.next;

    // assign current last node's next to this new node
    // assign new node's previous to this last node
    last.next = freshNode;
    freshNode.prev = last;
    // new_node becomes the last node now

}

For Insertion at the Specific Position

So, here the Node is being inserted at the N^thposition in the list.
Change the address in the next of the (N-1)^th node of the list to the address of the New Node.
The previous of the New Node will point back to the (N-1)^th node of the list.
The next of the New Node will point to the (N+1)^th node of the list and vice versa.

public void insertAfterPosition(int n, int data) {
    int len = getLength(head);

    // if insertion position is 0 means entering at start
    if (n == 0) {
        insertBeginning(data);
        return;
    }
    // means inserting after last item
    if (n == len) {
        insertEnd(data);
        return;
    }

    // else insertion will happen somewhere in the middle


    if (n < 1 || len < n) 
        System.out.println("Invalid position");

    else {
        Node freshNode = new Node(data);

        // can remove null assignments also (constructor takes care of these)
        // added just for explanation purpose
        freshNode.next = null;
        freshNode.prev = null;

        // nthNode used to traverse the Linked List
        Node nthNode = head;

        // traverse till the nth node
        while (--n > 0) {
            nthNode = nthNode.next;
        }

        Node nextNode = nthNode.next; // (n+1)th node

        // assigning (n+1)th node's previous to this new node
        nextNode.prev = freshNode;

        // new_node's next assigned to (n+1)th node
        freshNode.next = nextNode;
        // new_node's previous assigned to nth node
        freshNode.prev = nthNode;

        // assign nth node's next to new_node
        nthNode.next = freshNode;
    }
}

// required for insertPosition() method
public int getLength(Node node) {
    int size = 0;
    // traverse to the last node each time incrementing the size
    while (node != null) {
        node = node.next;
        size++;
    }
    return size;
}

Complete Code for Insertion

Method 1

Method 2

Method 1

This method uses member functions of the class

Run

import java.lang.*;

class DoublyLinkedList {
    Node head;
    // not using parameterized constructor would by default
    // force head instance to become null
    // Node head = null;  // can also do this, but not required

    // Node Class
    class Node {
        int data;
        Node next, prev;

        Node(int x) // parameterized constructor
        {
            data = x;
            next = null;
            prev = null;
        }
    }

    public void insertBeginning(int data) {
        // Creating newNode memory & assigning data value
        Node freshNode = new Node(data);

        freshNode.next = head;
        freshNode.prev = null;

        // if DLL had already >=1 nodes
        if (head != null)
            head.prev = freshNode;

        // changing head to this
        head = freshNode;
    }

    public void insertEnd(int data) {
        // Creating newNode memory & assigning data value
        Node freshNode = new Node(data);

        // assign data
        // since this will be the last node its next will be NULL
        freshNode.next = null;

        //if we are entering the first node
        if (head == null) {
            head = freshNode;
            freshNode.prev = null;
            return;
        }

        Node last = head;

        // traverse to the current last node
        while (last.next != null)
            last = last.next;

        // assign current last node's next to this new node
        // assign new node's previous to this last node
        last.next = freshNode;
        freshNode.prev = last;
        // new_node becomes the last node now

    }

    public void insertAfterPosition(int n, int data) {
        int len = getLength(head);

        // if insertion position is 0 means entering at start
        if (n == 0) {
            insertBeginning(data);
            return;
        }
        // means inserting after last item
        if (n == len) {
            insertEnd(data);
            return;
        }

        // else insertion will happen somewhere in the middle


        if (n < 1 || len < n) System.out.println("Invalid position");

        else {
            Node freshNode = new Node(data);

            // can remove null assignments also (constructor takes care of these)
            // added just for explanation purpose
            freshNode.next = null;
            freshNode.prev = null;

            // nthNode used to traverse the Linked List
            Node nthNode = head;

            // traverse till the nth node
            while (--n > 0) {
                nthNode = nthNode.next;
            }

            Node nextNode = nthNode.next; // (n+1)th node

            // assigning (n+1)th node's previous to this new node
            nextNode.prev = freshNode;

            // new_node's next assigned to (n+1)th node
            freshNode.next = nextNode;
            // new_node's previous assigned to nth node
            freshNode.prev = nthNode;

            // assign nth node's next to new_node
            nthNode.next = freshNode;
        }
    }

    public void printList() {
        Node node = head;
        Node end = null;
        //as linked list will end when Node reaches Null

        System.out.print("\nIn forward: ");
        while (node != null) {
            System.out.print(node.data + " ");
            end = node;
            node = node.next;
        }
        System.out.print("\nIn backward: ");

        while (end != null) {
            System.out.print(end.data + " ");
            end = end.prev;
        }
        System.out.println();
    }

    // required for insertPosition() method
    public int getLength(Node node) {
        int size = 0;
        // traverse to the last node each time incrementing the size
        while (node != null) {
            node = node.next;
            size++;
        }
        return size;
    }

}
class Main{

    public static void main(String args[])
    {
        DoublyLinkedList doublylist = new DoublyLinkedList();

        doublylist.insertBeginning(3);
        doublylist.insertBeginning(2);
        doublylist.insertBeginning(1);

        doublylist.printList();

        doublylist.insertEnd(4);
        doublylist.insertEnd(6);
        doublylist.insertEnd(7);
        doublylist.insertEnd(8);

        doublylist.printList();

        //Inserts after 4th position
        doublylist.insertAfterPosition(4,5);

        doublylist.printList();
    }
}

Output

In forward: 1 2 3 
In backward: 3 2 1 

In forward: 1 2 3 4 6 7 8 
In backward: 8 7 6 4 3 2 1 

In forward: 1 2 3 4 5 6 7 8 
In backward: 8 7 6 5 4 3 2 1

Method 2

This method uses static methods to call functions.

Run

import java.lang.*;

// Node Class
class Node {
    int data;
    Node next, prev;

    Node(int x) // parameterized constructor
    {
        data = x;
        next = null;
        prev = null;
    }
}

class Main
{
    static Node insertBeginning(Node head, int data)
    {
        // Creating newNode memory & assigning data value
        Node newNode = new Node(data);

        newNode.next = head;
        newNode.prev = null;

        // if DLL had already >=1 nodes
        if(head !=null)
            head.prev = newNode;

        // changing head to this
        head = newNode;

        return head;
    }

    static Node insertEnd(Node head, int data) {

        // Creating newNode memory & assigning data value
        Node newNode = new Node(data);

        // assign data
        // since this will be the last node its next will be NULL
        newNode.next = null;

        //if we are entering the first node
        if(head==null){
            head = newNode;
            newNode.prev = null;
            return head;
        }

        Node last = head;

        // traverse to the current last node
        while(last.next!=null)
            last = last.next;

        // assign current last node's next to this new node
        // assign new node's previous to this last node
        last.next = newNode;
        newNode.prev = last;
        // new_node becomes the last node now

        return head;
    }

    static Node insertAfterPosition(int n, int data, Node head) {
        int len = getLength(head);

        // if insertion position is 0 means entering at start
        if(n == 0){
            head = insertBeginning(head, data);
            return head;
        }
        // means inserting after last item
        if(n == len){
            head = insertEnd(head, data);
            return head;
        }

        // else insertion will happen somewhere in the middle


        if(n < 1 || len < n)
            System.out.println("Invalid position");

        else
        {
            Node newNode = new Node(data);

            // can remove null assignments also (constructor takes care of these)
            // added just for explanation purpose
            newNode.next = null;
            newNode.prev = null;

            // nthNode used to traverse the Linked List
            Node nthNode = head; // traverse till the nth node

            while(--n > 0){
                nthNode = nthNode.next;
            }

            Node nextNode = nthNode.next; // (n+1)th node

            // assigning (n+1)th node's previous to this new node
            nextNode.prev = newNode;

            // new_node's next assigned to (n+1)th node
            newNode.next= nextNode;
            // new_node's previous assigned to nth node
            newNode.prev = nthNode;

            // assign nth node's next to new_node
            nthNode.next = newNode;
        }
        return head;
    }

    static void printList(Node temp) {

        Node end = null;
        //as linked list will end when Node reaches Null

        System.out.print("\nIn forward: ");
        while(temp!=null)
        {
            System.out.print(temp.data + " ");
            end = temp;
            temp = temp.next;
        }
        System.out.print("\nIn backward: ");

        while (end != null) {
            System.out.print(end.data + " ");
            end = end.prev;
        }
        System.out.println();
    }

    // required for insertAfterPosition() method
    static int getLength(Node node){
        int size=0;

        // traverse to the last node each time incrementing the size
        while(node!=null)
        {
            node = node.next;
            size++;
        }
        return size;
    }

    public static void main(String args[])
    {
        Node head = null;
        head = insertBeginning(head,3);
        head = insertBeginning(head,2);
        head = insertBeginning(head,1);

        printList(head);

        head = insertEnd(head,4);
        head = insertEnd(head,6);
        head = insertEnd(head,7);
        head = insertEnd(head,8);

        printList(head);

        //Inserts after 4th position
        head = insertAfterPosition(4,5,head);

        printList(head);

    }
}

Output

In forward: 1 2 3 
In backward: 3 2 1 

In forward: 1 2 3 4 6 7 8 
In backward: 8 7 6 4 3 2 1 

In forward: 1 2 3 4 5 6 7 8 
In backward: 8 7 6 5 4 3 2 1

 import java.util.*;

    public class PrepInsta
    {  

        //Represent a node of the doubly linked list  

        class DoublyLinkedList{  
            int d;  
            Node prev;  
            Node next;  

            public Node(int d) {  
                this.d = d;  
            }  
        }  

        //Represent the head and tail of the doubly linked list  
        Node head, tail = null;  

        //addNode will add a node to the list  
        public void addNode(int d) {  
              //Create a new node  
              Node newNode = new Node(d);  

            //If list is empty  
            if(head == null) {  
                //Both head and tail will point to newNode  
                head = tail = newNode;  
                //head's previous will point to null  
                head.prev = null;  
                //tail's next will point to null, as it is the last node of the list  
                tail.next = null;  
            }  
            else {  
                //newNode will be added after tail such that tail's next will point to newNode  
                tail.next = newNode;  
                //newNode's previous will point to tail  
                newNode.prev = tail;  
                //newNode will become new tail  
                tail = newNode;  
                //As it is last node, tail's next will point to null  
                tail.next = null;  
            }  
        }  

        //display() will print out the nodes of the list  
        public void display() {  
            //Node current will point to head  
            Node curr = head;  
            if(head == null) {  
                System.out.println("List is empty");  
                return;  
            }  
            System.out.println("Nodes of doubly linked list: ");  
            while(curr != null) {  
                //Prints each node by incrementing the pointer.  

                System.out.print(curr.d + " ");  
                curr = curr.next;  
            }  
        }  

        public static void main(String[] args) {  

            PrepInsta dList = new PrepInsta();  
            //Add nodes to the list  
            dList.addNode(1);  
            dList.addNode(2);  
            dList.addNode(3);  
            dList.addNode(4);  
            dList.addNode(5);  

            //Displays the nodes present in the list  
            dList.display();  
        }  
    }

Java Program for Insertion in Doubly Linked List

Insertion in a Doubly Linked List in Java

Doubly Linked List Structure

For Insertion in the Beginning of the List

For Insertion in the End​

For Insertion at the Specific Position​

Complete Code for Insertion

Output

Output

For Insertion in the End

For Insertion at the Specific Position