Mastering Doubly Linked Lists in Java: A Comprehensive Guide
Doubly Linked Lists are a fundamental data structure in computer science, particularly in Java programming. They offer efficient insertion, deletion, and traversal operations compared to other data structures like arrays or singly linked lists. In this blog, we’ll delve into the concept of doubly linked lists, their implementation in Java, and explore some common operations associated with them.
What is a Doubly Linked List?
A Doubly Linked List is a type of linked list where each node contains a data element and two references or pointers: one pointing to the next node in the sequence, and another pointing to the previous node. This bidirectional linkage allows traversal in both forward and backward directions, making operations like insertion and deletion more efficient compared to singly linked lists.
Each node in a doubly linked list typically has the following structure:
class Node {
int data;
Node prev;
Node next;
}Here, data represents the value stored in the node, prev is a reference to the previous node, and next is a reference to the next node.
How to represent Doubly Linked List in java?
Doubly Linked List:
- It is called a two-way linked list.
- Given a node, we can navigate the list in both forward and backward directions, which is not possible in a singly linked list.
- In a singly linked list, a node can only be deleted if we have a pointer to its previous node. However, in a doubly linked list, we can delete the node even if we don’t have a pointer to its previous node.
- ListNode in a Doubly Linked List:
<------| previous | data | next |------->
In this visual representation:
<------indicates the direction of the previous pointers.|prev|represents the pointer to the previous node.|data|represents the data stored in the node.|next|represents the pointer to the next node.------->indicates the direction of the next pointers.
Each node in the doubly linked list contains pointers to both the previous and next nodes, allowing bidirectional traversal.
ListNode in a Doubly Linked List:
public class ListNode {
int data;
ListNode previous;
ListNode next;
public ListNode(int data) {
this.data = data;
}
}
Doubly Linked List:
null <-----head-----> 1 <-------> 10 <-------> 15 <-------> 65 <------tail-----> null
Doubly Linked List node has two pointers: previous and next. The list has two pointers:
headpoints to the first node.tailpoints to the last node of the list.
How to implement Doubly Linked List in java ?
public class DoublyLinkedList {
private ListNode head;
private ListNode tail;
private int length;
private class ListNode {
private int data;
private ListNode next;
private ListNode previous;
public ListNode(int data) {
this.data = data;
}
}
public DoublyLinkedList() {
this.head = null;
this.tail = null;
this.length = 0;
}
public boolean isEmpty() {
return length == 0; // head == null
}
public int length() {
return length;
}
}
This Java class DoublyLinkedList defines a doubly linked list. It includes inner class ListNode for representing each node in the list. The class provides methods to check if the list is empty and to get the length of the list. The constructor initializes the head and tail pointers to null and sets the length to 0.
Common Operations of Doubly Linked List in java
Here are some common operations performed on a doubly linked list:
- Insertion: Elements can be inserted at the beginning, end, or at any specific position within the list.
- Deletion: Elements can be deleted from the list based on their value or position.
- Traversal: Traversing the list from the beginning to the end or vice versa.
- Search: Searching for a specific element within the list.
- Reverse: Reversing the order of elements in the list.
How to print elements of Doubly Linked List in java?
null<-----head------> 1 <-------> 10 <-------> 15 <-------> 25 <------tail------>nullHere, we use two algorithms to print data:
i) It will start from the head and print data until the end, i.e., Forward Direction.
ii) It will start from the tail and print data until the end, i.e., Backward Direction.
Forward Direction Print
ListNode temp = head;
while(temp != null)
{
System.out.print(temp.data + "-->");
temp = temp.next;
}
System.out.println("null");
Here, we use a temporary node for traversing purposes. We assign the head node to it, i.e., ListNode temp = head;. Next, we move until the end of the list from the head. While traversing, we print data, and when we reach the end, our while loop terminates. That’s why we need to print ‘null’ on the next line.
Output: 1–>10–>15–>25–>null
Code
public void displayForward() {
if (head == null) {
return;
}
ListNode temp = head;
while (temp != null) {
System.out.print(temp.data + "-->");
temp = temp.next;
}
System.out.println("null");
}
This method displayForward is designed to print the elements of the doubly linked list in the forward direction. It starts from the head node and traverses the list, printing the data of each node followed by an arrow (-->). Finally, it prints null to indicate the end of the list. If the list is empty (i.e., head is null), the method simply returns without performing any operation.
Backward Direction Print
ListNode temp = tail;
while(temp != null)
{
System.out.print(temp.data + "-->");
temp = temp.previous;
}
System.out.println("null");
Here, we use a temporary node for traversing purposes. We assign the tail node to it, i.e., ListNode temp = tail;. Next, we move back until the end of the list from the tail. While traversing, we print data, and when we reach the end, our while loop terminates. That’s why we need to print ‘null’ on the next line.
Output: 25 –> 15 –> 10 –> 1 –> null
Code
public void displayBackward() {
if (tail == null) {
return;
}
ListNode temp = tail;
while (temp != null) {
System.out.print(temp.data + "-->");
temp = temp.previous;
}
System.out.println("null");
}
This method displayBackward is designed to print the elements of the doubly linked list in the backward direction. It starts from the tail node and traverses the list, printing the data of each node followed by an arrow (-->). Finally, it prints null to indicate the end of the list. If the list is empty (i.e., tail is null), the method simply returns without performing any operation.
How to insert node at the beginning of Doubly Linked List?
ListNode newNode = new ListNode(value);
if(isEmpty())
{
tail = newNode;
}
else
{
head.previous = newNode;
}
newNode.next = head;
head = newNode;
length++; // as we inserted node successfully increase the length by one
Here, the head node plays a major role, while the tail node is only considered when the list node is empty. At that time, both head and tail point to null. So when we insert a new node, we assign it to the tail. At that time, the new node’s previous and next pointers point to null, and both head and tail point to that new node. But the next time when our list contains nodes, how do we insert at the beginning?
Inserting at the beginning means we need to assign newNode to the head’s previous pointer so that the new node will be before the head node. Still, the new node’s next pointer needs to be assigned to the head so that a two-way connection is built between every node.
Finally, we have successfully inserted the new node at the beginning. Our head should point to the new node, so we update it accordingly. However, our tail remains the same at the last node only.
Output:
null<---|previous|10|next|<------->|previous|1|next|---->null // here head --> 10 and tail --> 1Code
public void insertFirst(int value) {
ListNode newNode = new ListNode(value);
if (isEmpty()) {
tail = newNode;
} else {
head.previous = newNode;
}
newNode.next = head;
head = newNode;
length++;
}This method insertFirst is designed to insert a new node with the given value at the beginning of the doubly linked list. If the list is empty, the new node becomes both the head and the tail of the list. Otherwise, the new node is inserted before the current head node, and its next reference is updated to point to the current head node. Finally, the length of the list is incremented.
How to insert node at the end of a Doubly Linked List in Java?
ListNode newNode = new ListNode(value);
if(isEmpty())
{
head = newNode;
}
else
{
tail.next = newNode;
newNode.previous = tail;
}
tail = newNode;
The logic is similar to the insertion at the beginning. Here, the tail pointer plays a major role as it points to the end of the list. When the list is empty, both head and tail will point to null. Now, we create a new node with the given value, but its previous and next pointers point to null. So, when the list is empty and we add a new node at the end of the list, it means we only need to point head and tail to the new node. But from the next insertion onward, adjacent nodes will point to each other, maintaining the two-way nature of the main doubly linked list. Therefore, we will add the new node to the tail node’s next pointer, and the new node’s previous pointer will point to the tail node. Here, the head remains the same, only the tail will change every time.
Finally, after every successful insertion, we need to increment the length by 1.
Output:
null<-----|previous|1|next|<--------->|previous|10|next|------>null // here head --> 1 and newNode & tail --> 10Code
public void insertLast(int value) {
ListNode newNode = new ListNode(value);
if (isEmpty()) {
head = newNode; // If the list is initially empty, assign the new node to the head
} else {
// Establish two-way connection between the new node and the current tail node
tail.next = newNode;
newNode.previous = tail;
}
tail = newNode; // Update the tail to point to the new node
length++; // Increment the length of the list by 1
}
This method insertLast is designed to insert a new node with the given value at the end of the doubly linked list. If the list is initially empty, the new node becomes the head of the list. Otherwise, it establishes a two-way connection between the new node and the current tail node, and updates the tail pointer to point to the new node. Finally, it increments the length of the list by 1.
How to delete first node in doubly linked list in java ?
//Sample Input:
null<---|previous|1|next|<------>|previous|10|next|<-------->|previous|15|next|--->null // here head --> 1 and tail --> 15if(isEmpty())
{
throw new NoSuchElementException();
}
ListNode temp = head;
if(head == tail)
{
tail = null;
}
else
{
head.next.previous = null;
}
head = head.next;
temp.next = null;
length--;
return temp;
Here, the tail will not play any major role because it is at the end of the list, and we want to delete the first node. So, the head will play a major role in this case. We assign the head node to the temporary node ‘temp’ because we want to delete the first node.
If the list has only one node, which is also the last node, it means head and tail should point to the same value. In such cases, the tail will be assigned with null, and the head will move to the next pointer, which may also be null. Additionally, we assign null to the temp’s next node, and return the temp node. Furthermore, we need to reduce the length by 1.
If the list has more than one node, we first move to the head’s next node and then remove its previous node. Then, we change the head to the next node so that we remove the head node. Using the statement ‘temp.next = null;’, we remove the head node and return it. Additionally, we need to reduce the length by 1.
Code
public ListNode deleteFirst() {
if (isEmpty()) {
throw new NoSuchElementException();
}
ListNode temp = head;
if (head == tail) {
tail = null;
} else {
head.next.previous = null;
}
head = head.next;
temp.next = null;
length--;
return temp;
}
This method deleteFirst is designed to delete the first node of the doubly linked list and return the deleted node. If the list is empty, it throws a NoSuchElementException. Otherwise, it removes the head node from the list. If the list contains only one node (head and tail are the same), it sets the tail to null. Otherwise, it updates the previous reference of the next node after the head to null. Finally, it updates the head pointer to the next node, decrements the length of the list, and returns the deleted node.
How to delete last node in Doubly Linked List in java ?
if(isEmpty())
{
throw new NoSuchElementException();
}
ListNode temp = tail;
if(head == tail)
{
head = null;
}
else
{
tail.previous.next = null;
}
tail = tail.previous;
temp.previous = null;
length--;
return temp;
If the list is empty, we throw a NoSuchElementException.
When the list contains only one node, at that time, both head and tail point to the same node. Here, only head will play a major role; elsewhere, the tail plays an important role. To delete the last node in this case, we assign null to head, and the tail’s previous will become the new tail. Then, we delete the tail and return it.
When the list contains more than one node, we delete the connection between two adjacent nodes. We move to the tail’s previous node, then back to the next node and assign null to it. Next, we move our current tail to its previous node, and finally, we remove the connection between the tail and its previous node by setting temp.previous to null. We then return the last node.
Code
public ListNode deleteLast() {
if (isEmpty()) {
throw new NoSuchElementException();
}
ListNode temp = tail;
if (head == tail) {
head = null;
} else {
tail.previous.next = null;
}
tail = tail.previous;
temp.previous = null;
length--;
return temp;
}
This method deleteLast is designed to delete the last node of the doubly linked list and return the deleted node. If the list is empty, it throws a NoSuchElementException. Otherwise, it removes the tail node from the list. If the list contains only one node (head and tail are the same), it sets the head to null. Otherwise, it updates the next reference of the previous node of the tail to null. Finally, it updates the tail pointer to the previous node, decrements the length of the list, and returns the deleted node.
Advantages of Doubly Linked Lists
Doubly linked lists offer several advantages over other data structures:
- Bidirectional traversal: Unlike singly linked lists, where traversal is only possible in one direction, doubly linked lists allow traversal in both forward and backward directions.
- Efficient insertion and deletion: Insertion and deletion operations can be performed more efficiently in doubly linked lists since only the adjacent nodes need to be updated.
- Dynamic size: Doubly linked lists can grow or shrink dynamically, allowing for efficient memory utilization.
Conclusion
Doubly linked lists are a versatile data structure that provides efficient operations for dynamic storage and retrieval of data. Understanding their implementation and common operations is essential for any Java programmer. By utilizing the bidirectional traversal and efficient insertion/deletion capabilities, doubly linked lists offer an excellent alternative to arrays or singly linked lists in various programming scenarios.
