The Story Behind Linked Lists
Adding a new carriage anywhere is easy: unhook two adjacent carriages, insert the new one, re-hook. The entire rest of the train doesn't move. Removing a carriage is equally painless: unhook it and link its neighbours directly together.
But if you want to find, say, the 47th carriage, you have no choice but to walk from the locomotive, one carriage at a time. There is no shortcut. That trade-off — cheap reshuffling, expensive lookup — is the soul of a linked list.
A linked list is a sequence of nodes scattered anywhere in memory. Each node stores a value and a pointer to the next node. Unlike arrays, nodes do not need to be contiguous — the pointer chain is what gives the list its order.
Think of each node as a sticky note with two fields: a data field
(the value you care about) and a next field (an arrow pointing to the
next sticky note). The list itself is just a variable called head that holds
the arrow to the very first note. If head is None, the list is empty.
Three Flavours of Linked List
next.
Traversal is one-directional — forward only. Cannot go backwards without restarting from head.
Lowest memory overhead: one pointer per node.
next and prev pointers.
Traversal works in both directions. Deletion is O(1) if you already have the node reference.
Used in Python's collections.deque.
next points back to the head instead of None.
Useful for round-robin schedulers, music playlists, and buffer rings.
Can be singly or doubly circular.
We implement a complete singly linked list from scratch using only Python classes —
no built-in list, deque, or any other container.
Every node is an object. Every operation is written explicitly so you can see exactly
what happens in memory at each step.
Interactive Diagram — See the Pointers Move
Select an operation and step through each frame. Arrows represent pointers. Orange = currently followed pointer · Green = newly written · Red = being removed · Blue = being read/traversed.
Time Complexity — Linked List vs Array
| Operation | Linked List | Array (dynamic) | Who Wins? |
|---|---|---|---|
| Access by index | O(n) | O(1) | Array — direct address arithmetic |
| Search (unsorted) | O(n) | O(n) | Tie — both scan linearly |
| Prepend (insert at head) | O(1) | O(n) | Linked List — just re-point head |
| Append (insert at tail) | O(n)* | O(1) amort. | Array wins; O(1) with tail pointer |
| Insert in middle | O(n) find + O(1) | O(n) | Linked List once found — no shifting |
| Delete head | O(1) | O(n) | Linked List — just move head pointer |
| Delete middle/tail | O(n) find + O(1) | O(n) | Linked List once found — no shifting |
| Memory per element | data + pointer | data only | Array — no pointer overhead |
| Cache performance | Poor (scattered) | Excellent | Array — contiguous = cache-friendly |
Walking to the tail every append is wasteful. Store a self.tail pointer
alongside self.head. Append becomes: create node, set self.tail.next = node,
update self.tail = node — all O(1). Our implementation below includes this optimisation.
Full Python Implementation — Classes Only
Below is a complete singly linked list built entirely from Python classes.
No list, no deque, no imports. Every node is an object.
Every operation is explicit.
The Node Class
# ── Node: the building block ──────────────────────────────────
class Node:
def __init__(self, data):
self.data = data # the value this node holds
self.next = None # pointer to next node (None = no next)
def __repr__(self):
return f"Node({self.data})"
That is the entire definition. data holds the value.
next holds a reference to another Node object — or
None if this is the last node. There is nothing else.
The entire power of a linked list comes from chaining these tiny objects together.
The LinkedList Class — Full Implementation
# ── LinkedList: manages the chain of nodes ────────────────────
class LinkedList:
def __init__(self):
self.head = None # first node (None = empty list)
self.tail = None # last node (tail pointer for O(1) append)
self.size = 0 # number of nodes
# ── helpers ───────────────────────────────────────────────
def __len__(self):
return self.size
def is_empty(self):
return self.head is None
def __repr__(self):
parts, cur = [], self.head
while cur:
parts.append(str(cur.data))
cur = cur.next
return " → ".join(parts) + " → None"
# ── prepend: insert at head — O(1) ───────────────────────
def prepend(self, data):
new_node = Node(data)
new_node.next = self.head # new node points to old head
self.head = new_node # head now points to new node
if self.tail is None: # first node ever inserted
self.tail = new_node
self.size += 1
# ── append: insert at tail — O(1) with tail pointer ──────
def append(self, data):
new_node = Node(data)
if self.tail is None: # empty list
self.head = self.tail = new_node
else:
self.tail.next = new_node # current tail points to new node
self.tail = new_node # update tail pointer
self.size += 1
# ── insert_after: insert after a given value — O(n) find ─
def insert_after(self, target, data):
current = self.head
while current:
if current.data == target:
new_node = Node(data)
new_node.next = current.next # bridge to rest of list
current.next = new_node # predecessor links to new node
if current is self.tail: # inserted after old tail
self.tail = new_node
self.size += 1
return True
current = current.next
return False # target not found
# ── delete: remove node by value — O(n) ──────────────────
def delete(self, data):
if self.is_empty():
return False
if self.head.data == data: # deleting the head
self.head = self.head.next
if self.head is None: # list is now empty
self.tail = None
self.size -= 1
return True
current = self.head
while current.next:
if current.next.data == data:
if current.next is self.tail: # deleting the tail
self.tail = current
current.next = current.next.next # unlink the node
self.size -= 1
return True
current = current.next
return False # not found
# ── search: find node by value — O(n) ────────────────────
def search(self, data):
current, idx = self.head, 0
while current:
if current.data == data:
return idx # return position (0-based)
current = current.next
idx += 1
return -1 # not found
# ── get: access by index — O(n) ──────────────────────────
def get(self, index):
if index < 0 or index >= self.size:
raise IndexError(f"Index {index} out of range")
current = self.head
for _ in range(index):
current = current.next
return current.data
# ── reverse: reverse in-place — O(n) ─────────────────────
def reverse(self):
prev, current = None, self.head
self.tail = self.head
while current:
nxt = current.next
current.next = prev
prev = current
current = nxt
self.head = prevCode Execution Animator — Watch Every Line Run
Each tab shows a different method executing step by step. The highlighted line is what is currently running. The chain panel updates to reflect pointer changes in real time. The variable watch tracks every live variable.
The purple ▶ arrow marks the active line. In the chain panel: green border = new node created, amber border = head pointer updated, red border = marked for deletion, blue border = currently traversed, purple border = found/result. The tail label tracks the tail pointer separately from head.
Full Demo — Putting It All Together
# ── Full demo using our LinkedList class ──────────────────────
ll = LinkedList()
# Build the list
ll.append(10) # 10
ll.append(30) # 10 → 30
ll.append(40) # 10 → 30 → 40
ll.prepend(5) # 5 → 10 → 30 → 40
ll.insert_after(10, 20) # 5 → 10 → 20 → 30 → 40
print("List :", ll)
print("Length :", len(ll))
print("Head :", ll.head.data)
print("Tail :", ll.tail.data)
print("Search 20:", ll.search(20)) # returns index 2
print("Get [2] :", ll.get(2)) # returns 20
# Modify
ll.delete(5) # remove head
ll.delete(40) # remove tail
print("After del:", ll)
# Reverse
ll.reverse()
print("Reversed :", ll)6 Golden Rules for Linked Lists
append() walks
the entire list — O(n) per call. With a tail pointer, append is O(1).
A linked list without a tail pointer is half-implemented.
get(index) on a linked list is O(n). If you access elements by index
frequently, use an array. The linked list's O(1) insert/delete advantage only matters
if you already have a reference to the node.
delete(), search(), get() — all must check
self.head is None before dereferencing. A single unguarded
.next on a None object gives AttributeError.
head and tail as needed.
A stale tail pointer causes insidious bugs — appends go to the wrong place silently.
collections.deque is one.