Doubly Linked List Insertion and Deletion in Java

Java Program for Insertion and Deletion in Doubly Linked List

Lets have a look on the code for Doubly Linked List Insertion and Deletion in Java. We will look at different methods available to do so and both deletion and insertion at various positions possible.

java

Doubly Linked List Introduction

Just like a singly linked list in Java, a doubly-linked list is also a non-contiguous data structure.

Which is basically a chain of nodes connected to one another.

Each node has the following –

  • Data
  • Next Node reference
  • Previous Node reference
  • Head reference

The head reference basically denotes the first node(start) of the doubly linked list.

Some versions also contain something called as tail reference which denotes the last node in the doubly linked list.

Doubly Linked List in Java

Possible positions to insert or delete

We can insert or delete at the following positions in the doubly linked list –

  • At start
  • At end
  • In the middle (After a position)

Below are programs for all positions insertion/deletion in Java.

Doubly Linked List in Java an example

Structure of a Node in Doubly Linked List Java

Below is how a node is initialized in Java for a Doubly Linked List –

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

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

Doubly Linked List Insertion in Java

Let us look at the program below –

This method uses class instances to call functions.

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

    public void insertLast(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;
        }

        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

    }

    public void insertPosition(int n,int data)
    {
        int len = calcSize(head);

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

        // 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; } } public void display() { 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 calcSize(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[]) { DoublyLinkedList dll = new DoublyLinkedList(); dll.insertStart(12); dll.insertStart(8); dll.insertStart(4); dll.display(); dll.insertLast(20); dll.insertLast(24); dll.insertLast(28); dll.insertLast(32); dll.display(); //Inserts after 3rd position dll.insertPosition(3,100); dll.display(); } }

Output

In forward: 4 8 12 
In backward: 12 8 4

In forward: 4 8 12 20 24 28 32
In backward: 32 28 24 20 12 8 4

In forward: 4 8 12 100 20 24 28 32
In backward: 32 28 24 20 100 12 8 4

This method uses static methods to call functions.

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 insertStart(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 insertLast(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 insertPosition(int n, int data, Node head) {
        int len = calcSize(head);

        // if insertion position is 0 means entering at start
        if(n == 0){
            head = insertStart(head, data);
            return head;
        }
        // means inserting after last item
        if(n == len){
            head = insertLast(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 display(Node node) { 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 static int calcSize(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 = insertStart(head,3); head = insertStart(head,2); head = insertStart(head,1); display(head); head = insertLast(head,5); head = insertLast(head,6); head = insertLast(head,7); head = insertLast(head,8); display(head); //Inserts after 3rd position head = insertPosition(3,25,head); display(head); } }

Output

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

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

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

Doubly Linked List Deletion in Java

Let us look at the program below –

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

    public void deleteStart(){
        Node temp = head;

        // if DLL is empty
        if(head == null){
            System.out.println("Linked List Empty, nothing to delete");
            return;
        }

        // if Linked List has only 1 node
        if(temp.next == null){
            System.out.println(temp.data + " deleted");
            head = null;
            return;
        }

        // move head to next node
        head = head.next;
        // assign head node's previous to NULL
        head.prev = null;

        System.out.println(temp.data + " deleted");
    }
    public void deleteLast()
    {
        Node temp = head;

        // if DLL is empty
        if(head == null){
            System.out.println("DLL empty can't delete");
            return;
        }

        // if Linked List has only 1 node
        if(temp.next == null){
            System.out.println(temp.data + " deleted");
            head = null;
            return;
        } // else traverse to the last node

        while (temp.next != null)
            temp = temp.next;

        Node secondLast = temp.prev;

        // Curr assign 2nd last node's next to Null
        secondLast.next = null;

        System.out.println(temp.data + " deleted");

    }

    public void deleteNthNode(int n)
    {
        //if the head node itself needs to be deleted
        int len = calcSize(head);

        // not valid
        if(n < 1 || n > len){
            System.out.println("Not a valid position");
            return;
        }

        // delete the first node
        if(n == 1){
            deleteStart();
            return;
        }

        if(n == len){
            deleteLast();
            return;
        }

        Node temp = head;

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

        Node previousNode = temp.prev; // (n-1)th node
        Node nextNode = temp.next; // (n+1)th node

        // assigning (n-1)th node's next pointer to (n+1)th node
        previousNode.next = temp.next;

        // assigning (n+1)th node's previous pointer to (n-1)th node
        nextNode.prev = temp.prev;

        // deleting nth node
        System.out.println(temp.data + " deleted");
    }

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

        System.out.print("In 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("\n");
    }
    // required for insertPosition() method
    public int calcSize(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[])
    {
        DoublyLinkedList dll = new DoublyLinkedList();

        dll.insert(24);
        dll.insert(20);
        dll.insert(16);
        dll.insert(12);
        dll.insert(8);
        dll.insert(4);
        dll.insert(0);

        dll.display();

        dll.deleteStart();
        dll.display();

        dll.deleteLast();
        dll.deleteLast();
        dll.display();

        //deletes after 3rd position
        dll.deleteNthNode(3);

        dll.display();
    }
}

Output

In forward: 0 4 8 12 16 20 24 
In backward: 24 20 16 12 8 4 0 

0 deleted
In forward: 4 8 12 16 20 24 
In backward: 24 20 16 12 8 4 

24 deleted
20 deleted
In forward: 4 8 12 16 
In backward: 16 12 8 4 

12 deleted
In forward: 4 8 16 
In backward: 16 8 4 
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
{
    public static Node deleteStart(Node head)
    {
        Node temp = head;

        // if DLL is empty
        if(head == null){
            System.out.println("Linked List Empty, nothing to delete");
            return head;
        }

        // if Linked List has only 1 node
        if(temp.next == null){
            System.out.println(temp.data + " deleted");
            head = null;
            return head;
        }

        // move head to next node
        head = head.next;
        // assign head node's previous to NULL
        head.prev = null;

        System.out.println(temp.data + " deleted");

        return head;
    }
    static Node deleteLast(Node head) {
        Node temp = head;

        // if DLL is empty
        if(head == null){
            System.out.println("DLL empty can't delete");
            return head;
        }

        // if Linked List has only 1 node
        if(temp.next == null){
            System.out.println(temp.data + " deleted");
            head = null;
            return head;
        } // else traverse to the last node

        while (temp.next != null)
            temp = temp.next;

        Node secondLast = temp.prev;

        // Curr assign 2nd last node's next to Null
        secondLast.next = null;

        System.out.println(temp.data + " deleted");
        return head;
    }

    static Node deleteNthNode(int n, Node head) {
        //if the head node itself needs to be deleted
        int len = calcSize(head);

        // not valid
        if(n < 1 || n > len){
            System.out.println("Not a valid position");
            return head;
        }

        // delete the first node
        if(n == 1){
            head = deleteStart(head);
            return head;
        }

        if(n == len){
            head = deleteLast(head);
            return head;
        }

        Node temp = head;

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

        Node previousNode = temp.prev; // (n-1)th node
        Node nextNode = temp.next; // (n+1)th node

        // assigning (n-1)th node's next pointer to (n+1)th node
        previousNode.next = temp.next;

        // assigning (n+1)th node's previous pointer to (n-1)th node
        nextNode.prev = temp.prev;

        // deleting nth node
        System.out.println(temp.data + " deleted");
        return head;
    }
    public static Node insert(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 void display(Node head) {

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

        System.out.print("In 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("\n");
    }

    // required for insertPosition() method
    static int calcSize(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 = insert(head,24);
        head = insert(head,20);
        head = insert(head,16);
        head = insert(head,12);
        head = insert(head,8);
        head = insert(head,4);
        head =  insert(head,0);

        display(head);

        head = deleteStart(head);
        display(head);

        head = deleteLast(head);
        head = deleteLast(head);
        display(head);

        //Inserts after 3rd position
        head = deleteNthNode( 3,head);
        display(head);


    }
}

Output

In forward: 0 4 8 12 16 20 24 
In backward: 24 20 16 12 8 4 0 

0 deleted
In forward: 4 8 12 16 20 24 
In backward: 24 20 16 12 8 4 

24 deleted
20 deleted
In forward: 4 8 12 16 
In backward: 16 12 8 4 

12 deleted
In forward: 4 8 16 
In backward: 16 8 4