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.

First we need to find the middle of the linked list then insert a node.

linked list box

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

Run
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() {

        Node node = head;
        Node end = null;


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

    }
}

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

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

        System.out.println("List before insertion");
        ll.display();

        ll.insertMiddle(1);

        System.out.println("List after insertion");
        ll.display();
    }
}

Output

List before insertion
0 4 
List after insertion
0 1 4 

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

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 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

Doubly Linked List