Linked list in Python: build one, then choose the right container
Implement a minimal singly linked list in Python, check its operation costs, and learn when list or collections.deque is the better tool.
A Python linked list uses node objects that point to the next node. Prepending to a known head is O(1), but finding a value or index is O(n). Python's built-in list is a dynamic array, and collections.deque is usually the practical choice for efficient operations at both ends.
Each box holds a value and a note pointing to the next box. Adding a new first box is easy: point it at the old first box. Reaching the tenth box still means following nine notes.
The word list in Python names an array-backed sequence, not a linked list. A linked list can be built from small node objects, and doing so is a useful way to understand pointer-based structures. It is rarely the right default container for application code. The general linked-list guide explains the memory-layout trade-off; this page shows what the implementation and choices look like in Python.
Write a minimal list#
from dataclasses import dataclass
@dataclass
class Node:
value: int
next: "Node | None" = None
class LinkedList:
def __init__(self) -> None:
self.head: Node | None = None
def prepend(self, value: int) -> None:
self.head = Node(value, self.head)
def find(self, value: int) -> Node | None:
current = self.head
while current is not None:
if current.value == value:
return current
current = current.next
return Noneprepend constructs one node and changes one head reference, regardless of list length. find may follow every next reference before it can answer. The code intentionally does not add an index operation: an index would still require a walk from the head.
The cost is finding the node#
If you already hold a node and its predecessor, splicing a new node between them is O(1). If a caller asks to insert “at position 500,” the structure must first walk to that position, so the whole operation is O(n). Python object allocation and pointer chasing also have real overhead. Big-O counts operations, not the cache locality that makes an array fast in practice.
A tail pointer can make appending O(1), but it adds an invariant: an empty list, removal of the tail, and every mutation must keep head and tail consistent. A toy implementation that forgets this detail is a common source of broken examples.
Choose a Python container#
Use built-in list for frequent indexed reads and ordinary append-heavy sequences. Use collections.deque for a queue or for append/pop at both ends; the site’s deque walkthrough shows the left-end cost that a list pays. Build a custom linked list when node identity and splicing are the actual requirements, or when learning the data structure. Choosing it merely because O(1) insertion sounds fast ignores the lookup that usually comes first.
Questions people also ask
2 QUESTIONSIs Python's built-in list a linked list?
No. It is an array-backed sequence with efficient indexing and append but potentially expensive insertions or removals near the front.
When should I use collections.deque?
Use it for queues and work at both ends. It supports efficient append and pop operations at either end, but indexing near the middle is not its strength.