JAVA Program for Insertion at the Nth Position of a Doubly Linked List
Java Program for Insertion at the Nth Position
The Process of insertion in a doubly linked list is somewhat similar to the process of insertion in a Singly Linked List, the difference here is just that here we have a extra pointer (Previous) that needs to be directed to the address of the node lying before the node that is being Inserted.
Steps to be followed while Inserting a Node at a Specific location of a Doubly Linked List
- Check for the presence of Node in the List, if there exists some Nodes, Continue.
- Now, to insert a node at the Nth Position of the Doubly Linked List, we’ll have to store and redirect various links of the Linked List.
- First of all the address stored in the next pointer of the (n-1)th node of the List will now store the address of the New Node that is being inserted.
- Now the address stored in the Previous Pointer of the (n+1)th node of the Linked List will also be re-directed to the address of the New Node being inserted.
- Now, at last the Previous Pointer of the New Node will be directed towards the address of the node at (n-1)th position and the Next Pointer of the New Node will be directed towards the address of the node at (n+1)th position.
Algorithm to insert a node at the specific position in a doubly linked list
- Node node=new Node()
- node.data=data
- node.nextNode=null
- if(this.head==null)
- if(location!=0)
- return
- else
- this.head=node
- if(head!=null&&location==0)
- node.nextNode=this.head
- this.head=node
- return
- Node curr=this.head
- Node prev =Nnull
- while(i=0)
- tempNode=tempNode.nextNode
Java program to Insert a Node at the Specific Position in a Doubly Linked List
Method 1
Method 2
Method 1
Run
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 insertBeginning(int data) {
// Creating newNode memory & assigning data value
Node freshNode = new Node(data);
freshNode.next = head;
freshNode.prev = null;
// if DLL had already >=1 nodes
if (head != null)
head.prev = freshNode;
// changing head to this
head = freshNode;
}
public void insertEnd(int data) {
// Creating newNode memory & assigning data value
Node freshNode = new Node(data);
// assign data
// since this will be the last node its next will be NULL
freshNode.next = null;
//if we are entering the first node
if (head == null) {
head = freshNode;
freshNode.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 = freshNode;
freshNode.prev = last;
// new_node becomes the last node now
}
public void insertAfterPosition(int n, int data) {
int len = getLength(head);
// if insertion position is 0 means entering at start
if (n == 0) {
insertBeginning(data);
return;
}
// means inserting after last item
if (n == len) {
insertEnd(data);
return;
}
// else insertion will happen somewhere in the middle
if (n < 1 || len < n) System.out.println("Invalid position");
else { Node freshNode = new Node(data);
// can remove null assignments also (constructor takes care of these)
// added just for explanation purpose
freshNode.next = null;
freshNode.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 = freshNode;
// new_node's next assigned to (n+1)th node
freshNode.next = nextNode;
// new_node's previous assigned to nth node
freshNode.prev = nthNode;
// assign nth node's next to new_node
nthNode.next = freshNode;
}
}
public void printList() {
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 getLength(Node node) {
int size = 0;
// traverse to the last node each time incrementing the size
while (node != null) {
node = node.next;
size++;
}
return size;
}
}
class Main{
public static void main(String args[])
{
DoublyLinkedList doublylist = new DoublyLinkedList();
doublylist.insertBeginning(3);
doublylist.insertBeginning(2);
doublylist.insertBeginning(1);
doublylist.insertBeginning(4);
doublylist.insertBeginning(7);
//Inserts after 4th position
doublylist.insertAfterPosition(4,5);
doublylist.printList();
}
}
Output
In forward: 7 4 1 2 5 3 In backward: 3 5 2 1 4 7
Method 2
Run
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 insertBeginning(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 insertEnd(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 insertAfterPosition(int n, int data, Node head) {
int len = getLength(head);
// if insertion position is 0 means entering at start
if(n == 0){
head = insertBeginning(head, data);
return head;
}
// means inserting after last item
if(n == len){
head = insertEnd(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 printList(Node temp) {
Node end = null;
//as linked list will end when Node reaches Null
System.out.print("\nIn forward: ");
while(temp!=null)
{
System.out.print(temp.data + " ");
end = temp;
temp = temp.next;
}
System.out.print("\nIn backward: ");
while (end != null) {
System.out.print(end.data + " ");
end = end.prev;
}
System.out.println();
}
// required for insertAfterPosition() method
static int getLength(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 = insertBeginning(head,3);
head = insertBeginning(head,2);
head = insertBeginning(head,1);
head = insertBeginning(head,4);
head = insertBeginning(head,7);
//Inserts after 4th position
head = insertAfterPosition(4,5,head);
printList(head);
}
}
Output
In forward: 7 4 1 2 5 3 In backward: 3 5 2 1 4 7
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