Doubly Linked List in Java
Doubly Linked List In Java
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;
}
} 
Operations on a Doubly Linked List
Following operations can be performed on a doubly linked list:-
- Insertion
- Insertion at the beginning.
- Insertion at the end.
- Insertion at a specific position.
- Deletion
- Deletion from the beginning.
- Deletion from the end.
- Deletion from a specific position.
In our examples, we will focus on insertion/deletion at beginning
Code for Adding a Node in Doubly Linked List
Method 1
Method 2
Method 1
This method uses class instances to call functions.
Run
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;
System.out.println(newNode.data + " inserted");
}
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.display();
dll.insertNode(23);
dll.insertNode(22);
dll.insertNode(21);
dll.insertNode(20);
dll.display();
}
}Output
26 inserted 25 inserted 24 inserted In forward: 24 25 26 In backward: 26 25 24 23 inserted 22 inserted 21 inserted 20 inserted In forward: 20 21 22 23 24 25 26 In backward: 26 25 24 23 22 21 20
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 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;
System.out.println(newNode.data + " inserted");
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);
display(head);
head = insertNode(head,23);
head = insertNode(head,22);
head = insertNode(head,21);
head = insertNode(head,20);
display(head);
}
}Output
26 inserted 25 inserted 24 inserted In forward: 24 25 26 In backward: 26 25 24 23 inserted 22 inserted 21 inserted 20 inserted In forward: 20 21 22 23 24 25 26 In backward: 26 25 24 23 22 21 20
Code for Deleting a Node in Doubly Linked List
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
Method 1
Method 2
Method 1
This method uses class instances to call functions.
Run
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.
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
{
// 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
Fun Fact
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.
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
Singly Linked List
- Introduction to Linked List in Data Structure
Click Here - Linked List in –
- Singly Linked List in –
- Insertion in singly Linked List –
- Insertion at beginning in singly Linked List –
- Insertion at nth position in singly Linked List –
- Insertion at end in singly Linked List –
- Deletion in singly Linked List –
- Deletion from beginning in singly linked list :
- Deletion from nth position in singly linked list :
- Deletion from end in singly linked list :
- Linked List Insertion and Deletion –
C | C++ | Java - Reverse a linked list without changing links between nodes (Data reverse only) –
C | C++ | Java - Reverse a linked list by changing links between nodes –
- Print reverse of a linked list without actually reversing –
- Print reverse of a linked list without actually reversing –
- Insertion in the middle Singly Linked List –
- Insertion in a Sorted Linked List –
- Delete alternate nodes of a Linked List –
- Find middle of the linked list –
- Reverse a linked list in groups of given size –
- Find kth node from end of the linked list –
- Append the last n nodes of a linked list to the beginning of the list –
- Check whether linked list is palindrome or not –
- Fold a Linked List –
- Insert at given Position –
- Deletion at given Position –
Singly Linked List
- Introduction to Linked List in Data Structure
- Linked List in – C | C++ | Java
- Singly Linked List in – C | C++ | Java
- Insertion in singly Linked List – C | C++ | Java
- Deletion in singly Linked List – C | C++ | Java
- Reverse a linked list without changing links between nodes (Data reverse only) – C | C++ | Java
- Linked List Insertion and Deletion – C | C++ | Java
- Reverse a linked list by changing links between nodes – C | C++ | Java
- Linked List insertion in the middle – C | C++ | Java
- Print reverse of a linked list without actually reversing – C |C++ | Java
- Search an element in a linked list – C | C++ | Java
- Insertion in a Sorted Linked List – C | C++ | Java
- Delete alternate nodes of a Linked List – C | C++ | Java
- Find middle of the linked list – C | C++ | Java
- Reverse a linked list in groups of given size – C | C++ | Java
- Find kth node from end of the linked list – C | C++ | Java
- Append the last n nodes of a linked list to the beginning of the list – C | C++ | Java
- Check whether linked list is palindrome or not – C | C++ | Java
- Fold a Linked List – C | C++ | Java
- Insert at a given position – C | C++ | Java
- Delete at a given position – C | C++ | Java
Login/Signup to comment