Programming
Aptitude
Syllabus
Interview Preparation
Interview Exp.
Off Campus
Doubly Linked List Insertion and Deletion in Java
Java Program for Insertion and Deletion in Doubly Linked List
Lets have a look on the code for Doubly Linked List Insertion and Deletion in Java. We will look at different methods available to do so and both deletion and insertion at various positions possible.
Doubly Linked List Introduction
Just like a singly linked list in Java, a doubly-linked list is also a non-contiguous data structure.
Which is basically a chain of nodes connected to one another.
Each node has the following –
- Data
- Next Node reference
- Previous Node reference
- Head reference
The head reference basically denotes the first node(start) of the doubly linked list.
Some versions also contain something called as tail reference which denotes the last node in the doubly linked list.
Possible positions to insert or delete
We can insert or delete at the following positions in the doubly linked list –
- At start
- At end
- In the middle (After a position)
Below are programs for all positions insertion/deletion in Java.
Structure of a Node in Doubly Linked List Java
Below is how a node is initialized in Java for a Doubly Linked List –
// Node Class
class Node{
int data;
Node next, prev;
Node(int x) // parameterized constructor
{
data = x;
next = null;
prev = null;
}
}Doubly Linked List Insertion in Java
Let us look at the program below –
Method 1
This method uses class instances to call functions.
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 insertStart(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;
}
public void insertLast(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;
}
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
}
public void insertPosition(int n,int data)
{
int len = calcSize(head);
// if insertion position is 0 means entering at start
if(n == 0){
insertStart(data);
return;
}
// means inserting after last item
if(n == len){
insertLast(data);
return;
}
// 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;
}
}
public void display()
{
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 calcSize(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[])
{
DoublyLinkedList dll = new DoublyLinkedList();
dll.insertStart(12);
dll.insertStart(8);
dll.insertStart(4);
dll.display();
dll.insertLast(20);
dll.insertLast(24);
dll.insertLast(28);
dll.insertLast(32);
dll.display();
//Inserts after 3rd position
dll.insertPosition(3,100);
dll.display();
}
}
Output
In forward: 4 8 12
In backward: 12 8 4
In forward: 4 8 12 20 24 28 32
In backward: 32 28 24 20 12 8 4
In forward: 4 8 12 100 20 24 28 32
In backward: 32 28 24 20 100 12 8 4
Method 2
This method uses static methods to call functions.
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 insertStart(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 insertLast(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 insertPosition(int n, int data, Node head) {
int len = calcSize(head);
// if insertion position is 0 means entering at start
if(n == 0){
head = insertStart(head, data);
return head;
}
// means inserting after last item
if(n == len){
head = insertLast(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 display(Node node) {
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
static int calcSize(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 = insertStart(head,3);
head = insertStart(head,2);
head = insertStart(head,1);
display(head);
head = insertLast(head,5);
head = insertLast(head,6);
head = insertLast(head,7);
head = insertLast(head,8);
display(head);
//Inserts after 3rd position
head = insertPosition(3,25,head);
display(head);
}
}Output
In forward: 1 2 3 In backward: 3 2 1 In forward: 1 2 3 5 6 7 8 In backward: 8 7 6 5 3 2 1 In forward: 1 2 3 25 5 6 7 8 In backward: 8 7 6 5 25 3 2 1
Doubly Linked List Deletion in Java
Let us look at the program below –
Method 1
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 insert(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;
}
public void deleteStart(){
Node temp = head;
// if DLL is empty
if(head == null){
System.out.println("Linked List Empty, nothing to delete");
return;
}
// if Linked List has only 1 node
if(temp.next == null){
System.out.println(temp.data + " deleted");
head = null;
return;
}
// move head to next node
head = head.next;
// assign head node's previous to NULL
head.prev = null;
System.out.println(temp.data + " deleted");
}
public void deleteLast()
{
Node temp = head;
// if DLL is empty
if(head == null){
System.out.println("DLL empty can't delete");
return;
}
// if Linked List has only 1 node
if(temp.next == null){
System.out.println(temp.data + " deleted");
head = null;
return;
} // else traverse to the last node
while (temp.next != null)
temp = temp.next;
Node secondLast = temp.prev;
// Curr assign 2nd last node's next to Null
secondLast.next = null;
System.out.println(temp.data + " deleted");
}
public void deleteNthNode(int n)
{
//if the head node itself needs to be deleted
int len = calcSize(head);
// not valid
if(n < 1 || n > len){
System.out.println("Not a valid position");
return;
}
// delete the first node
if(n == 1){
deleteStart();
return;
}
if(n == len){
deleteLast();
return;
}
Node temp = head;
// traverse to the nth node
while (--n > 0){
temp = temp.next;
}
Node previousNode = temp.prev; // (n-1)th node
Node nextNode = temp.next; // (n+1)th node
// assigning (n-1)th node's next pointer to (n+1)th node
previousNode.next = temp.next;
// assigning (n+1)th node's previous pointer to (n-1)th node
nextNode.prev = temp.prev;
// deleting nth node
System.out.println(temp.data + " deleted");
}
public void display()
{
Node node = head;
Node end = null;
//as linked list will end when Node reaches Null
System.out.print("In 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("\n");
}
// required for insertPosition() method
public int calcSize(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[])
{
DoublyLinkedList dll = new DoublyLinkedList();
dll.insert(24);
dll.insert(20);
dll.insert(16);
dll.insert(12);
dll.insert(8);
dll.insert(4);
dll.insert(0);
dll.display();
dll.deleteStart();
dll.display();
dll.deleteLast();
dll.deleteLast();
dll.display();
//deletes after 3rd position
dll.deleteNthNode(3);
dll.display();
}
}Output
In forward: 0 4 8 12 16 20 24 In backward: 24 20 16 12 8 4 0 0 deleted In forward: 4 8 12 16 20 24 In backward: 24 20 16 12 8 4 24 deleted 20 deleted In forward: 4 8 12 16 In backward: 16 12 8 4 12 deleted In forward: 4 8 16 In backward: 16 8 4
Method 2
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
{
public static Node deleteStart(Node head)
{
Node temp = head;
// if DLL is empty
if(head == null){
System.out.println("Linked List Empty, nothing to delete");
return head;
}
// if Linked List has only 1 node
if(temp.next == null){
System.out.println(temp.data + " deleted");
head = null;
return head;
}
// move head to next node
head = head.next;
// assign head node's previous to NULL
head.prev = null;
System.out.println(temp.data + " deleted");
return head;
}
static Node deleteLast(Node head) {
Node temp = head;
// if DLL is empty
if(head == null){
System.out.println("DLL empty can't delete");
return head;
}
// if Linked List has only 1 node
if(temp.next == null){
System.out.println(temp.data + " deleted");
head = null;
return head;
} // else traverse to the last node
while (temp.next != null)
temp = temp.next;
Node secondLast = temp.prev;
// Curr assign 2nd last node's next to Null
secondLast.next = null;
System.out.println(temp.data + " deleted");
return head;
}
static Node deleteNthNode(int n, Node head) {
//if the head node itself needs to be deleted
int len = calcSize(head);
// not valid
if(n < 1 || n > len){
System.out.println("Not a valid position");
return head;
}
// delete the first node
if(n == 1){
head = deleteStart(head);
return head;
}
if(n == len){
head = deleteLast(head);
return head;
}
Node temp = head;
// traverse to the nth node
while (--n > 0){
temp = temp.next;
}
Node previousNode = temp.prev; // (n-1)th node
Node nextNode = temp.next; // (n+1)th node
// assigning (n-1)th node's next pointer to (n+1)th node
previousNode.next = temp.next;
// assigning (n+1)th node's previous pointer to (n-1)th node
nextNode.prev = temp.prev;
// deleting nth node
System.out.println(temp.data + " deleted");
return head;
}
public static Node insert(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 void display(Node head) {
Node node = head;
Node end = null;
//as linked list will end when Node reaches Null
System.out.print("In 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("\n");
}
// required for insertPosition() method
static int calcSize(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 = insert(head,24);
head = insert(head,20);
head = insert(head,16);
head = insert(head,12);
head = insert(head,8);
head = insert(head,4);
head = insert(head,0);
display(head);
head = deleteStart(head);
display(head);
head = deleteLast(head);
head = deleteLast(head);
display(head);
//Inserts after 3rd position
head = deleteNthNode( 3,head);
display(head);
}
}Output
In forward: 0 4 8 12 16 20 24 In backward: 24 20 16 12 8 4 0 0 deleted In forward: 4 8 12 16 20 24 In backward: 24 20 16 12 8 4 24 deleted 20 deleted In forward: 4 8 12 16 In backward: 16 12 8 4 12 deleted In forward: 4 8 16 In backward: 16 8 4
Login/Signup to comment