What is a Doubly Linked List?
Learn what a doubly linked list is, how prev/next pointers enable O(1) deletion and bidirectional traversal, with code and interview questions.
Expected Interview Answer
A doubly linked list is a sequence of nodes where each node stores a value plus pointers to both the next and the previous node, allowing traversal in either direction.
Unlike a singly linked list, which only points forward, each doubly linked node carries a "prev" and a "next" reference, so you can walk backward from any node without restarting from the head. This makes deletion of a known node O(1) because you no longer need to track the previous node separately during traversal, and it enables efficient operations like removing the tail. The tradeoff is extra memory for the second pointer per node and more bookkeeping to keep both links consistent on every insert or delete.
- O(1) deletion given a node reference
- Bidirectional traversal
- Efficient tail removal
- Simplifies LRU cache and deque implementations
AI Mentor Explanation
A doubly linked list is like a chain of fielders on the boundary who each know both the fielder to their left and their right. If the umpire pulls one fielder out of position, the remaining two neighbors can instantly reconnect to each other without walking the whole boundary to find who was next to whom. A singly linked list would be fielders who only know the one to their right, so removing someone means someone had to remember who came before.
Step-by-Step Explanation
Step 1
Define the node
Each node stores a value, a next pointer, and a prev pointer.
Step 2
Maintain head and tail
Keep references to both ends so insertion at either side is O(1).
Step 3
Insert with two relinks
Update the new node’s prev/next, then fix the neighbors’ pointers to include it.
Step 4
Delete with two relinks
Point the removed node’s prev.next and next.prev at each other, skipping the node.
What Interviewer Expects
- Clear contrast with singly linked lists
- Correct O(1) deletion claim given a node reference
- Awareness of the extra memory cost per node
- A real use case such as LRU cache or browser history
Common Mistakes
- Forgetting to update both prev and next pointers on insert/delete
- Confusing O(1) deletion-given-a-node with O(1) deletion-by-value
- Not handling head/tail edge cases separately
- Ignoring the extra pointer’s memory overhead
Best Answer (HR Friendly)
“A doubly linked list is a chain of items where each item knows both its neighbor before and after it, so you can move through the list in either direction and remove items quickly without having to search for what came before them.”
Code Example
class Node:
def __init__(self, value):
self.value = value
self.prev = None
self.next = None
def delete_node(node):
if node.prev:
node.prev.next = node.next
if node.next:
node.next.prev = node.prev
node.prev = None
node.next = NoneFollow-up Questions
- How does a doubly linked list power an LRU cache?
- What is the memory overhead versus a singly linked list?
- How would you implement a deque using a doubly linked list?
- When would you prefer an array over a doubly linked list?
MCQ Practice
1. What is the time complexity of deleting a node given a direct reference to it in a doubly linked list?
With prev and next pointers available, relinking neighbors takes constant time.
2. What extra field does a doubly linked list node have compared to a singly linked list node?
Doubly linked nodes add a prev pointer alongside the existing next pointer.
3. Which real-world data structure commonly uses a doubly linked list internally?
LRU caches use a doubly linked list to move and evict entries in O(1).
Flash Cards
Doubly linked list? — Each node has prev and next pointers, enabling bidirectional traversal.
Deletion cost? — O(1) given a direct reference to the node.
Tradeoff vs singly linked? — Extra pointer per node means more memory and bookkeeping.
Common use case? — LRU cache and deque implementations.