Introduction
In this tutorial, we are going to discuss Doubly Linked Lists (DLL), how they are structured, their advantages, disadvantages, and why they are often preferred over singly linked lists in certain situations. We will also look into Java’s built-in LinkedList class that uses a doubly linked list internally.
What is a Doubly Linked List?
A Doubly Linked List (DLL) is a linear data structure consisting of nodes, where each node has three components:
- Data – The actual value stored in the node.
- Next Pointer – A reference to the next node in the list.
- Previous Pointer – A reference to the previous node in the list.
This bidirectional nature of a doubly linked list allows traversal in both forward and backward directions, making insertion and deletion operations more efficient in certain scenarios.
Why Do We Need a Doubly Linked List?
In a singly linked list, we maintain a reference to the head node (the first node in the list). However, if we need to insert a new element at the end of the list, we have no other option but to traverse the list from the head until we reach the end. This traversal takes O(n) time complexity.
Additionally, removing or modifying elements towards the end of the list is cumbersome because there is no direct reference to the last element.
This is where Doubly Linked Lists (DLL) come into play.
Structure of a Doubly Linked List
A doubly linked list has the following properties:
- Head Node: This is the first node in the list, and it has a previous pointer set to
null. - Tail Node: This is the last node in the list, and it has a next pointer set to
null. - Bidirectional Pointers: Every intermediate node has two pointers:
- One pointing to the next node.
- One pointing to the previous node.
The bidirectional nature of DLL allows:
- Traversing the list in both directions.
- Faster insertion and deletion at the beginning and end of the list.
Here is an example of a doubly linked list with values:
null<-Head -> [2] <-> [10] <-> [-2] <-> [5] -> Tail->null
- The first node (
Head) has anullprevious pointer. - The last node (
Tail) has anullnext pointer. - Every intermediate node points to both its previous and next nodes.
Java’s Built-in LinkedList Implementation
The java.util.LinkedList is a Doubly-linked list implementation of the List and Deque interfaces. Implements all optional list operations, and permits all elements (including null).
Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.
Note that this implementation is not synchronized. If multiple threads access a linked list concurrently, and at least one of the threads modifies the list structurally, it must be synchronized externally.
If no such object exists, the list should be “wrapped” using the Collections.synchronizedList method. This is best done at creation time, to prevent accidental unsynchronized access to the list:
List list = Collections.synchronizedList(new LinkedList(…));
The iterators returned by this class’s iterator and listIterator methods are fail-fast: if the list is structurally modified at any time after the iterator is created, in any way except through the Iterator’s own remove or add methods, the iterator will throw a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.
Advantages of Doubly Linked Lists
A doubly linked list has several advantages over a singly linked list:
- Efficient Insertion at the End
In a singly linked list, inserting at the end requires traversing the entire list from the head to the tail, which takes O(n) time.
In a doubly linked list, since we have a reference to the tail node, we can insert a new node at the end in O(1) constant time. - Efficient Deletion from the End
Similarly, if we need to delete the last element, we can do it in O(1) constant time as we have a reference to the tail node. - Bidirectional Traversal
We can traverse a doubly linked list in both directions:- Forward traversal: Starting from the head to the tail.
- Backward traversal: Starting from the tail to the head.
- Easy Node Deletion
In a singly linked list, deleting a node in the middle requires a traversal from the head.
In a doubly linked list, since we have a reference to the previous node, we can easily delete a node by:- Adjusting the
nextpointer of the previous node. - Adjusting the
previouspointer of the next node.
- Adjusting the
Disadvantages of Doubly Linked Lists
While doubly linked lists offer many advantages, they also come with a few disadvantages:
- Increased Memory Usage
Every node requires two pointers (next and previous), which means that a doubly linked list consumes more memory than a singly linked list. - Complex Implementation
Implementing a doubly linked list is slightly more complicated because we need to manage two pointers for each node instead of one. - Inefficient Searching
Searching for an arbitrary value still requires traversing the list from either the head or the tail, resulting in O(n) time complexity.
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
}
}