A Doubly Linked List is a type of linked list where every node has two links – one pointing to the next node and another pointing to the previous node. This makes it easier to move in both directions.
A Doubly Linked List is an improved version of the Singly Linked List. In this structure, each node stores three things:
- data
- next (pointer to the next node)
- prev (pointer to the previous node)
Because of the extra pointer, you can move both forward and backward inside the list.
Example:
null ← 10 ⇄ 20 ⇄ 30 → nullThis makes some operations faster and easier compared to a singly linked list. In this chapter, we will learn how to implement a doubly linked list from scratch in Java. We will create nodes, connect them forward and backward, insert elements, delete elements, and even print the list in reverse order.
Why Do We Use a Doubly Linked List?
A doubly linked list is useful when:
- You need a two-way traversal
- You want faster deletion, because you can access previous nodes directly
- You need to insert or delete from the middle frequently
- You want to implement navigation, like browser forward/back buttons
- Because of the prev pointer, this structure becomes more flexible.
Where Is Doubly Linked List Used?
- Browser history (Back ↔ Forward)
- Music players (Next ↔ Previous song)
- Undo/Redo systems
- Navigation menus
- LRU Cache (Least Recently Used Cache)
Full Java Code – Doubly Linked List Implementation
// Node class for Doubly Linked List
class Node {
int data;
Node next;
Node prev;
Node(int data) {
this.data = data;
this.next = null;
this.prev = null;
}
}
// Doubly Linked List Implementation
public class DoublyLinkedList {
private Node head;
private int size;
// Insert at the beginning
public void addFirst(int value) {
Node newNode = new Node(value);
newNode.next = head;
if (head != null) {
head.prev = newNode;
}
head = newNode;
size++;
}
// Insert at the end
public void addLast(int value) {
Node newNode = new Node(value);
if (head == null) {
head = newNode;
} else {
Node temp = head;
while (temp.next != null) {
temp = temp.next;
}
temp.next = newNode;
newNode.prev = temp;
}
size++;
}
// Insert at a specific index
public void addAt(int index, int value) {
if (index < 0 || index > size) {
System.out.println("Invalid index");
return;
}
if (index == 0) {
addFirst(value);
return;
}
Node newNode = new Node(value);
Node temp = head;
for (int i = 0; i < index - 1; i++) {
temp = temp.next;
}
newNode.next = temp.next;
newNode.prev = temp;
if (temp.next != null) {
temp.next.prev = newNode;
}
temp.next = newNode;
size++;
}
// Delete first node
public void removeFirst() {
if (head == null) {
System.out.println("List is empty");
return;
}
head = head.next;
if (head != null) {
head.prev = null;
}
size--;
}
// Delete last node
public void removeLast() {
if (head == null) {
System.out.println("List is empty");
return;
}
if (head.next == null) {
head = null;
} else {
Node temp = head;
while (temp.next != null) {
temp = temp.next;
}
temp.prev.next = null;
}
size--;
}
// Delete at a specific index
public void removeAt(int index) {
if (index < 0 || index >= size) {
System.out.println("Invalid index");
return;
}
if (index == 0) {
removeFirst();
return;
}
Node temp = head;
for (int i = 0; i < index; i++) {
temp = temp.next;
}
temp.prev.next = temp.next;
if (temp.next != null) {
temp.next.prev = temp.prev;
}
size--;
}
// Search
public int search(int value) {
Node temp = head;
int index = 0;
while (temp != null) {
if (temp.data == value) {
return index;
}
temp = temp.next;
index++;
}
return -1;
}
// Print forward
public void printForward() {
Node temp = head;
while (temp != null) {
System.out.print(temp.data + " ⇄ ");
temp = temp.next;
}
System.out.println("null");
}
// Print backward
public void printBackward() {
if (head == null) {
System.out.println("List is empty");
return;
}
Node temp = head;
// Move to last node
while (temp.next != null) {
temp = temp.next;
}
// Print backward
while (temp != null) {
System.out.print(temp.data + " ⇄ ");
temp = temp.prev;
}
System.out.println("null");
}
// Main method to test
public static void main(String[] args) {
DoublyLinkedList dll = new DoublyLinkedList();
dll.addLast(10);
dll.addLast(20);
dll.addFirst(5);
dll.addAt(2, 15);
System.out.print("Forward: ");
dll.printForward(); // 5 ⇄ 10 ⇄ 15 ⇄ 20 ⇄ null
System.out.print("Backward: ");
dll.printBackward(); // 20 ⇄ 15 ⇄ 10 ⇄ 5 ⇄ null
dll.removeFirst();
dll.removeLast();
dll.removeAt(1);
System.out.print("After deletions: ");
dll.printForward(); // 10 ⇄ null
int pos = dll.search(10);
System.out.println("10 found at index: " + pos);
}
}
In the above Java code for a double-linked list, we cover the following operations: Insertion, Deletion, Search, and printing the List.