In a doubly Linked List insertion can be done at the following positions –
- At the beginning
- At the end
- After a given node
We will write the code for all the above cases. Let’s understand each one by one first.


Doubly Linked List Structure
Below is how node class is defined –
// Node Class class Node{ int data; Node next, prev; Node(int x) // parameterized constructor { data = x; next = null; prev = null; } }





For Insertion in the Beginning of the List
- Change the address in the Head of the list to the address of the New Node.
- The previous of the New Node will point to null since it is the first node of the list.
- The next of the New Node will point to the previous initial node of the list.





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; }
For Insertion in the End
- Change the address in the Last Node of the list to the address of the New Node.
- The previous of the New Node will point to the Previously Last Node of the list.
- The next of the New Node will point to Null since the new node is the Last Node.





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 }
For Insertion at the Specific Position
- So, here the Node is being inserted at the Nth
position in the list. - Change the address in the next of the (N-1)th node of the list to the address of the New Node.
- The previous of the New Node will point back to the (N-1)th node of the list.
- The next of the New Node will point to the (N+1)th node of the list and vice versa.





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; } } // 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; }
Complete Code for Insertion
Method 1
This method uses member functions of the class
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.printList(); doublylist.insertEnd(4); doublylist.insertEnd(6); doublylist.insertEnd(7); doublylist.insertEnd(8); doublylist.printList(); //Inserts after 4th position doublylist.insertAfterPosition(4,5); doublylist.printList(); } }
Output
In forward: 1 2 3 In backward: 3 2 1 In forward: 1 2 3 4 6 7 8 In backward: 8 7 6 4 3 2 1 In forward: 1 2 3 4 5 6 7 8 In backward: 8 7 6 5 4 3 2 1
Method 2
This method uses static methods to call functions.
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); printList(head); head = insertEnd(head,4); head = insertEnd(head,6); head = insertEnd(head,7); head = insertEnd(head,8); printList(head); //Inserts after 4th position head = insertAfterPosition(4,5,head); printList(head); } }
Output
In forward: 1 2 3 In backward: 3 2 1 In forward: 1 2 3 4 6 7 8 In backward: 8 7 6 4 3 2 1 In forward: 1 2 3 4 5 6 7 8 In backward: 8 7 6 5 4 3 2 1
Login/Signup to comment