Skip to main content
The DoublyLinkedList class provides a doubly linked list implementation where each node has references to both the next and previous nodes. It inherits from LinkedList.

​
Node

A doubly linked list node implementation.

​
Constructor

​
value
any
required
The value of the node
from dsa.doublylinkedlist import Node

node = Node(10)
print(node.value)  # Output: 10
print(node.next)   # Output: None
print(node.prev)   # Output: None

​
Properties

​
value
any
The value stored in the node
​
next
Node | None
Reference to the next node in the list
​
prev
Node | None
Reference to the previous node in the list

​
DoublyLinkedList

A doubly linked list implementation that inherits several methods from LinkedList, except for methods that modify the contents of the list.

​
Constructor

​
head
Node | None
default:"None"
Reference to the head node
​
tail
Node | None
default:"None"
Reference to the tail node
​
count
int
default:"0"
The number of nodes in the linked list
If only the head node is specified, tail is set to the head node and count is automatically set to 1. If both head and tail nodes are specified, count should be specified as well.
from dsa.doublylinkedlist import DoublyLinkedList, Node

# Create an empty doubly linked list
dll = DoublyLinkedList()

# Create with a single node
node = Node(10)
dll = DoublyLinkedList(head=node)

​
Properties

​
head
Node | None
Reference to the first node in the list
​
tail
Node | None
Reference to the last node in the list
​
count
int
The number of nodes in the linked list

​
Methods

​
from_list(mylist)

Class method to create a doubly linked list from a list.
​
mylist
list
required
A list or container to convert from
Returns: Doubly linked list with the contents of the list 
dll = DoublyLinkedList.from_list([1, 2, 3, 4, 5])
print(dll.to_list())  # Output: [1, 2, 3, 4, 5]

​
to_list()

Convert the doubly linked list to a Python list. Returns: A list with contents of the doubly linked list 
dll = DoublyLinkedList.from_list([1, 2, 3])
print(dll.to_list())  # Output: [1, 2, 3]

​
traverse()

Print the contents of the doubly linked list (forward direction). 
dll = DoublyLinkedList.from_list([1, 2, 3, 4, 5])
dll.traverse()  # Output: 1 2 3 4 5

​
traverse_reverse()

Print the contents of the doubly linked list in reverse order. 
dll = DoublyLinkedList.from_list([1, 2, 3, 4, 5])
dll.traverse_reverse()  # Output: 5 4 3 2 1

​
search(value)

Search for a value in the doubly linked list.
​
value
any
required
The value to search for
Returns: The Node containing the value, or None if not found 
dll = DoublyLinkedList.from_list([10, 20, 30])
node = dll.search(20)
if node:
    print(f"Found: {node.value}")  # Output: Found: 20
    print(f"Previous: {node.prev.value}")  # Output: Previous: 10
    print(f"Next: {node.next.value}")      # Output: Next: 30

​
is_empty()

Check if the doubly linked list is empty. Returns: True if the list is empty, False otherwise 
dll = DoublyLinkedList()
print(dll.is_empty())  # Output: True
dll.append(1)
print(dll.is_empty())  # Output: False

​
prepend(value)

Place a value at the beginning of the doubly linked list.
​
value
any
required
The value to prepend
dll = DoublyLinkedList.from_list([2, 3, 4])
dll.prepend(1)
print(dll.to_list())  # Output: [1, 2, 3, 4]

​
append(value)

Place a value at the end of the doubly linked list.
​
value
any
required
The value to append
dll = DoublyLinkedList.from_list([1, 2, 3])
dll.append(4)
print(dll.to_list())  # Output: [1, 2, 3, 4]

​
insert_after(after_value, value)

Insert a value after a specified value.
​
after_value
any
required
The value to insert after
​
value
any
required
The value to insert
Returns: None Raises:
  • ValueError: If the after_value is not found
dll = DoublyLinkedList.from_list([1, 2, 4])
dll.insert_after(2, 3)
print(dll.to_list())  # Output: [1, 2, 3, 4]

# Verify bidirectional links
node = dll.search(3)
print(node.prev.value)  # Output: 2
print(node.next.value)  # Output: 4

​
delete(value)

Delete the first occurrence of a value in the doubly linked list.
​
value
any
required
The value to be deleted
Raises:
  • ValueError: If the value is not found
