Doubly Linked List
Overview
A Doubly Linked List (DLL) is an evolution of the Singly Linked List. While a singly linked node only knows about the node after it, a doubly linked node maintains two pointers: one pointing to the next node, and one pointing to the previous node.
This addition solves the biggest limitation of a singly linked list: you can now traverse the list backwards just as easily as forwards. More importantly, if you have a reference to a specific node, you can delete it in O(1) time because you immediately have access to its predecessor via the prev pointer. In a singly linked list, even if you know the node to delete, you have to traverse from the head all the way down to find its predecessor (O(N)).
The tradeoff is memory and complexity. Every single node now requires extra memory to store the prev pointer. Additionally, every insertion or deletion operation requires updating four pointers instead of two, increasing the surface area for bugs.
Syntax
public class DoublyLinkedList {
static class Node {
int data;
Node prev;
Node next;
Node(int data) {
this.data = data;
}
}
Node head;
Node tail; // DLLs often track the tail for O(1) appends
// O(1) Append to end
public void append(int data) {
Node newNode = new Node(data);
if (head == null) {
head = tail = newNode;
return;
}
// 4 pointer updates required for appending
tail.next = newNode; // 1. Old tail points forward to new node
newNode.prev = tail; // 2. New node points backward to old tail
tail = newNode; // 3. Update tail reference
// (newNode.next is already null)
}
// O(1) Deletion if you have the node reference
public void deleteNode(Node target) {
if (target == null) return;
if (target.prev != null) {
target.prev.next = target.next; // Bypass target going forward
} else {
head = target.next; // Target was head
}
if (target.next != null) {
target.next.prev = target.prev; // Bypass target going backward
} else {
tail = target.prev; // Target was tail
}
}
}Common Pitfalls
- Forgetting to update
prevpointers. When inserting a node, developers often remember to updatea.next = b, but forget to updateb.prev = a. This creates a broken list where forward traversal works, but backward traversal skips nodes or hits NullPointerExceptions. - Failing to handle the
headandtailedge cases during deletion. If the node being deleted is the head, itsprevis null, sotarget.prev.next = ...will throw an NPE. You must always check if the node is at the boundaries of the list. - Memory bloat in cache-heavy applications. Because Java objects have significant memory overhead (object header + data + 2 references), a Doubly Linked List holding primitive
ints will use 4-5x more memory than a primitiveint[]array.
Interview Questions
The ability to traverse backwards, and the ability to delete a node in O(1) time if you already have a reference to it (since you immediately know its predecessor via the prev pointer).
LinkedList class implement its internal structure?Java's java.util.LinkedList is implemented as a Doubly Linked List. It maintains both a first (head) and last (tail) pointer, making it implement both the List and Deque (Double Ended Queue) interfaces efficiently.
Yes, and it's simpler than a singly linked list. You just traverse the list, and for every node, you swap its prev and next pointers. Finally, you swap the head and tail references of the list itself.
Real-World Example
A web browser's Back and Forward navigation history is a perfect use case for a Doubly Linked List. The current page is a node. Clicking 'Back' moves to node.prev. Clicking 'Forward' moves to node.next. If you visit a new page, you simply overwrite node.next and discard the old forward history.
class BrowserHistory {
class PageNode {
String url;
PageNode prev, next;
PageNode(String url) { this.url = url; }
}
PageNode current;
public void visit(String url) {
PageNode newPage = new PageNode(url);
if (current != null) {
current.next = newPage;
newPage.prev = current;
}
current = newPage; // Move to the new page
}
public String back() {
if (current.prev != null) current = current.prev;
return current.url;
}
public String forward() {
if (current.next != null) current = current.next;
return current.url;
}
}Check Your Knowledge
Test your understanding of Doubly Linked List with these quick questions.