Introduction
A doubly linked list is an extension of the singly linked list, with added flexibility due to its two-way links between nodes. In a doubly linked list, each node points to both its next and previous nodes, enabling bidirectional traversal. This feature makes operations like insertion, deletion, and traversal faster in certain scenarios compared to singly linked lists. In this post, we’ll explore the doubly linked list structure, its advantages, and implement it step-by-step in Java. To learn more about linked lists, click here.
What is a Doubly Linked List?
A doubly linked list is a series of connected nodes where each node contains:
- Data: The value stored in the node.
- Next: A reference to the next node.
- Prev: A reference to the previous node.
By storing both forward and backward links, a doubly linked list allows:
- Bidirectional Traversal: Moving both forward and backward through the list.
- Efficient Deletion: Deleting a node in constant time when the node pointer is known.
Why Use a Doubly Linked List?
Doubly linked lists provide advantages over singly linked lists in several cases, such as:
- Bidirectional traversal is required.
- Deleting nodes without needing to traverse from the start.
- Efficient insertion and deletion operations at both ends of the list.
Doubly Linked List Implementation in Java
To implement a doubly linked list, we’ll break it down into three classes:
- Node – Represents each node in the list.
- DoublyLinkedList – Contains methods to manage the doubly linked list.
- Main – Demonstrates insertion, deletion, and traversal operations.
Step-by-Step Implementation
Step 1: Define the Node Class
Each node contains data, a pointer to the next node, and a pointer to the previous node.
class Node {
int data;
Node next;
Node prev;
public Node(int data) {
this.data = data;
this.next = null;
this.prev = null;
}
}Step 2: Create the DoublyLinkedList Class
This class will manage the linked list and its operations, such as insertion and deletion.
class DoublyLinkedList {
Node head;
public DoublyLinkedList() {
this.head = null;
}
}Step 3: Insert Nodes into the Doubly Linked List
We’ll create methods to add nodes at both the beginning and the end of the list.
- Insert at the Beginning:
public void insertAtBeginning(int data) {
Node newNode = new Node(data);
if (head != null) {
head.prev = newNode;
}
newNode.next = head;
head = newNode;
}- Insert at the End:
public void insertAtEnd(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
return;
}
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
newNode.prev = current;
}Step 4: Delete Nodes from the Doubly Linked List
We’ll create methods to delete a node from the beginning and a specific node by its value.
- Delete at the Beginning:
public void deleteAtBeginning() {
if (head != null) {
head = head.next;
if (head != null) {
head.prev = null;
}
}
}- Delete by Value:
public void deleteByValue(int data) {
if (head == null) return;
Node current = head;
while (current != null && current.data != data) {
current = current.next;
}
if (current == null) return;
if (current.prev != null) {
current.prev.next = current.next;
} else {
head = current.next;
}
if (current.next != null) {
current.next.prev = current.prev;
}
}Step 5: Display the Doubly Linked List
We’ll create methods to traverse and print the list in both forward and reverse order.
- Display Forward:
public void displayForward() {
Node current = head;
while (current != null) {
System.out.print(current.data + " -> ");
current = current.next;
}
System.out.println("null");
}- Display Backward:
public void displayBackward() {
Node current = head;
while (current != null && current.next != null) {
current = current.next;
}
while (current != null) {
System.out.print(current.data + " -> ");
current = current.prev;
}
System.out.println("null");
}Complete Java Program for Doubly Linked List
Here’s the full Java program that includes the Node, DoublyLinkedList, and Main classes:
class Node {
int data;
Node next;
Node prev;
public Node(int data) {
this.data = data;
this.next = null;
this.prev = null;
}
}
class DoublyLinkedList {
Node head;
public DoublyLinkedList() {
this.head = null;
}
public void insertAtBeginning(int data) {
Node newNode = new Node(data);
if (head != null) {
head.prev = newNode;
}
newNode.next = head;
head = newNode;
}
public void insertAtEnd(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
return;
}
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
newNode.prev = current;
}
public void deleteAtBeginning() {
if (head != null) {
head = head.next;
if (head != null) {
head.prev = null;
}
}
}
public void deleteByValue(int data) {
if (head == null) return;
Node current = head;
while (current != null && current.data != data) {
current = current.next;
}
if (current == null) return;
if (current.prev != null) {
current.prev.next = current.next;
} else {
head = current.next;
}
if (current.next != null) {
current.next.prev = current.prev;
}
}
public void displayForward() {
Node current = head;
while (current != null) {
System.out.print(current.data + " -> ");
current = current.next;
}
System.out.println("null");
}
public void displayBackward() {
Node current = head;
while (current != null && current.next != null) {
current = current.next;
}
while (current != null) {
System.out.print(current.data + " -> ");
current = current.prev;
}
System.out.println("null");
}
}
public class Main {
public static void main(String[] args) {
DoublyLinkedList list = new DoublyLinkedList();
list.insertAtBeginning(10);
list.insertAtEnd(20);
list.insertAtEnd(30);
System.out.println("List after insertions:");
list.displayForward();
list.deleteByValue(20);
System.out.println("List after deleting 20:");
list.displayForward();
list.deleteAtBeginning();
System.out.println("List after deleting at the beginning:");
list.displayForward();
System.out.println("List in reverse order:");
list.displayBackward();
}
}Output:
List after insertions:
10 -> 20 -> 30 -> null
List after deleting 20:
10 -> 30 -> null
List after deleting at the beginning:
30 -> null
List in reverse order:
30 -> nullConclusion
A doubly linked list is a powerful structure for scenarios requiring bidirectional traversal or efficient deletion. In this Java implementation, we explored node insertion, deletion, and both forward and reverse traversal. Experiment with the code to enhance your understanding, such as adding a size method or creating a clear function to remove all nodes!