Once I had a solid Node class figured out, the next logical step was building an actual working singly linked list around it — one that I could insert into, delete from, search, and traverse just like any other data structure I’d use in a real project. In this guide, I want to build a complete, practical singly linked list implementation in Python, explain how each operation works internally, and cover the complexity trade-offs compared to Python’s built-in list.
What Is a Singly Linked List?
A singly linked list is a linear collection of nodes where each node points to the next node in the sequence, and the last node points to None. Unlike arrays, there’s no direct indexing — to reach the 5th element, I have to traverse from the head, following next references one at a time.
[Head] -> Node(10) -> Node(20) -> Node(30) -> None
Building the Node and LinkedList Classes
class Node:
__slots__ = ("data", "next")
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
self.size = 0
def __len__(self):
return self.size
def is_empty(self):
return self.head is None
Inserting Elements
I like to support insertion at three positions: the beginning, the end, and an arbitrary index.
Insert at the Beginning
class LinkedList(LinkedList):
def insert_at_head(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node
self.size += 1
This operation is O(1) because I don’t need to traverse anything — I just point the new node at the current head and make it the new head.
Insert at the End
class LinkedList(LinkedList):
def insert_at_tail(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
else:
current = self.head
while current.next is not None:
current = current.next
current.next = new_node
self.size += 1
This is O(n) because I have to walk the entire list to find the last node. A common optimization I use in production-quality implementations is maintaining a self.tail reference so this becomes O(1):
class LinkedList:
def __init__(self):
self.head = None
self.tail = None
self.size = 0
def insert_at_tail(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
self.tail = new_node
else:
self.tail.next = new_node
self.tail = new_node
self.size += 1
Insert at a Specific Index
class LinkedList:
def insert_at_index(self, index, data):
if index < 0 or index > self.size:
raise IndexError("Index out of bounds")
if index == 0:
self.insert_at_head(data)
return
new_node = Node(data)
current = self.head
for _ in range(index - 1):
current = current.next
new_node.next = current.next
current.next = new_node
self.size += 1
Traversing and Printing the List
class LinkedList:
def to_list(self):
result = []
current = self.head
while current is not None:
result.append(current.data)
current = current.next
return result
def __repr__(self):
return " -> ".join(str(x) for x in self.to_list()) + " -> None"
Let me put all these pieces together into a complete, working example:
class Node:
__slots__ = ("data", "next")
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
self.tail = None
self.size = 0
def __len__(self):
return self.size
def is_empty(self):
return self.head is None
def insert_at_head(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node
if self.tail is None:
self.tail = new_node
self.size += 1
def insert_at_tail(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
self.tail = new_node
else:
self.tail.next = new_node
self.tail = new_node
self.size += 1
def delete_value(self, value):
current = self.head
previous = None
while current is not None:
if current.data == value:
if previous is None:
self.head = current.next
else:
previous.next = current.next
if current is self.tail:
self.tail = previous
self.size -= 1
return True
previous = current
current = current.next
return False
def search(self, value):
current = self.head
index = 0
while current is not None:
if current.data == value:
return index
current = current.next
index += 1
return -1
def to_list(self):
result = []
current = self.head
while current is not None:
result.append(current.data)
current = current.next
return result
def __repr__(self):
return " -> ".join(str(x) for x in self.to_list()) + " -> None"
ll = LinkedList()
ll.insert_at_tail(10)
ll.insert_at_tail(20)
ll.insert_at_tail(30)
ll.insert_at_head(5)
print(ll)
print("Length:", len(ll))
print("Index of 20:", ll.search(20))
ll.delete_value(20)
print(ll)
Output:
5 -> 10 -> 20 -> 30 -> None
Length: 4
Index of 20: 2
5 -> 10 -> 30 -> None
Reversing a Singly Linked List
Reversing a linked list is a classic exercise that tests whether I truly understand pointer manipulation:
class LinkedList(LinkedList):
def reverse(self):
previous = None
current = self.head
self.tail = current
while current is not None:
next_node = current.next
current.next = previous
previous = current
current = next_node
self.head = previous
This runs in O(n) time and O(1) extra space, since I’m just re-pointing existing nodes rather than creating new ones.
Time and Space Complexity Summary
| Operation | Time Complexity | Notes |
|---|---|---|
| Insert at head | O(1) | No traversal needed |
| Insert at tail (with tail pointer) | O(1) | Requires maintaining a tail reference |
| Insert at tail (no tail pointer) | O(n) | Must traverse to find the last node |
| Insert at index | O(n) | Must traverse to the index |
| Delete by value | O(n) | Must search before deleting |
| Search | O(n) | Linear scan, no random access |
| Reverse | O(n) | Single pass, constant extra space |
Compare this to Python’s built-in list, which offers O(1) indexing and O(1) amortized append, but O(n) insertion/removal at the front (since every element has to shift). This is exactly why I choose a linked list when I expect a lot of insertions/removals at the front or middle of a sequence, and a regular Python list when I mostly need fast random access and appending at the end.
Memory Considerations
Each node in my linked list carries the overhead of a full Python object (even with __slots__, there’s a base object header) plus a reference to the next node. For large collections of simple values like integers, a Python list (which is really a dynamic array of pointers to objects) is often more memory-efficient overall, because it doesn’t need a separate node wrapper object for each element. I generally only reach for a hand-built linked list in Python when the structural properties — O(1) insertion/removal given a node reference, no need for shifting — actually matter for my use case, rather than for raw memory efficiency.
Real-World and Automation Use Cases
- Implementing a custom queue or stack when I want explicit control over node-level behavior.
- Undo/redo history in an application, where each action is a node I can traverse backward and forward through.
- Building blocks for more advanced structures, like a hash table with separate chaining, where each bucket is itself a small linked list.
- Music/playlist “next song” logic, where each song naturally points to the next one in sequence.
- Polynomial representation in symbolic math tools, where each node represents a term with a coefficient and exponent.
Common Mistakes and Debugging Tips
- Losing the head reference. If I accidentally overwrite
self.headbefore capturing what it originally pointed to, I lose access to the rest of the list. I’m especially careful during reversal and deletion operations. - Forgetting to update the tail pointer. If I maintain a
tailreference for O(1) appends, I have to remember to update it during deletions and reversals too — otherwise it becomes stale and later inserts behave incorrectly. - Off-by-one errors on index-based insertion. I always double check boundary conditions: what happens when
index == 0orindex == size? - Creating accidental cycles. During manual pointer manipulation (especially reversal), it’s easy to create a cycle by mismanaging
nextassignments — testing thoroughly with small lists helps catch this early.
Best Practices I Follow
- Maintain a
tailpointer if tail insertions are common, to avoid unnecessary O(n) traversals. - Track
sizeincrementally rather than recomputing it by traversal every timelen()is called. - Write a
__repr__method early for easier debugging. - Test edge cases explicitly: empty list, single-element list, deleting the head, deleting the tail.
FAQs
Q: When should I use a linked list instead of Python’s built-in list? When I need frequent insertions or deletions at the front or middle of the sequence, and I don’t need fast random access by index.
Q: Is a Python list actually a linked list internally? No — Python’s built-in list is implemented as a dynamic array (a contiguous block of pointers to objects), not a linked list.
Q: What’s the main disadvantage of a singly linked list? No backward traversal (that requires a doubly linked list), and O(n) access time for arbitrary indices.
Q: How do I know if I’ve created a cycle by mistake? Use Floyd’s cycle detection algorithm (the “tortoise and hare” technique) to check for cycles efficiently in O(n) time and O(1) space.
Troubleshooting Tips
- If deletion doesn’t seem to work, verify that you’re updating the
previous.nextreference, not the current node’s data. - If your list “shrinks” unexpectedly, check whether
sizeis being decremented correctly during deletion. - If reversal produces a broken or partial list, trace through the three-pointer dance (
previous,current,next_node) with a small 3-node list on paper first.
Summary
Building a singly linked list from scratch taught me more about pointers, references, and memory than years of just using Python’s built-in list ever did. Once I internalized the trade-offs — O(1) head insertion versus O(n) search, and no random access — I got a much clearer sense of when a linked list is genuinely the right tool, versus when Python’s built-in list is simply the better, simpler choice.
