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.
Method to insert a node in the middle of the doubly linked list
- Method 1: Using size variable
- Method 2: Using the function to calculate the size
Java Program for insertion in the middle of a Doubly Linked List
Method 1
Method 2
Method 1
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
Method 2
Run
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() {
Node node = head;
Node end = null;
System.out.println("List in forward direction: ");
while (node != null) {
System.out.print(node.data + " ");
end = node;
node = node.next;
}
System.out.println();
System.out.println("List in backward direction: ");
while (end != null) {
System.out.print(end.data + " ");
end = end.prev;
}
System.out.println("\n");
}
}
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 List in forward direction: 0 4 List in backward direction: 4 0 List after insertion List in forward direction: 0 1 4 List in backward direction: 4 1 0
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
Doubly Linked List
- Introduction to Doubly Linked list in Data Structure
Click Here - Doubly Linked List in –
- Insertion in doubly linked list –
- Insertion at beginning in doubly linked list –
- Insertion at end in doubly linked list –
- Insertion at nth node in doubly linked list –
- 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 a doubly linked list :
- Insertion in the middle in a doubly linked list :
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
- Deletion 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
Login/Signup to comment