Doubly Linked Lists Navigating Data Both Ways
If you’ve been working with data structures, you’re likely familiar with the concept of a singly linked list. Nodes pointing to the next node in sequence. Simple, elegant, but sometimes limiting. What if you need to go backwards? Enter the Doubly Linked List.
This post will peel back the layers of the doubly linked list, demonstrating its internal workings with clear, runnable Python examples.
What is a Doubly Linked List?
At its core, a doubly linked list is a linear data structure where each element, called a node, not only points to the next node in the sequence but also to the previous node. This bidirectional linkage is its defining characteristic and its greatest strength.
Imagine a chain where each link knows not just the link in front of it, but also the one behind. This allows you to traverse the chain in both directions.
The Anatomy of a Node
In a singly linked list, a node typically has two components: data and next. For a doubly linked list, we add a third: prev.
data: The actual value or information stored in the node.next: A pointer (or reference) to the subsequent node in the list.prev: A pointer (or reference) to the preceding node in the list.
The list itself typically maintains references to its head (the first node) and often its tail (the last node) to facilitate efficient operations at both ends.
Why Doubly? Advantages Explored
The added prev pointer isn’t just an arbitrary design choice; it unlocks significant benefits:
- Bidirectional Traversal: This is the most obvious advantage. You can start from the
headand movenext, or start from thetailand moveprev. This is incredibly useful for features like “undo/redo” or browser “back/forward” navigation. - Efficient Deletion: In a singly linked list, to delete a specific node, you often need a reference to its predecessor to adjust the
nextpointer. This usually means traversing the list from theheaduntil you find the node before the one you want to delete. In a doubly linked list, if you have a pointer to the node you want to delete, you can directly access both itsnextandprevnodes to relink them, making deletion anO(1)operation (once the node is found). - Easier Insertion Before a Node: Similar to deletion, inserting a new node before an existing node is straightforward because you can directly access the
prevnode of the target.
The Downsides: Disadvantages
No data structure is a silver bullet. Doubly linked lists come with their own trade-offs:
- Increased Memory Overhead: Each node requires an extra pointer (
prev), meaning more memory consumption per node compared to a singly linked list. For applications with tight memory constraints or an enormous number of nodes, this can be a factor. - More Complex Operations: Every insertion and deletion operation requires updating two pointers (
nextandprev) instead of just one. While not inherently difficult, it introduces more potential for off-by-one errors or forgotten pointer updates if you’re not careful.
Core Operations - Implementation with Python
Let’s get our hands dirty with some Python code. We’ll start by defining our Node and DoublyLinkedList classes, then walk through common operations.
The Node Class
First, our building block: the Node.
class Node:
def __init__(self, data):
self.data = data
self.next = None # Pointer to next node
self.prev = None # Pointer to previous nodeThe DoublyLinkedList Class
Now, the main class to manage our list of nodes. We’ll keep track of head and tail, and also length for convenience.
class DoublyLinkedList:
def __init__(self):
self.head = None
self.tail = None # Useful for efficient append and backward traversal
self.length = 0
def is_empty(self):
return self.head is None
def __len__(self):
return self.length
def traverse_forward(self):
"""Traverses the list from head to tail and prints elements."""
if self.is_empty():
print("List is empty.")
return
current = self.head
elements = []
while current:
elements.append(str(current.data))
current = current.next
print("Forward traversal:", " <-> ".join(elements))
def traverse_backward(self):
"""Traverses the list from tail to head and prints elements."""
if self.is_empty():
print("List is empty.")
return
current = self.tail
elements = []
while current:
elements.append(str(current.data))
current = current.prev
print("Backward traversal:", " <-> ".join(elements))Let’s test our basic traversal methods with an empty list.
my_list = DoublyLinkedList()
my_list.traverse_forward()
my_list.traverse_backward()
print(f"List length: {len(my_list)}")List is empty.
List is empty.
List length: 0Adding Elements: append (to the end)
Adding to the end is efficient because we have a tail pointer.
class DoublyLinkedList:
# ... (previous code for Node, __init__, is_empty, __len__, traverse_forward, traverse_backward)
def append(self, data):
"""Adds a new node with the given data to the end of the list."""
new_node = Node(data)
if self.is_empty():
self.head = new_node
self.tail = new_node
else:
self.tail.next = new_node
new_node.prev = self.tail
self.tail = new_node
self.length += 1
print(f"Appended: {data}")
# Example Usage:
print("--- Appending Elements ---")
dll = DoublyLinkedList()
dll.append(10)
dll.append(20)
dll.append(30)
dll.traverse_forward()
dll.traverse_backward()
print(f"List length: {len(dll)}")
dll_single = DoublyLinkedList()
dll_single.append(100)
dll_single.traverse_forward()
dll_single.traverse_backward()
print(f"List length: {len(dll_single)}")--- Appending Elements ---
Appended: 10
Appended: 20
Appended: 30
Forward traversal: 10 <-> 20 <-> 30
Backward traversal: 30 <-> 20 <-> 10
List length: 3
Appended: 100
Forward traversal: 100
Backward traversal: 100
List length: 1Adding Elements: prepend (to the beginning)
Adding to the beginning is also efficient as we have a head pointer.
class DoublyLinkedList:
# ... (previous code)
def prepend(self, data):
"""Adds a new node with the given data to the beginning of the list."""
new_node = Node(data)
if self.is_empty():
self.head = new_node
self.tail = new_node
else:
new_node.next = self.head
self.head.prev = new_node
self.head = new_node
self.length += 1
print(f"Prepended: {data}")
# Example Usage:
print("\n--- Prepending Elements ---")
dll_prepend = DoublyLinkedList()
dll_prepend.prepend(3)
dll_prepend.prepend(2)
dll_prepend.prepend(1)
dll_prepend.traverse_forward()
dll_prepend.traverse_backward()
print(f"List length: {len(dll_prepend)}")
dll_mixed = DoublyLinkedList()
dll_mixed.append(5)
dll_mixed.prepend(1)
dll_mixed.append(10)
dll_mixed.prepend(0)
dll_mixed.traverse_forward()
dll_mixed.traverse_backward()
print(f"List length: {len(dll_mixed)}")--- Prepending Elements ---
Prepended: 3
Prepended: 2
Prepended: 1
Forward traversal: 1 <-> 2 <-> 3
Backward traversal: 3 <-> 2 <-> 1
List length: 3
Appended: 5
Prepended: 1
Appended: 10
Prepended: 0
Forward traversal: 0 <-> 1 <-> 5 <-> 10
Backward traversal: 10 <-> 5 <-> 1 <-> 0
List length: 4Insertion: insert_after
Inserting after a specific node requires first finding that node.
class DoublyLinkedList:
# ... (previous code)
def insert_after(self, target_data, new_data):
"""Inserts a new node with new_data after the node containing target_data."""
if self.is_empty():
print("List is empty. Cannot insert after.")
return
current = self.head
while current:
if current.data == target_data:
new_node = Node(new_data)
new_node.next = current.next
new_node.prev = current
if current.next: # If not inserting after the tail
current.next.prev = new_node
else: # Inserting after the current tail
self.tail = new_node
current.next = new_node
self.length += 1
print(f"Inserted {new_data} after {target_data}")
return
current = current.next
print(f"Target data {target_data} not found. Cannot insert after.")
# Example Usage:
print("\n--- Inserting After ---")
dll_insert_after = DoublyLinkedList()
dll_insert_after.append(1)
dll_insert_after.append(3)
dll_insert_after.append(5)
dll_insert_after.traverse_forward() # 1 <-> 3 <-> 5
dll_insert_after.insert_after(3, 4) # Insert in middle
dll_insert_after.traverse_forward() # 1 <-> 3 <-> 4 <-> 5
dll_insert_after.insert_after(5, 6) # Insert after tail
dll_insert_after.traverse_forward() # 1 <-> 3 <-> 4 <-> 5 <-> 6
dll_insert_after.insert_after(1, 2) # Insert after head
dll_insert_after.traverse_forward() # 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> 6
dll_insert_after.insert_after(99, 100) # Target not found
dll_insert_after.traverse_forward() # No change
print(f"List length: {len(dll_insert_after)}")--- Inserting After ---
Appended: 1
Appended: 3
Appended: 5
Forward traversal: 1 <-> 3 <-> 5
Inserted 4 after 3
Forward traversal: 1 <-> 3 <-> 4 <-> 5
Inserted 6 after 5
Forward traversal: 1 <-> 3 <-> 4 <-> 5 <-> 6
Inserted 2 after 1
Forward traversal: 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> 6
Target data 99 not found. Cannot insert after.
Forward traversal: 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> 6
List length: 6Insertion: insert_before
Inserting before a specific node also requires finding that node first.
class DoublyLinkedList:
# ... (previous code)
def insert_before(self, target_data, new_data):
"""Inserts a new node with new_data before the node containing target_data."""
if self.is_empty():
print("List is empty. Cannot insert before.")
return
current = self.head
while current:
if current.data == target_data:
if current.prev is None: # Inserting before the head
self.prepend(new_data)
else: # Inserting in the middle
new_node = Node(new_data)
new_node.next = current
new_node.prev = current.prev
current.prev.next = new_node
current.prev = new_node
self.length += 1 # Prepend already increments length
print(f"Inserted {new_data} before {target_data}")
return
current = current.next
print(f"Target data {target_data} not found. Cannot insert before.")
# Example Usage:
print("\n--- Inserting Before ---")
dll_insert_before = DoublyLinkedList()
dll_insert_before.append(20)
dll_insert_before.append(40)
dll_insert_before.append(60)
dll_insert_before.traverse_forward() # 20 <-> 40 <-> 60
dll_insert_before.insert_before(40, 30) # Insert in middle
dll_insert_before.traverse_forward() # 20 <-> 30 <-> 40 <-> 60
dll_insert_before.insert_before(20, 10) # Insert before head
dll_insert_before.traverse_forward() # 10 <-> 20 <-> 30 <-> 40 <-> 60
dll_insert_before.insert_before(60, 50) # Insert before tail
dll_insert_before.traverse_forward() # 10 <-> 20 <-> 30 <-> 40 <-> 50 <-> 60
dll_insert_before.insert_before(99, 5) # Target not found
dll_insert_before.traverse_forward() # No change
print(f"List length: {len(dll_insert_before)}")--- Inserting Before ---
Appended: 20
Appended: 40
Appended: 60
Forward traversal: 20 <-> 40 <-> 60
Inserted 30 before 40
Forward traversal: 20 <-> 30 <-> 40 <-> 60
Prepended: 10
Forward traversal: 10 <-> 20 <-> 30 <-> 40 <-> 60
Inserted 50 before 60
Forward traversal: 10 <-> 20 <-> 30 <-> 40 <-> 50 <-> 60
Target data 99 not found. Cannot insert before.
Forward traversal: 10 <-> 20 <-> 30 <-> 40 <-> 50 <-> 60
List length: 6Deletion: delete
Deletion is where the prev pointer really shines. We don’t need to find the predecessor; we can directly modify the prev and next pointers of the surrounding nodes.
class DoublyLinkedList:
# ... (previous code)
def delete(self, data):
"""Deletes the first occurrence of a node with the given data."""
if self.is_empty():
print("List is empty. Cannot delete.")
return
current = self.head
while current:
if current.data == data:
if current.prev: # Not the head node
current.prev.next = current.next
else: # Is the head node
self.head = current.next
if current.next: # Not the tail node
current.next.prev = current.prev
else: # Is the tail node
self.tail = current.prev # New tail might be None if list becomes empty
if self.head is None: # If the last node was deleted
self.tail = None
self.length -= 1
print(f"Deleted: {data}")
return
current = current.next
print(f"Data {data} not found. Cannot delete.")
# Example Usage:
print("\n--- Deleting Elements ---")
dll_delete = DoublyLinkedList()
dll_delete.append(1)
dll_delete.append(2)
dll_delete.append(3)
dll_delete.append(4)
dll_delete.append(5)
dll_delete.traverse_forward() # 1 <-> 2 <-> 3 <-> 4 <-> 5
dll_delete.delete(3) # Delete middle
dll_delete.traverse_forward() # 1 <-> 2 <-> 4 <-> 5
dll_delete.traverse_backward() # 5 <-> 4 <-> 2 <-> 1
dll_delete.delete(1) # Delete head
dll_delete.traverse_forward() # 2 <-> 4 <-> 5
dll_delete.traverse_backward() # 5 <-> 4 <-> 2
dll_delete.delete(5) # Delete tail
dll_delete.traverse_forward() # 2 <-> 4
dll_delete.traverse_backward() # 4 <-> 2
dll_delete.delete(100) # Data not found
dll_delete.traverse_forward() # No change
dll_delete.delete(2) # Delete remaining element
dll_delete.traverse_forward() # 4
dll_delete.traverse_backward() # 4
dll_delete.delete(4) # Delete last element
dll_delete.traverse_forward() # List is empty.
dll_delete.traverse_backward() # List is empty.
dll_delete.delete(999) # Delete from empty list
print(f"List length: {len(dll_delete)}")--- Deleting Elements ---
Appended: 1
Appended: 2
Appended: 3
Appended: 4
Appended: 5
Forward traversal: 1 <-> 2 <-> 3 <-> 4 <-> 5
Deleted: 3
Forward traversal: 1 <-> 2 <-> 4 <-> 5
Backward traversal: 5 <-> 4 <-> 2 <-> 1
Deleted: 1
Forward traversal: 2 <-> 4 <-> 5
Backward traversal: 5 <-> 4 <-> 2
Deleted: 5
Forward traversal: 2 <-> 4
Backward traversal: 4 <-> 2
Data 100 not found. Cannot delete.
Forward traversal: 2 <-> 4
Deleted: 2
Forward traversal: 4
Backward traversal: 4
Deleted: 4
List is empty.
List is empty.
List is empty. Cannot delete.
List length: 0Note: The delete method has several conditional checks (if current.prev, if current.next, if self.head is None) to correctly handle deletions of the head, tail, or the only node in the list. This is crucial for maintaining correct head and tail pointers.
Searching: find
Searching is similar to a singly linked list; we traverse from the head until we find the data.
class DoublyLinkedList:
# ... (previous code)
def find(self, data):
"""Searches for a node with the given data and returns it, or None if not found."""
if self.is_empty():
print(f"List is empty. {data} not found.")
return None
current = self.head
while current:
if current.data == data:
print(f"Found {data} in the list.")
return current
current = current.next
print(f"Data {data} not found in the list.")
return None
# Example Usage:
print("\n--- Searching Elements ---")
dll_find = DoublyLinkedList()
dll_find.append("apple")
dll_find.append("banana")
dll_find.append("cherry")
dll_find.traverse_forward()
found_node = dll_find.find("banana")
if found_node:
print(f"Node data: {found_node.data}")
not_found_node = dll_find.find("grape")
if not_found_node:
print(f"Node data: {not_found_node.data}") # This won't execute
dll_empty_find = DoublyLinkedList()
dll_empty_find.find("something")--- Searching Elements ---
Appended: apple
Appended: banana
Appended: cherry
Forward traversal: apple <-> banana <-> cherry
Found banana in the list.
Node data: banana
Data grape not found in the list.
List is empty. apple not found.
List is empty. something not found.Practical Use Cases
Doubly linked lists aren’t just theoretical constructs; they underpin many common software features:
- Web Browser History: When you click “Back” or “Forward” in your browser, you’re interacting with a structure very similar to a doubly linked list. Each page visited is a node, allowing efficient navigation in both directions.
- Undo/Redo Functionality: Text editors, graphic design software, and IDEs implement undo/redo operations using a doubly linked list. Each action taken is a node. Undo moves backward, Redo moves forward.
- Music Playlists: Imagine a media player where you can skip to the next song or go back to the previous one. This is a perfect fit for a doubly linked list.
- Least Recently Used (LRU) Cache: In an LRU cache, a doubly linked list is often used in conjunction with a hash map to quickly access elements and efficiently move recently used items to the front (or end) of the list, while evicting the least recently used from the other end.
Conclusion
Doubly linked lists offer a powerful way to organize data when bidirectional traversal and efficient deletions (given a node reference) are critical. While they come with a slight memory cost and increased complexity in pointer management compared to their singly linked counterparts, the benefits often outweigh these drawbacks in scenarios demanding such flexibility.
Understanding their mechanics is a fundamental step in mastering data structures and designing more efficient and user-friendly applications. Choose your tools wisely, and happy coding!
Last updated on