Doubly Linked List in Java is a mutated version of Linked List.
Similar to a Linked List Doubly Linked List also stores data elements of homogeneous data type in a linear format
Structure of a Doubly Linked List in Java
The difference between a Linked List and a Doubly Linked is that singly linked list just has reference to the next node in the chain while doubly linked list has reference to both previous and next node in the chain
Components of doubly linked list are –
Data
Reference to the Next node
Reference to the Previous node
Doubly Linked List allows traversal in both forward and backward direction as for any node both previous and next nodes are known.
The first node is referred to as the head and the last node is referred to as the tail node.
// Node Class
class Node{
int data;
Node next, prev;
Node(int x) // parameterized constructor
{
data = x;
next = null;
prev = null;
}
}
Let us look at the code for deletion, we will for now focus on deletion from the start which is the default nature in a linked list. Which will require the following –
Checking if the doubly linked list is empty
No deletion possible
Checking if the doubly Linked list has a single node
Changing the head to null
Otherwise, moving the head node to next node and changing previous of new head to null
import java.lang.*;
class DoublyLinkedList {
Node head;
// Node Class
class Node {
int data;
Node next, prev;
Node(int x) // parameterized constructor
{
data = x;
next = null;
prev = null;
}
}
// inserts at first position
public void insertNode(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 deleteNode(){
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 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("\n");
}
}
class Main{
public static void main(String args[])
{
DoublyLinkedList dll = new DoublyLinkedList();
dll.insertNode(26);
dll.insertNode(25);
dll.insertNode(24);
dll.insertNode(23);
dll.insertNode(22);
dll.insertNode(21);
dll.insertNode(20);
dll.display();
dll.deleteNode();
dll.deleteNode();
dll.deleteNode();
dll.display();
}
}
Output
In forward: 20 21 22 23 24 25 26
In backward: 26 25 24 23 22 21 20
20 deleted
21 deleted
22 deleted
In forward: 23 24 25 26
In backward: 26 25 24 23
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
{
// inserts a node at the first position
static Node insertNode(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;
}
// deletes the first node in doubly linked list
public static Node deleteNode(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 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("\n");
}
public static void main(String args[])
{
Node head = null;
head = insertNode(head,26);
head = insertNode(head,25);
head = insertNode(head,24);
head = insertNode(head,23);
head = insertNode(head,22);
head = insertNode(head,21);
head = insertNode(head,20);
display(head);
head = deleteNode(head);
head = deleteNode(head);
head = deleteNode(head);
display(head);
}
}
Output
In forward: 20 21 22 23 24 25 26
In backward: 26 25 24 23 22 21 20
20 deleted
21 deleted
22 deleted
In forward: 23 24 25 26
In backward: 26 25 24 23
Merits of Doubly Linked List
A Doubly Linked List can be traversed in any given Direction Since it has pointers to both the next and the previous Node of the List.
It is easier to reverse a Doubly Linked List.
Both Deletion and Insertion and easier in a Doubly Linked List.
Demerits of Doubly Linked List
Every operation on a Doubly Linked List requires an extra step to perform calculations on that extra address stored with each node.
Every Node requires extra space in the memory to store that one extra address.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Doubly Linked List in Real Life can be seen implemented in back and forward buttons in a browser navigation. Also the undo and redo buttons are a great example of application of Doubly Linked List.
Login/Signup to comment