A
AiTechWorlds
AiTechWorlds
Imagine browsing the web. You visit a news site, then click to a sports page, then to a video. Now you press the Back button. The browser remembers where you came from. Press Forward and it takes you right back to the video. This feels completely natural — but how does it work under the hood?
A singly linked list only knows how to go one direction: forward. Every node points to the next. But browser history needs to travel both ways. That is exactly what a doubly linked list solves. Each node carries a pointer to the next node AND a pointer to the previous node — like a two-lane road instead of a one-way street.
Singly linked lists are efficient, but they have a blind spot: you cannot go backward. If you are standing at node 5 in a singly linked list and need node 4, you have to start from the beginning and traverse all the way there again — O(n) wasted work.
A doubly linked list eliminates that blind spot. You can move in either direction at any point, making operations like deletion more efficient (no need to find the previous node first) and enabling backward traversal naturally.
Each node in a doubly linked list holds three things:
| Field | Purpose |
|---|---|
data | The actual value stored |
next | Pointer to the next node |
prev | Pointer to the previous node |
The head node has prev = None. The tail node has next = None.
None ← [A] ⇄ [B] ⇄ [C] ⇄ [D] → None
class Node:
def __init__(self, data):
self.data = data # The value this node holds
self.next = None # Points to the next node (starts as None)
self.prev = None # Points to the previous node (starts as None)
class DoublyLinkedList:
def __init__(self):
self.head = None # The list starts empty — head points nowhere
# --- Append: add to the END of the list ---
def append(self, data):
new_node = Node(data)
if self.head is None: # List is empty — new node becomes head
self.head = new_node
return
current = self.head
while current.next: # Walk to the last node
current = current.next
current.next = new_node # Last node's next now points to new node
new_node.prev = current # New node's prev points back to old last
# --- Prepend: add to the BEGINNING of the list ---
def prepend(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
return
new_node.next = self.head # New node points forward to old head
self.head.prev = new_node # Old head points back to new node
self.head = new_node # Update head to be the new node
# --- Delete: remove a node by value ---
def delete(self, data):
current = self.head
while current:
if current.data == data:
if current.prev: # If there is a node before
current.prev.next = current.next # Skip over current going forward
else:
self.head = current.next # Deleting the head — update head
if current.next: # If there is a node after
current.next.prev = current.prev # Skip over current going backward
return # Done — node is unlinked
current = current.next
print(f"Value {data} not found.")
# --- Display forward: head to tail ---
def display_forward(self):
elements = []
current = self.head
while current:
elements.append(str(current.data))
current = current.next
print("Forward: " + " ⇄ ".join(elements))
# --- Display backward: tail to head ---
def display_backward(self):
current = self.head
while current and current.next: # Walk to the last node first
current = current.next
elements = []
while current:
elements.append(str(current.data))
current = current.prev # Now walk backwards using prev pointers
print("Backward: " + " ⇄ ".join(elements))
append("A"), append("B"), append("C"):Head
↓
[A | next→] → [B | next→] → [C | next→None]
[A | prev←None] [B | prev←] [C | prev←]
Each node knows its neighbor in both directions.
delete("B"):Before: [A] ⇄ [B] ⇄ [C]
Step 1: A.next = C (skip B going forward)
Step 2: C.prev = A (skip B going backward)
After: [A] ⇄ [C]
No need to traverse from the head to find B's predecessor — B already knows it via prev.
dll = DoublyLinkedList()
dll.append("Page1")
dll.append("Page2")
dll.append("Page3")
dll.prepend("HomePage")
dll.display_forward()
dll.display_backward()
dll.delete("Page2")
dll.display_forward()
Output:
Forward: HomePage ⇄ Page1 ⇄ Page2 ⇄ Page3
Backward: Page3 ⇄ Page2 ⇄ Page1 ⇄ HomePage
Forward: HomePage ⇄ Page1 ⇄ Page3
| Feature | Singly Linked List | Doubly Linked List |
|---|---|---|
| Memory per node | data + 1 pointer | data + 2 pointers |
| Forward traversal | Yes — O(n) | Yes — O(n) |
| Backward traversal | No | Yes — O(n) |
| Delete by reference | O(n) (find prev) | O(1) (prev pointer ready) |
| Insert at head | O(1) | O(1) |
| Insert at tail | O(n) | O(n) without tail pointer |
| Use case | Simple forward-only | Bidirectional navigation |
Key insight: The extra
prevpointer costs a little memory but saves significant time when you need to delete a known node or traverse backwards.
| Operation | Time Complexity |
|---|---|
| Access | O(n) |
| Search | O(n) |
| Insert head | O(1) |
| Insert tail | O(n)* |
| Delete known | O(1) |
*O(1) if a tail pointer is maintained separately.
Browser History — The Back and Forward buttons navigate a doubly linked list of visited URLs. Each page is a node; prev is the back pointer, next is the forward pointer.
Music Player — A playlist where you can skip to the next song or return to the previous one. Each track is a node in a doubly linked list.
LRU Cache (Least Recently Used) — One of the most common interview topics. An LRU cache combines a doubly linked list with a hash map. The list keeps track of access order (most recent at head, least recent at tail). When the cache is full, the tail node is evicted in O(1). The hash map gives O(1) access to any node. Together, all operations are O(1).
Text Editors — The cursor in many editors is implemented with a doubly linked list of characters or lines. Moving left uses prev, moving right uses next.
A doubly linked list is the right tool whenever your data has a natural two-directional flow — going back and forward, previous and next, undo and redo. The cost is one extra pointer per node. The benefit is backward traversal and O(1) deletion of any known node, which makes it a cornerstone of more advanced data structures like LRU caches and deques.
Get this course's notes on Telegram!
Free cheat sheets, summaries & practice exercises