JAVA Program for Insertion at the Nth Position of a Doubly Linked List

February 14, 2023

Java Program for Insertion at the Nth Position

The Process of insertion in a doubly linked list is somewhat similar to the process of insertion in a Singly Linked List, the difference here is just that here we have a extra pointer (Previous) that needs to be directed to the address of the node lying before the node that is being Inserted.

Steps to be followed while Inserting a Node at a Specific location of a Doubly Linked List

Check for the presence of Node in the List, if there exists some Nodes, Continue.
Now, to insert a node at the Nth Position of the Doubly Linked List, we’ll have to store and redirect various links of the Linked List.
First of all the address stored in the next pointer of the (n-1)th node of the List will now store the address of the New Node that is being inserted.
Now the address stored in the Previous Pointer of the (n+1)th node of the Linked List will also be re-directed to the address of the New Node being inserted.
Now, at last the Previous Pointer of the New Node will be directed towards the address of the node at (n-1)th position and the Next Pointer of the New Node will be directed towards the address of the node at (n+1)th position.

Deletion in doubly linked list

Deletion from beginning in doubly linked list

Deletion from nth in doubly linked list

Deletion from end in doubly linked list

Insertion and Deletion in doubly linked list

Algorithm to insert a node at the specific position in a doubly linked list

Node node=new Node()
node.data=data
node.nextNode=null
if(this.head==null)
if(location!=0)
return
else
this.head=node
if(head!=null&&location==0)
node.nextNode=this.head
this.head=node
return
Node curr=this.head
Node prev =Nnull
while(i=0)
tempNode=tempNode.nextNode

Java program to Insert a Node at the Specific Position in a Doubly Linked List

Method 1

Method 2

Method 1

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.insertBeginning(4);
        doublylist.insertBeginning(7);

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

        doublylist.printList();
    }
}

Output

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

Method 2

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);
        head = insertBeginning(head,4);
        head = insertBeginning(head,7);


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

        printList(head);

    }
}

Output

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

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Doubly Linked List

Introduction to Doubly Linked list in Data Structure
Click Here
Doubly Linked List in –
C | C++ | Java
Insertion in doubly linked list –
C | C++ | Java
Insertion at beginning in doubly linked list –
C | C++ | Java
Insertion at end in doubly linked list –
C | C++ | Java
Insertion at n^th node in doubly linked list –
C | C++ | Java
Deletion in doubly linked list –
C | C++ | Java
Deletion from beginning in doubly linked list :
C | C++ | Java
Deletion from nth in doubly linked list :
C | C++ | Java
Deletion from end in doubly linked list :
C | C++ | Java
Insertion and Deletion in a doubly linked list :
C | C++ | Java
Insertion in the middle in a doubly linked list :
C | C++ | Java

Doubly Linked List

Introduction to Doubly Linked list in Data Structure
Doubly Linked List in – C | C++ | Java
Insertion in doubly linked list – C | C++ | Java
- Insertion at beginning in doubly linked list – C | C++ | Java
- Insertion at end in doubly linked list – C | C++ | Java
- Insertion at n^th node in doubly linked list – C | C++ | Java
Deletion in doubly linked list – C | C++ | Java
- Deletion from beginning in doubly linked list : C | C++ | Java
- Deletion from nth in doubly linked list : C | C++ | Java
- Deletion from end in doubly linked list : C | C++ | Java
Insertion and Deletion in doubly linked list – C | C++ | Java
Insertion in the middle in a doubly linked list – C | C++ | Java