Insertion in the middle Doubly Linked List in Java

Java Program for insertion in the middle of a Doubly Linked List

We will be looking at a couple of methods to Do Insertion in the middle of a Doubly Linked List in Java
linked list box
  • Method 1: Using size variable
  • Method 2: Using the function to calculate the size
Insertion in the middle of Doubly Linked List in Java

Let us look at both the methods below –

import java.lang.*;

class LinkedList {
    Node head;
    int size = 0;

    // 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)
    {
        Node newNode = new Node(data);
        newNode.next = head;
        newNode.prev = null;

        if(head !=null)
            head.prev = newNode;

        head = newNode;
        size++;
    }
    public void insertMiddle(int data) {
        Node newNode = new Node(data);

        // if the LL was empty
        if(head == null){
            // using insert function to insert at start
            insert(data);
            return;
        }

        // otherwise
        // find correct insertion position for middle
        int mid = (size % 2 == 0) ? (size/2) : (size+1)/2;

        // will only happen when there is one node in Doubly Linked List
        // we will have to insert at the last,
        // inserting 2nd node at the last
        // Example size = 1 will result in mid = 1 so entering after 1st node
        // where size itself is 1 so entering last node
        if(mid == size){
            newNode.next = null;
            newNode.prev = head;
            head.next = newNode;
            size++;
            return;
        }

        Node temp = head;
        // traverse to current mid position
        while(--mid > 0){
            temp = temp.next;
        }

        // (mid+1)th node prev to this newNode
        (temp.next).prev = newNode;
        // newNode's prev to this current middle node
        newNode.prev = temp;
        // newNode's next to (mid+1)th node
        newNode.next = temp.next;
        // current mid node's next becomes this newNode
        temp.next = newNode;
        size++;
    }

    public void display()
    {
        System.out.println("\n");
        Node node = head;
        Node end = null;

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

        System.out.print("\nList in backward direction: ");

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


    public static void main(String args[])
    {
        LinkedList ll = new LinkedList();

        ll.insert(4);
        ll.insert(0);

        ll.display();

        ll.insertMiddle(1);
        ll.display();

        ll.insertMiddle(3);
        ll.display();

        ll.insertMiddle(2);
        ll.display();
    }


}

Output

List in forward direction: 0 4 
List in backward direction: 4 0 


List in forward direction: 0 1 4 
List in backward direction: 4 1 0 


List in forward direction: 0 1 3 4 
List in backward direction: 4 3 1 0 


List in forward direction: 0 1 2 3 4 
List in backward direction: 4 3 2 1 0
import java.lang.*;

class LinkedList {
    Node head;
    // 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)
    {
        Node newNode = new Node(data);
        newNode.next = head;
        newNode.prev = null;

        if(head !=null)
            head.prev = newNode;

        head = newNode;
    }
    public void insertMiddle(int data) {
        Node newNode = new Node(data);

        // if the LL was empty
        if(head == null){
            // using insert function to insert at start
            insert(data);
            return;
        }

        // otherwise
        // find correct insertion position for middle
        int size = findSize();
        int mid = (size % 2 == 0) ? (size/2) : (size+1)/2;

        // will only happen when there is one node in Doubly Linked List
        // we will have to insert at the last,
        // inserting 2nd node at the last
        // Example size = 1 will result in mid = 1 so entering after 1st node
        // where size itself is 1 so entering last node
        if(mid == size){
            newNode.next = null;
            newNode.prev = head;
            head.next = newNode;
            size++;
            return;
        }

        Node temp = head;
        // traverse to current mid position
        while(--mid > 0){
            temp = temp.next;
        }

        // (mid+1)th node prev to this newNode
        (temp.next).prev = newNode;
        // newNode's prev to this current middle node
        newNode.prev = temp;
        // newNode's next to (mid+1)th node
        newNode.next = temp.next;
        // current mid node's next becomes this newNode
        temp.next = newNode;
        size++;
    }

    public int findSize(){
        int size = 0;

        Node node = head;

        while(node!=null){
            node = node.next;
            size++;
        }
        return size;
    }
    public void display()
    {
        System.out.println("\n");
        Node node = head;
        Node end = null;

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

        System.out.print("\nList in backward direction: ");

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


    public static void main(String args[])
    {
        LinkedList ll = new LinkedList();

        ll.insert(4);
        ll.insert(0);

        ll.display();

        ll.insertMiddle(1);
        ll.display();

        ll.insertMiddle(3);
        ll.display();

        ll.insertMiddle(2);
        ll.display();
    }


}

Output

List in forward direction: 0 4 
List in backward direction: 4 0 


List in forward direction: 0 1 4 
List in backward direction: 4 1 0 


List in forward direction: 0 1 3 4 
List in backward direction: 4 3 1 0 


List in forward direction: 0 1 2 3 4 
List in backward direction: 4 3 2 1 0

Doubly Linked List

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 nth node in doubly linked list –
    C | C++ | Java
  • Deletion in doubly linked list  –
    C | C++ | Java
  • Deletion from beginning in doubly linked list :
  • 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