Quick answer: A doubly linked list stores each value in a node with previous and next references. With a pointer to the relevant node, insertion and deletion can be constant-time operations, but traversal is linear and each node costs more memory than an item in a Python list.
A doubly linked list is a chain of nodes where each node stores data, a link to the next node, and a link to the previous node. That extra previous link makes it possible to move forward and backward through the list.
The official Python documentation covers classes and dataclasses.
Python’s built-in list is usually the better default for application code. A linked list is useful as a learning data structure and in specific cases where frequent node insertion and removal are more important than direct indexing.
The core idea is simple: every operation must keep both directions consistent. If a node’s next pointer changes, the neighboring node’s prev pointer may need to change too.
That consistency is the main source of mistakes. A list can look correct when traversed forward but fail when traversed backward if one prev link was not updated.
For a small teaching implementation, clarity matters more than squeezing every operation into the fewest lines. Write the empty-list, head, tail, and middle-node cases so they are easy to inspect.
Create A Node Class
A node can be represented with a small dataclass. The previous and next links start as None.
from dataclasses import dataclass
@dataclass
class Node:
data: int
prev: "Node | None" = None
next: "Node | None" = None
node = Node(10)
print(node.data)
print(node.prev)
print(node.next)
The type hints use quotes because the class refers to itself while it is still being defined. This keeps the code readable and editor-friendly.
Each node stores one value. The list object will keep track of the first node, often called the head, and optionally the last node, often called the tail.
A tail reference is not strictly required, but it makes appending and reverse traversal much easier. Without it, the code must walk to the end before adding or reading the last node.
Append To The End
Appending adds a new node after the current tail.
class Node:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
class DoublyLinkedList:
def __init__(self):
self.head = None
self.tail = None
def append(self, data):
node = Node(data)
if self.tail is None:
self.head = self.tail = node
return
node.prev = self.tail
self.tail.next = node
self.tail = node
items = DoublyLinkedList()
items.append("A")
items.append("B")
print(items.head.data, items.tail.data)
The first append sets both head and tail. Later appends connect the new node to the old tail and then move the tail reference.
Keeping a tail reference makes append efficient because the code does not need to walk from the head every time.
The important invariant is that tail.next should be None after the append. If a new tail still points somewhere else, traversal can produce incorrect results.
Traverse Forward
Forward traversal starts at the head and follows next links.
class Node:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
a, b, c = Node("A"), Node("B"), Node("C")
a.next = b
b.prev = a
b.next = c
c.prev = b
current = a
values = []
while current:
values.append(current.data)
current = current.next
print(values)
This is how you read the list from first to last. The loop stops when the next reference becomes None.
Unlike a Python list, a linked list does not support fast direct indexing. To reach an item, you follow links one node at a time.
This is why linked lists are not a drop-in replacement for built-in lists. They trade fast indexing for pointer-based insertion and deletion patterns.
Traverse Backward
Backward traversal starts at the tail and follows prev links.
class Node:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
a, b, c = Node(1), Node(2), Node(3)
a.next = b
b.prev = a
b.next = c
c.prev = b
current = c
values = []
while current:
values.append(current.data)
current = current.prev
print(values)
This is the main advantage over a singly linked list. Each node knows the node before it, so reverse traversal does not need to restart from the head.
Backward traversal is useful for undo stacks, browser-style history, ordered navigation, and data-structure practice.
It is also a useful debugging check. If forward traversal and backward traversal disagree, one of the links was not maintained correctly.
Prepend To The Front
Prepending adds a new node before the current head.
class Node:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
head = Node("B")
new_head = Node("A")
new_head.next = head
head.prev = new_head
head = new_head
print(head.data)
print(head.next.data)
print(head.next.prev.data)
The new node becomes the head. Its next points to the old head, and the old head’s prev points back to the new node.
When implementing this inside a full list class, remember to update the tail too if the list was empty before the prepend.
The empty-list case is special because the new node is both the head and the tail. Handling that case first keeps the rest of the method simple.
Delete A Node
Deleting a node means linking its neighbors to each other.
class Node:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
a, b, c = Node("A"), Node("B"), Node("C")
a.next = b
b.prev = a
b.next = c
c.prev = b
a.next = c
c.prev = a
print(a.next.data)
print(c.prev.data)
This removes b from the chain. A complete method also needs to handle deleting the head, deleting the tail, and deleting the only node.
After deletion, it is often helpful to clear the removed node’s prev and next references if the node might be reused or inspected. The remaining list should not depend on that node anymore.
The practical rule is simple: every insert or delete should update both next and prev links. Test empty lists, one-node lists, head changes, tail changes, and middle-node deletion.
For most everyday Python code, use the built-in list or collections.deque. Use a doubly linked list when you are studying data structures or when node-level insertion and bidirectional traversal are central to the problem.
Define The Node Invariant
Every node’s next pointer should lead forward and its previous pointer should lead back. The list should also maintain head and tail references and keep them consistent when nodes are added or removed.
Insert At A Known Position
To insert between left and right, set the new node’s previous and next pointers, then repair left.next and right.prev. Update head or tail when one neighbor is missing.
Delete Without Losing The Chain
Save the target’s neighbors, link them to each other, and clear the removed node’s pointers if it should not remain connected. Handle a one-node list and deleting either endpoint explicitly.
Choose Traversal Direction
If the target index is closer to the tail, walk backward through prev pointers; otherwise walk forward. This improves traversal constants but does not provide random access like a Python list.
Compare Python’s Built-ins
A list is compact and offers fast indexing. collections.deque is often a better production choice for efficient operations at both ends. Implement a linked list mainly when its structure is the subject or requirement.
Test Structural Invariants
After every operation, test forward and backward traversal, head and tail, length, empty transitions, duplicate values, and deletion of an unknown node or index.
The official deque documentation provides a production alternative for double-ended queues. Related Python Pool references include lists and tests.
For related data structures, compare built-in lists, invariant tests, and traversal patterns before choosing linked nodes.
Frequently Asked Questions
What is a doubly linked list?
It is a sequence of nodes where each node stores a value plus references to both the previous and next nodes.
What is the advantage over a singly linked list?
A doubly linked list supports backward traversal and can unlink a known node without first finding its predecessor.
What happens when deleting the head or tail?
Update the list’s head or tail and repair the remaining neighbor pointer, including the special case where the list becomes empty.
Is a Python list usually better?
Often yes for indexed access and compact storage; a linked list is useful when its pointer-based operations match the workload and memory overhead is acceptable.