dll = DoublyLinkedList.from_list([1, 2, 3, 2, 4])
dll.delete(2)  # Deletes first occurrence
print(dll.to_list())  # Output: [1, 3, 2, 4]

​
delete_head()

Delete the head node of the doubly linked list. Raises:
  • IndexError: If linked list is empty
dll = DoublyLinkedList.from_list([1, 2, 3])
dll.delete_head()
print(dll.to_list())  # Output: [2, 3]

​
delete_tail()

Delete the tail node of the doubly linked list. Raises:
  • IndexError: If linked list is empty
dll = DoublyLinkedList.from_list([1, 2, 3])
dll.delete_tail()
print(dll.to_list())  # Output: [1, 2]

​
Special Methods

​
__getitem__(index)

Return value at a specified index (inherited from LinkedList).
​
index
int
required
Index of the value
Returns: The value at the specified index Raises:
  • IndexError: If index is out of bounds
dll = DoublyLinkedList.from_list([10, 20, 30, 40])
print(dll[0])  # Output: 10
print(dll[2])  # Output: 30

​
__len__()

Return the number of elements in the doubly linked list (inherited from LinkedList). 
dll = DoublyLinkedList.from_list([1, 2, 3, 4, 5])
print(len(dll))  # Output: 5

​
__eq__(other)

Compare this doubly linked list to another for equality.
​
other
any
required
The object to compare with
Returns: True if both are DoublyLinkedList instances with equal contents 
dll1 = DoublyLinkedList.from_list([1, 2, 3])
dll2 = DoublyLinkedList.from_list([1, 2, 3])
dll3 = DoublyLinkedList.from_list([1, 2, 4])

print(dll1 == dll2)  # Output: True
print(dll1 == dll3)  # Output: False

​
__repr__()

Return a string representation of the doubly linked list (inherited from LinkedList). 
dll = DoublyLinkedList.from_list([1, 2, 3])
print(dll)  # Output: [ 1 2 3 ] Count: 3

​
Complete Example

from dsa.doublylinkedlist import DoublyLinkedList

# Create a doubly linked list from a list
dll = DoublyLinkedList.from_list([10, 20, 30, 40, 50])

# Display the list
print(f"Initial list: {dll.to_list()}")
print(f"Length: {len(dll)}")

# Traverse forward and backward
print("Forward: ", end="")
dll.traverse()  # Output: 10 20 30 40 50

print("Backward: ", end="")
dll.traverse_reverse()  # Output: 50 40 30 20 10

# Access elements by index
print(f"First element: {dll[0]}")
print(f"Third element: {dll[2]}")

# Add elements
dll.prepend(5)
dll.append(60)
dll.insert_after(30, 35)
print(f"After additions: {dll.to_list()}")
# Output: [5, 10, 20, 30, 35, 40, 50, 60]

# Verify bidirectional links
node = dll.search(35)
if node:
    print(f"Node value: {node.value}")
    print(f"Previous node: {node.prev.value}")  # Output: 30
    print(f"Next node: {node.next.value}")      # Output: 40

# Delete elements
dll.delete(35)
dll.delete_head()
dll.delete_tail()
print(f"After deletions: {dll.to_list()}")
# Output: [10, 20, 30, 40, 50]

# Compare lists
dll2 = DoublyLinkedList.from_list([10, 20, 30, 40, 50])
print(f"Lists equal: {dll == dll2}")  # Output: True

# Check if empty
print(f"Is empty: {dll.is_empty()}")  # Output: False

# Clear the list
while not dll.is_empty():
    dll.delete_head()

print(f"After clearing, is empty: {dll.is_empty()}")  # Output: True

​
Advantages Over Singly Linked List

DoublyLinkedList provides bidirectional traversal and more efficient deletion operations:
  • Can traverse backward using traverse_reverse()
  • Deleting a node is O(1) when you have a reference to it
  • Each node maintains links to both neighbors
  • Better for implementing deques and LRU caches

​
Use Cases

class LRUCache:
    def __init__(self, capacity):
        from dsa.doublylinkedlist import DoublyLinkedList
        self.cache = {}
        self.order = DoublyLinkedList()
        self.capacity = capacity
    
    def access(self, key):
        # Move accessed item to front
        if key in self.cache:
            # In real implementation, would update order
            return self.cache[key]
        return None

cache = LRUCache(3)

Build docs developers (and LLMs) love

Get started for freeTalk to us