Java Program for Insertion in Doubly Linked List

November 4, 2020

Insertion in a Doubly Linked List in JAVA Programming Language

Doubly Linked List is a mutated version of Linked List. Similar to a Linked List Doubly Linked List also Stores Data in a sequential format. Here, the difference is that in Doubly Linked List instead of having a single pointer to the next node in the list has two pointers in it, one pointing to the next node and another pointing to the adjacent previous node in the List. Hence the existence of these pointers makes traversing the list even faster. There are multiple operations that can be performed on a Doubly Linked List, One such operation is Insertion that is explained below.

Insertion in Doubly linked List in Java

Steps to be followed for Insertion in a Doubly Linked List

  • The foremost step is to create a Node and store data in the Node
  • After creating a node, check for whether the list is empty, if yes exit.
  • Now determine the position of insertion,  whether the node has to be inserted in the Beginning of the list, in the End or at a Specific Index
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 previously initial Node of the list.
Insertion in Beginning in Detail

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.
Insertion in End in Detail

For Insertion at the Specific Position​

  • So, here the Node is being inserted at the Nth
    position 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.
Insertion in at Specific Position in Detail

Insertion in the Beginning

Algorithm

  • AppendStart(int data)
  • Node newNode = new Node(data)
  • IF HEAD == NULL
    • newNode HEAD = TAIL = newNode
    • HEAD.previous = NULL
    • TAIL.next = NULL
  • ELSE
    • HEAD.previous = newNode
    • newNode.next = HEAD
    • newNode.previous = NULL
    •  HEAD = newNode
Insertion in Beginning in Detail
Insertion at beginning of a Doubly Linked List

Insertion in a Specific Location

Algorithm

  • appendAtEnd (data)
  • if(HEAD == NULL) 
    • HEAD = TAIL = newNode
    • HEAD.prev = NULL
    • TAIL.next = NULL
  • Else
    • TAIL.next = newNode
    • newNode.prev = TAIL
    • TAIL = newNode
    • TAIL.next = NULL
Insertion in at Specific Position in Detail
Insertion at end of a Doubly Linked List

Insertion in the End

Algorithm

  • appendAtEnd (data)
  • if(HEAD == NULL) 
    • HEAD = TAIL = newNode
    • HEAD.prev = NULL
    • TAIL.next = NULL
  • Else
    • TAIL.next = newNode
    • newNode.prev = TAIL
    • TAIL = newNode
    • TAIL.next = NULL
Insertion in End in Detail
Insertion at end of a Doubly Linked List

Java program for insertion in doubly linked list

 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();  
        }  
    }