1. Introduction
A Doubly Linked List (DLL) is a type of linked list in which each node contains a data part and two pointers: one pointing to the next node and the other pointing to the previous node. This allows traversal of the list in both directions (forward and backward), unlike a singly linked list where traversal is only possible in one direction.
2. Key Characteristics of Doubly Linked List
- Each node contains:
- Data: Stores the value (can be any type, such as
int,String, or custom objects). - Pointer to the next node: Points to the next node in the list.
- Pointer to the previous node: Points to the previous node in the list.
- Data: Stores the value (can be any type, such as
- Head and Tail: The doubly linked list has two ends:
- Head: The starting node.
- Tail: The last node.
3. Advantages of a Doubly Linked List
- Bidirectional traversal: Can be traversed in both directions.
- Easier insertion/deletion: Deleting or inserting a node (especially in the middle) becomes simpler, as you can access the previous node directly.
- Flexibility: DLL is more flexible compared to singly linked lists due to its two-way navigation.
4. Disadvantages of a Doubly Linked List
- Memory overhead: Extra space for the
prevpointer for each node. - Slightly complex: More pointers to manage, which increases the complexity of insertion, deletion, and other operations.
5. Applications of doubly linked list
- Implementation of LRU (Least Recently Used) Cache: A doubly linked list allows for efficient removal of items from both ends of the list. The LRU item (least recently used) can be removed from the tail, and new or frequently accessed items can be added or moved to the head.
- Undo and Redo Functionality in Applications: Text editors, graphics software, or IDEs often provide undo and redo features, allowing users to revert changes or redo previously undone actions. Each action can be stored in a node in a doubly linked list. The current state of the document is represented by a pointer to the current node. To undo an action, you move the pointer backward (i.e., use the
prevpointer). To redo an action, you move the pointer forward (i.e., use thenextpointer). - Browser’s Forward and Backward Navigation
- Managing Music Playlists: In media players, users often navigate back and forth between songs in a playlist.
- Implementation of Deques (Double-Ended Queues): A deque can be implemented efficiently using a doubly linked list, where elements can be added or removed from both ends (head and tail) in O(1) time.
- Navigation Systems: Locations visited can be stored in a doubly linked list. Moving backward in the navigation history follows the
prevpointer, while moving forward follows thenextpointer.
6. Java Implementation of Doubly Linked List
Node.java
class Node {
int data;
Node prev;
Node next;
// Constructor to create a new node
// Next and prev are initialized as null
Node(int data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
DoublyLinkedList.java
public class DoublyLinkedList {
Node head; // Points to the first node
Node tail; // Points to the last node
// Constructor to initialize an empty list
public DoublyLinkedList() {
head = null;
tail = null;
}
// Method to insert a node at the front of the list
public void insertFront(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
tail = newNode;
} else {
newNode.next = head;
head.prev = newNode;
head = newNode;
}
}
// Method to insert a node at the end of the list
public void insertEnd(int data) {
Node newNode = new Node(data);
if (tail == null) {
head = newNode;
tail = newNode;
} else {
tail.next = newNode;
newNode.prev = tail;
tail = newNode;
}
}
// Method to delete a node from the front of the list
public void deleteFront() {
if (head == null) {
System.out.println("List is empty.");
return;
}
head = head.next;
if (head != null) {
head.prev = null;
} else {
tail = null; // List became empty
}
}
// Method to delete a node from the end of the list
public void deleteEnd() {
if (tail == null) {
System.out.println("List is empty.");
return;
}
tail = tail.prev;
if (tail != null) {
tail.next = null;
} else {
head = null; // List became empty
}
}
// Method to traverse the list from the head
public void traverseForward() {
if (head == null) {
System.out.println("List is empty.");
return;
}
Node current = head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
// Method to traverse the list from the tail
public void traverseBackward() {
if (tail == null) {
System.out.println("List is empty.");
return;
}
Node current = tail;
while (current != null) {
System.out.print(current.data + " ");
current = current.prev;
}
System.out.println();
}
// Method to search for a specific value in the list
public boolean search(int key) {
Node current = head;
while (current != null) {
if (current.data == key) {
return true;
}
current = current.next;
}
return false;
}
}
Test.class
public class Main {
public static void main(String[] args) {
DoublyLinkedList dll = new DoublyLinkedList();
// Insert nodes at the end
dll.insertEnd(10);
dll.insertEnd(20);
dll.insertEnd(30);
System.out.println("List after inserting at end:");
dll.traverseForward(); // Output: 10 20 30
// Insert nodes at the front
dll.insertFront(5);
dll.insertFront(1);
System.out.println("List after inserting at front:");
dll.traverseForward(); // Output: 1 5 10 20 30
// Traverse backward
System.out.println("Traverse backward:");
dll.traverseBackward(); // Output: 30 20 10 5 1
// Delete node from the front
dll.deleteFront();
System.out.println("List after deleting from front:");
dll.traverseForward(); // Output: 5 10 20 30
// Delete node from the end
dll.deleteEnd();
System.out.println("List after deleting from end:");
dll.traverseForward(); // Output: 5 10 20
// Search for an element
System.out.println("Searching for 10: " + dll.search(10)); // Output: true
System.out.println("Searching for 40: " + dll.search(40)); // Output: false
}
}