Doubly Linked List
Overview
A Doubly Linked List is an upgrade to the Singly Linked List. In addition to the `next` pointer, every Node also maintains a `prev` pointer that points back to the previous Node. This simple addition allows you to traverse the list in both directions (forwards and backwards). It makes deleting a given node exactly O(1) time (because you immediately know its predecessor), whereas a singly linked list requires an O(N) search to find the predecessor.
Syntax
Maintaining the `prev` pointer takes slightly more memory per node, but unlocks reverse traversal and incredibly fast deletions.
class DNode {
int data;
DNode next;
DNode prev; // The powerful new pointer
public DNode(int data) {
this.data = data;
}
}
public class DoublyLinkedList {
DNode head;
DNode tail; // Often track the end for O(1) appending
}Notice we don't need a while loop! We can instantly stitch the predecessor and successor together, bypassing the deleted node.
// Assuming we already have a direct reference to 'nodeToDelete'
public void deleteNode(DNode nodeToDelete) {
if (nodeToDelete == null) return;
// Update the next pointer of the PREVIOUS node
if (nodeToDelete.prev != null) {
nodeToDelete.prev.next = nodeToDelete.next;
} else {
head = nodeToDelete.next; // We are deleting the head
}
// Update the prev pointer of the NEXT node
if (nodeToDelete.next != null) {
nodeToDelete.next.prev = nodeToDelete.prev;
}
}Common Pitfalls
- Forgetting to update the `prev` pointer when inserting a new node, breaking reverse traversal.
- Mishandling edge cases: trying to delete the very first or very last node and throwing NullPointerExceptions.
Interview Tips
- The addition of a 'prev' pointer allows O(1) deletion of a node if you have the reference, because you instantly know the predecessor.
Real-World Example
Doubly Linked Lists are the backbone of Browser History (Back/Forward buttons) and LRU Caches (Redis).
public class BrowserHistory {
DNode currentUrl;
public void visit(String url) {
DNode newPage = new DNode(url);
currentUrl.next = newPage;
newPage.prev = currentUrl;
currentUrl = newPage;
}
public void goBack() {
if (currentUrl.prev != null) {
currentUrl = currentUrl.prev;
System.out.println("Navigated back to " + currentUrl.url);
}
}
}