I have used linked lists in Python projects for years, and I keep coming back to them when I need fast insertions or deletions in the middle of a collection. Arrays give you O(1) random access, but inserting at position 0 means shifting everything. A linked list sidesteps that entirely. Let me show you how they work and when they actually make sense.
In this article, I walk through what linked lists are, how to build one from scratch in Python, and the operations that make them worth using. I have tested each code example against Python 3.12.
TLDR
- Linked lists store elements as nodes, each pointing to the next element
- Insertion at the head is O(1). Traversal to find an element is O(n)
- Python has no built-in linked list, but a Node class plus a LinkedList class gives you full control
- Use a linked list when you do frequent insertions/deletions and rarely need random access
- The built-in deque in Python is a doubly linked list and handles most real-world cases
What is a Linked List?
A linked list is a linear data structure where each element lives in its own memory location. Instead of sitting next to each other like items in an array, each element – called a node – stores two things: the data you want to keep, and a pointer to the next node in the sequence.
Here is the key difference from arrays. When you insert an element at position 0 in a Python list, every existing element shifts one position to the right. That is O(n) time. With a linked list, you create a new node, point it at the old head, and update the head pointer. That is O(1).
The trade-off is random access. Want the 500th element? An array gives you that in one step. A linked list forces you to walk from the head through 499 pointers to reach it. That is O(n).
Each linked list tracks two things: the head (first node) and optionally the tail (last node). The tail’s next pointer is None, marking the end.
Building a Linked List from Scratch
Python does not ship with a linked list type, so I build my own whenever the built-in list does not fit the access pattern. The implementation has two classes: Node to hold data and a pointer, and LinkedList to manage the collection.
The Node Class
A node needs two fields: data to hold the value, and next_node to point to the following node. When next_node is None, that node is the tail of the list.
class Node:
def __init__(self, data, next_node=None):
self.data = data
self.next_node = next_node
The LinkedList Class
The LinkedList class starts with a head pointer. I initialize it as None, representing an empty list. The class also tracks the size so I do not have to count nodes every time.
class LinkedList:
def __init__(self, head=None):
self.head = head
self.size = 0
Core Operations
Let me walk through the four operations I reach for most often: printing, inserting at the head, finding a node, and deleting a node. Each one shows a different trade-off compared to a Python list.
Print the List
Traversal means walking node by node from head to tail. I keep moving forward until next_node is None. This touches every node exactly once, which is O(n).
def print_list(self):
current = self.head
while current:
print(current.data, end=" -> ")
current = current.next_node
print("None")
Insert at Head
Inserting at the head takes three steps. Create the new node, point it at the current head, then update the head pointer. No shifting required.
def insert_at_head(self, data):
new_node = Node(data)
new_node.next_node = self.head
self.head = new_node
self.size += 1
Search for a Node
To find a node by value, I traverse the list and compare each node’s data with the target. If I reach the tail without a match, the value is not in the list.
def find_node(self, target):
current = self.head
while current:
if current.data == target:
return current
current = current.next_node
return None
Delete a Node
Deletion requires keeping a reference to the previous node so I can bypass the deleted node and connect the prior node directly to the next one. For the head, I just move the head pointer forward.
def delete_node(self, target):
current = self.head
if current and current.data == target:
self.head = current.next_node
self.size -= 1
return
prev = current
current = current.next_node
while current:
if current.data == target:
prev.next_node = current.next_node
self.size -= 1
return
prev = current
current = current.next_node
Putting It All Together
Here is the full implementation with all four operations. I use an if __name__ == “__main__” guard to run a quick demo.
class Node:
def __init__(self, data, next_node=None):
self.data = data
self.next_node = next_node
class LinkedList:
def __init__(self, head=None):
self.head = head
self.size = 0
def print_list(self):
current = self.head
while current:
print(current.data, end=" -> ")
current = current.next_node
print("None")
def insert_at_head(self, data):
new_node = Node(data)
new_node.next_node = self.head
self.head = new_node
self.size += 1
def find_node(self, target):
current = self.head
while current:
if current.data == target:
return current
current = current.next_node
return None
def delete_node(self, target):
current = self.head
if current and current.data == target:
self.head = current.next_node
self.size -= 1
return
prev = current
current = current.next_node
while current:
if current.data == target:
prev.next_node = current.next_node
self.size -= 1
return
prev = current
current = current.next_node
if __name__ == "__main__":
ll = LinkedList()
for val in [3, 2, 1]:
ll.insert_at_head(val)
ll.print_list()
# Output: 1 -> 2 -> 3 -> None
print(ll.find_node(2).data)
# Output: 2
ll.delete_node(2)
ll.print_list()
# Output: 1 -> 3 -> None
When to Use a Linked List in Python
Python’s built-in list is implemented as a dynamic array. It is excellent for random access and appending to the end. For most tasks, use a list.
That said, I reach for a linked list in three situations. First, when I am doing many insertions and deletions at arbitrary positions and the O(n) shift cost of a list matters in practice. Second, when I am implementing other data structures like stacks, queues, or adjacency lists for graphs. Third, when memory is fragmented and I cannot allocate a contiguous block for an array.
For most cases where I need queue or deque behavior, Python’s collections.deque is already a doubly linked list. It handles O(1) inserts and deletes at both ends and is far more battle-tested than anything I write myself.
from collections import deque
dq = deque()
dq.appendleft("first")
dq.append("last")
print(dq.popleft())
# Output: first
Linked Lists vs Arrays
The key trade-off comes down to access pattern. Arrays give you O(1) indexed access at the cost of O(n) insertions in the middle. Linked lists give you O(1) insertions anywhere if you have a pointer to that position, at the cost of O(n) searches.
Python’s list type is not a pure array – it over-allocates capacity and uses amortized analysis, so append is O(1) most of the time. The constant factors for linked list operations are also higher because they involve pointer chasing and memory allocation per node. In practice, unless I have profiled and found the list to be the bottleneck, I stick with the built-in list.
FAQ
Q: Does Python have a built-in linked list?
Python does not ship with a standalone linked list type. The collections.deque a doubly linked list and covers most use cases for queue-like access patterns.
Q: When is a linked list faster than a Python list?
A linked list is faster when performing many insertions or deletions at known positions without shifting existing elements. For random access, a Python list is significantly faster because it supports O(1) indexed lookups.
Q: What is the time complexity of searching in a linked list?
Searching in a singly linked list requires traversing from the head until a match is found or the tail is reached. This is O(n) in the worst case, where n is the number of nodes.
Q: How is a doubly linked list different?
A doubly linked list has each node store both a next pointer and a previous pointer. This enables O(1) deletion when given a node reference, since the previous node is accessible without traversal. Python’s collections.deque is a doubly linked list.
Q: What is the space overhead of a linked list?
Each node stores its data plus one pointer. For an integer list, this means roughly 8 bytes for the data and 8 bytes for the pointer on a 64-bit system, plus Python object overhead. An array of the same integers packs them contiguously with no pointer overhead.
I keep coming back to linked lists when I need to understand how stacks and queues work under the hood, or when I am implementing graph algorithms that need adjacency lists. For production code, collections.deque covers most scenarios and performs better than a hand-rolled singly linked list.
