Nodes scattered in memory, held together by pointers. Insertion costs nothing once you are there — but getting there costs everything, and that trade-off defines when to use one.
Overview
Before the details
A linked list stores each element in its own node, which also holds a pointer to the next node. Unlike an array, the elements need not sit next to each other in memory — the pointers are what impose the order.
Controls
valueposition
Nodes and Pointers
step 0
Cost of the last operation
Insight
Each node stores a value and a pointer to the next node. There is no index arithmetic — the only way to reach position k is to follow k pointers from the head.
Used for
• Queue & stack implementations
• Hash table collision chains
• LRU caches (doubly linked)
• Undo histories
Complexity
Insert / delete at headO(1)
Access by indexO(n)
SearchO(n)
Linked Lists
The structure that trades instant access for instant insertion.
The Fundamental Trade-off
An array gives you arr[500] in O(1) because the address is pure arithmetic: start + 500 × itemsize. A linked list has no such shortcut — you must start at the head and follow 500 pointers. That is O(n).
In exchange, inserting into the middle of an array costs O(n) because everything after the insertion point must shift up. In a linked list, once you are at the right place, insertion is O(1): create the node and rewire two pointers. Nothing moves.
Watch the cost table as you insert at position 0 versus the end — the traversal is where the time goes, never the insertion itself.
Rewiring, Step by Step
To insert node N after node P:
// N points to the rest of the list// P now points to NOrder matters absolutely. Do those two lines the other way round and you overwrite P.next before reading it — the remainder of the list becomes unreachable and is lost. This is the classic linked-list bug.
Singly vs Doubly Linked
Singly linked — one pointer per node. Less memory, but you can only travel forward, and deleting a node requires knowing its predecessor.
Doubly linked — next and prev. Costs more memory but allows backward traversal and O(1) deletion given only the node itself.
That last property is why LRU caches use a doubly linked list: when a hash lookup hands you a node, you can unlink and re-insert it at the front in constant time.
Why Arrays Often Win Anyway
Big-O says linked lists should beat arrays for insertion-heavy work. In practice arrays frequently win regardless, because of cache locality. Array elements sit contiguously in memory, so the CPU loads many at once. Linked-list nodes are scattered, and each pointer hop risks a cache miss costing hundreds of cycles.
This is a good reminder that Big-O counts operations, not time. Modern advice: reach for a dynamic array by default, and a linked list when you specifically need O(1) splicing with a node reference already in hand.
Nodes joined by references
A linked list stores each element in a node that holds a value and a reference to the next node. Nothing is contiguous in memory, and there is no index.
class Node:
def __init__(self, value, nxt=None):
self.value = value
self.next = nxt
# 1 -> 2 -> 3 -> None
head = Node(1, Node(2, Node(3)))
That single design difference from an array produces every trade-off:
Operation
Linked list
Array / Python list
Access by index
O(n) — must walk
O(1)
Insert at front
O(1)
O(n) — shifts everything
Insert after a known node
O(1)
O(n)
Insert at end
O(1) with a tail pointer
O(1) amortised
Delete a known node
O(1)
O(n)
Search
O(n)
O(n)
Memory per element
Value plus a pointer
Value only
Cache behaviour
Poor
Excellent
The last two rows are why Python's list is used almost everywhere despite the theoretical advantages above. A pointer per element is substantial overhead, and following pointers to scattered memory addresses defeats the CPU cache — frequently making an O(n) array scan faster in practice than an O(n) list walk.
Why insertion is O(1) only if you are already there
The advertised advantage — O(1) insertion and deletion — has a precondition that is easy to gloss over: you must already hold a reference to the relevant node.
Inserting after a node you have is three assignments. Inserting at position 500 means walking 500 nodes first, so the operation is O(n) overall.
That is why linked lists win in specific situations rather than generally: when you are already traversing, when you hold node references from elsewhere, or when you only ever touch the ends.
def insert_after(node, value):
node.next = Node(value, node.next) # O(1), given the node
def delete_after(node):
if node.next:
node.next = node.next.next # O(1), and the node is orphaned
For deleting a node you hold in a singly linked list, you need its predecessor — which you do not have. That is what doubly linked lists solve.
Singly, doubly, circular
Type
Each node holds
Enables
Singly linked
next
Minimal memory; forward traversal only
Doubly linked
next and prev
Backwards traversal; O(1) delete given the node
Circular
Last points to first
Round-robin iteration
Doubly linked is the practically important variant, because O(1) deletion given only the node is exactly what an LRU cache needs: a hash table maps keys to nodes, and the node can be unlinked and moved to the front in constant time.
That combination — hash table plus doubly linked list &mdash} is the standard LRU implementation, and it is the clearest example of a linked list being the right tool.
Circular lists suit round-robin scheduling and buffers where there is no natural end.
The sentinel or dummy-head trick is worth knowing: allocate one node before the real head, so insertion and deletion never need a special case for the first element. It removes most of the null checks that make linked-list code error-prone.
The trade, measured on both sides
Linked lists are taught as the alternative to arrays and then almost never used. Both halves of that are justified, and the reasons are opposite: the linked list wins the operation it is famous for and loses everything else, including some things by a much larger margin than the complexity table suggests.
example_01.pyPython
import time
class Node:
def __init__(self, val):
self.val = val
self.next = None
class LinkedList:
def __init__(self, values=()):
self.head = None
tail = None
for v in values:
n = Node(v)
if tail:
tail.next = n
else:
self.head = n
tail = n
def get(self, i):
# O(i): there is no arithmetic that finds the i-th node
n, steps = self.head, 0
while n and steps < i:
n = n.next
steps += 1
return n, steps + 1
def insert_after(self, node, val):
# O(1): two pointer writes, no matter how long the list is
new = Node(val)
new.next = node.next
node.next = new
return 2
n = 5000
lst = list(range(n))
ll = LinkedList(range(n))
print("INDEXING, %d elements" % n)
for i in (0, n // 2, n - 1):
_, steps = ll.get(i)
print(" index %5d: list = 1 step (address arithmetic), linked = %d steps"
% (i, steps))
# There is no fifth-element formula for a linked list. Every access walks
# from the head, which is why the O(1) indexing of an array is not a small
# advantage but a categorical one.
print()
print("INSERTING AT THE FRONT, %d times" % 10000)
t0 = time.time()
a = []
for i in range(10000):
a.insert(0, i) # shifts every element right
t1 = time.time()
ll2 = LinkedList()
for i in range(10000):
node = Node(i) # two writes, wherever the list is
node.next = ll2.head
ll2.head = node
t2 = time.time()
print(" list.insert(0, x): %7.1f ms" % ((t1 - t0) * 1000))
print(" linked prepend: %7.1f ms" % ((t2 - t1) * 1000))
# This is the operation linked lists exist for, and the gap is real.
#
# But now the part the complexity table hides. Insertion is O(1) only
# once you HAVE the node. Finding it is O(n), and in real code you almost
# always have to find it first:
print()
print("insert after the value 4000, including the search:")
node, steps = ll.get(4000)
writes = ll.insert_after(node, "new")
print(" linked: %d steps to find + %d pointer writes = %d operations"
% (steps, writes, steps + writes))
print(" list: 1 step to find + %d shifts = %d operations"
% (n - 4000, n - 4000 + 1))
# The linked list did MORE total work here, because walking 4001 nodes
# cost more than shifting 1000 array slots -- and shifting an array is a
# single memmove over contiguous memory, while walking a list is 4001
# dependent pointer dereferences, each one a potential cache miss.
#
# That last point is the one that decides it in practice. An array of
# 5000 ints occupies one contiguous block the CPU prefetches perfectly.
# The same 5000 as linked nodes are scattered objects, each holding a
# value and a pointer:
import sys
print()
print("memory for 5000 ints:")
print(" list: %8d bytes (plus the ints)" % sys.getsizeof(lst))
print(" linked nodes: %8d bytes (5000 objects, ~%d bytes each)" % (
5000 * (sys.getsizeof(Node(0)) + 16), sys.getsizeof(Node(0)) + 16))
# Which is why the honest summary is: use a linked list when you are
# splicing at a position you already hold -- an LRU cache moving a node to
# the front, a free list, an allocator -- and use an array for almost
# everything else.
Output
Try it yourself
Insert at position 0. Zero traversal steps — genuinely O(1), the linked list's best case.
Insert at the end. The cost table shows the traversal dominating; the rewiring is still just two assignments.
Delete from the middle and watch the pointer of the previous node jump over the removed one. Nothing else in the list moves.
Search for a value. Every node must be checked in order — no binary search is possible, because you cannot jump to the middle.
Switch to doubly linked and note the backward arrows, plus the extra pointer each node now has to store.
Where that leaves you
Linked lists make insertion and deletion cheap and access expensive — the exact opposite of arrays. Use them when you hold a reference to the node you need and are splicing constantly; otherwise an array's cache behaviour usually beats the theory.
The classic manipulations
Reversal is the canonical exercise, and the three-pointer form is worth knowing by heart:
def reverse(head):
prev = None
while head:
head.next, prev, head = prev, head, head.next
return prev
Each step redirects one node's pointer backwards. The tuple assignment does it without a temporary, and the order matters: head.next is read on the right before being overwritten.
Finding the middle in one pass, with fast and slow pointers:
def middle(head):
slow = fast = head
while fast and fast.next:
slow, fast = slow.next, fast.next.next
return slow
Cycle detection (Floyd's algorithm) uses the same pointers and checks whether they meet. Resetting one to the head after they meet and advancing both by one finds the cycle's entry point.
Merging two sorted lists requires only pointer rearrangement and no extra allocation, which is why merge sort on a linked list uses O(1) extra space where merge sort on an array uses O(n).
Those four cover most linked-list problems, and all four are single-pass with constant extra memory.
When to actually use one
Genuinely good uses:
LRU caches — doubly linked list plus hash map.
Queues and deques — though collections.deque uses a block-based structure that is better than a pure linked list.
Adjacency lists in some graph representations.
Free lists in memory allocators.
Undo stacks and version chains where nodes are held by reference.
Immutable and persistent lists in functional languages, where sharing a tail between versions is free.
Poor uses:
Anything needing indexed access.
Anything where a Python list would do, which is most application code.
Large collections traversed frequently — the cache penalty is real and often decisive.
In Python specifically, you will rarely implement one. list covers dynamic arrays, collections.deque covers double-ended queues efficiently. Linked lists appear as interview material and inside libraries rather than in ordinary code — which does not make them unimportant, because the pointer-manipulation reasoning transfers to trees and graphs.
Common mistakes
Losing the head reference while traversing, so the list becomes unreachable.
Not handling the empty list or single node. Most linked-list bugs live at these boundaries; a sentinel node removes them.
Assigning pointers in the wrong order, orphaning the rest of the list. Read what you need before overwriting it.
Forgetting to update the tail pointer when appending or deleting at the end.
Creating a cycle accidentally, which turns any traversal into an infinite loop.
Deleting a node in a singly linked list without its predecessor, which cannot be done properly — the usual hack copies the next node's value and deletes that node instead, and it fails on the last node.
Questions people ask
Why use a linked list when arrays are faster? For O(1) insertion and deletion at a held reference, and when there is no capacity to resize. Those cases are narrower than textbooks suggest.
Is a Python list a linked list? No — it is a dynamic array of pointers, contiguous, with O(1) indexing.
How do I find the length? Walk it: O(n). Maintain a counter if the length is needed often.
Singly or doubly linked? Doubly if you need backwards traversal or O(1) deletion given a node; singly to save the pointer.
Why is collections.deque fast? It is a doubly linked list of fixed-size blocks, so it gets O(1) ends with much better cache behaviour than one node per element.
Are linked lists still relevant? As a data structure in application code, rarely. As the reasoning behind trees, graphs, allocators and persistent structures, very.
Recap in one screen
Each node holds a value and a reference; nothing is contiguous and there is no index.
O(1) insertion and deletion — but only at a node you already hold; reaching position k is O(n).
Doubly linked lists enable O(1) deletion given the node, which is what LRU caches rely on.
Poor cache behaviour and a pointer per element make arrays faster in practice for most work.
Use a sentinel head to remove the empty-list and first-element special cases that cause most bugs.
Run it in Python
A singly linked list with insert, delete, search and an in-place reversal — the operation that is genuinely hard to get right and the reason this structure keeps appearing in interviews.
linked_list.pyPython 3
# A singly linked list: each node holds a value and a reference to the next.
class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next
class LinkedList:
def __init__(self, values=()):
self.head = None
for v in reversed(list(values)): # build back to front
self.head = Node(v, self.head)
def __repr__(self):
parts, node = [], self.head
while node:
parts.append(str(node.value))
node = node.next
return " -> ".join(parts) + " -> None"
def push_front(self, value): # O(1) - no shifting, ever
self.head = Node(value, self.head)
def insert_after(self, target, value): # O(1) once you hold the node
node = self.find(target)
if node:
node.next = Node(value, node.next)
def find(self, value, verbose=False): # O(n) - no random access
node, steps = self.head, 0
while node:
steps += 1
if node.value == value:
if verbose:
print(f"find({value}) : {steps} hop(s) from the head")
return node
node = node.next
return None
def delete(self, value):
# The dummy head removes the "deleting the first node" special case.
dummy = Node(None, self.head)
prev = dummy
while prev.next:
if prev.next.value == value:
prev.next = prev.next.next # unlink; nothing moves
self.head = dummy.next
return True
prev = prev.next
return False
def reverse(self):
prev, node = None, self.head
while node:
nxt = node.next # save it BEFORE overwriting
node.next = prev # flip the arrow
prev, node = node, nxt # step both forward
self.head = prev
ll = LinkedList([10, 20, 30, 40])
print("start :", ll)
ll.push_front(5)
print("push_front(5):", ll)
ll.insert_after(20, 25)
print("insert 25 :", ll)
ll.delete(10)
print("delete 10 :", ll)
ll.find(40, verbose=True)
ll.reverse()
print("reversed :", ll)
Output
How the code works
self.head = Node(value, self.head)Inserting at the front is O(1) and involves no movement at all — the new node simply points at the old head. The same insert into a Python list costs O(n).
while node: ... node = node.nextThere is no arithmetic that jumps to element 5. Every access starts at the head and hops, which is why linked lists lose to arrays on almost every read-heavy workload despite the better insert.
dummy = Node(None, self.head)The sentinel trick. Without it, deleting the first node needs its own branch because there is no previous node to re-point — and that branch is where the bug always is.
prev.next = prev.next.nextDeletion is one assignment. Nothing is shifted and no memory is moved, which is the operation linked lists exist for.
nxt = node.next; node.next = prevThe order is the whole exercise. Overwrite node.next before saving it and the rest of the list is unreachable — not corrupted, just gone.
Change one thing
Delete the nxt = node.next line in reverse and print the result. The list is one node long, and the other three are lost.
Build a list of 100,000 nodes and time find on the last value against the same lookup on a Python list. Both are O(n), and the linked version is far slower — cache locality, not complexity.
Add a prev pointer to make it doubly linked. Deletion no longer needs the node before it, which is exactly what collections.deque buys with the extra memory.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.
Check yourself
0 of 3
Answer without scrolling back up.
In reverse(), why is 'nxt = node.next' saved before 'node.next = prev'?
Overwriting the only pointer to the remainder loses it - not corrupted, just gone. Delete the line and the list comes back one node long.
What is the dummy head in delete() for?
Without a previous node to re-point, deleting the head needs its own branch - and that branch is where the bug always is.
Compared with a Python list, a linked list is better at:
O(1) with no shifting. It loses on everything else, including sequential scans, because the nodes are scattered in memory.
Cheat sheet
Linked Lists
Nodes scattered in memory, held together by pointers. Insertion costs nothing once you are there — but getting there costs everything, and that trade-off defines when to use one.
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.