Doubly Linked List Visualization
Insert
Delete
Access
Utils
Doubly Linked List
Navigate forwards and backwards - see both prev and next pointers in action.
Time O(n) · Space O(n)
Implementation
class DllNode:
"""A single node in the doubly linked list."""
def __init__(self, val):
self.val = val
self.next = None
self.prev = None
class DllList:
"""
Doubly Linked List implementation.
Provides operations for adding, removing, searching, and
traversing elements in a bidirectional linked structure.
"""
def __init__(self, val=None):
"""Initialize the list, optionally with a starting value."""
if val is not None:
self.head = DllNode(val)
self.tail = self.head
self.len = 1
else:
self.head = None
self.tail = None
self.len = 0
def __len__(self):
"""Return the number of nodes in the list."""
return self.len
def __str__(self):
"""String representation: head <-> ... <-> tail."""
values = [str(el) for el in self]
return " <-> ".join(values)
def __repr__(self):
return str(self)
def __iter__(self):
"""Iterate over all values in the list."""
cur = self.head
while cur:
yield cur.val
cur = cur.next
def __bool__(self):
"""Return True if the list is not empty."""
return self.len > 0
def get_at(self, position) -> DllNode:
"""
Get the node at the specified position.
Raises IndexError if position is invalid.
"""
if position >= self.len or position < 0:
raise IndexError("Position is invalid.")
node = self.head
for _ in range(position):
node = node.next
return node
def add_left(self, val):
"""Add a new node with the given value at the head. O(1)"""
new_node = DllNode(val)
if not self:
self.head = new_node
self.tail = new_node
else:
new_node.next = self.head
self.head.prev = new_node
self.head = new_node
self.len += 1
def add_right(self, val):
"""Add a new node with the given value at the tail. O(1)"""
new_node = DllNode(val)
if not self:
self.head = new_node
self.tail = new_node
else:
new_node.prev = self.tail
self.tail.next = new_node
self.tail = new_node
self.len += 1
def add_at(self, val, position):
"""
Insert a new node at the specified position.
Raises IndexError if position is out of bounds.
"""
if position > len(self) or position < 0:
raise IndexError("Invalid position to insert a value at.")
if position == 0:
return self.add_left(val)
if position == len(self):
return self.add_right(val)
before = self.get_at(position - 1)
after = before.next
new_node = DllNode(val)
before.next = new_node
new_node.prev = before
new_node.next = after
after.prev = new_node
self.len += 1
def remove_left(self):
"""
Remove and discard the head node. O(1)
Raises IndexError if list is empty.
"""
if not self:
raise IndexError("List is empty.")
if self.len == 1:
self.head = None
self.tail = None
else:
self.head = self.head.next
self.head.prev = None
self.len -= 1
def remove_right(self):
"""
Remove and discard the tail node. O(1)
Raises IndexError if list is empty.
"""
if not self:
raise IndexError("List is empty.")
if self.len == 1:
self.head = None
self.tail = None
else:
self.tail = self.tail.prev
self.tail.next = None
self.len -= 1
def remove_at(self, position):
"""
Remove the node at the specified position.
Raises IndexError if list is empty or position is invalid.
"""
if not self:
raise IndexError("List is empty.")
if position < 0 or position >= self.len:
raise IndexError("Position is invalid.")
if position == 0:
return self.remove_left()
if position == self.len - 1:
return self.remove_right()
to_remove = self.get_at(position)
before = to_remove.prev
after = to_remove.next
before.next = after
after.prev = before
to_remove.prev = None
to_remove.next = None
self.len -= 1
def traverse(self):
"""Return a list of all values in the list."""
cur = self.head
arr = []
while cur:
arr.append(cur.val)
cur = cur.next
return arr
def search_for(self, val):
"""
Search for a value in the list.
Returns the position if found, -1 otherwise.
"""
cur = self.head
pos = 0
while cur:
if cur.val == val:
return pos
pos += 1
cur = cur.next
return -1
def reverse_list(self):
"""Reverse the linked list in place."""
cur = self.head
self.head, self.tail = self.tail, self.head
while cur:
cur.prev, cur.next = cur.next, cur.prev
cur = cur.prev # Move to next (which is now prev)
# Example usage:
if __name__ == "__main__":
# Create a new list
dll = DllList()
# Add elements at tail
dll.add_right(10)
dll.add_right(20)
dll.add_right(30)
print(dll) # 10 <-> 20 <-> 30
# Add to head
dll.add_left(5)
print(dll) # 5 <-> 10 <-> 20 <-> 30
# Add at position
dll.add_at(15, 2)
print(dll) # 5 <-> 10 <-> 15 <-> 20 <-> 30
# Search for a value
pos = dll.search_for(20)
print(f"Found 20 at position: {pos}") # Found 20 at position: 3
# Get value at position
node = dll.get_at(2)
print(f"Value at position 2: {node.val}") # Value at position 2: 15
# Remove elements
dll.remove_left()
print(dll) # 10 <-> 15 <-> 20 <-> 30
dll.remove_right()
print(dll) # 10 <-> 15 <-> 20
# Reverse the list
dll.reverse_list()
print(dll) # 20 <-> 15 <-> 10
About Doubly Linked List
How Doubly Linked List Works
A doubly linked list extends the singly linked list by adding a pointer to the previous node in each element. This allows traversal in both directions and makes deletion of a known node O(1) since you can access the predecessor directly.
Each node stores a value, a pointer to the next node, and a pointer to the previous node. Insertion and deletion update both pointers. Traversal can proceed from either end of the list.
Complexity
- Time
- O(n)
- Space
- O(n)
When to Use Doubly Linked List
- Browser history navigation (back/forward)
- LRU cache implementation
- Undo/redo systems requiring bidirectional traversal