Singly linked list
easyInsert at the front without shifting a single element - then search for a value and count the hops. That trade is the entire reason linked lists exist, and the entire reason arrays usually win anyway.
O(1) head insertAverage O(n) searchWorst O(n)Space O(n)What to notice
Insertion at the head is genuinely O(1)
Compare with the array visualizer, where inserting at the front shifts every element. A list just points a new node at the old head. That single asymmetry is why lists exist.
But everything else costs a walk
There is no arithmetic that finds node 5 - you must follow five pointers. No random access, no binary search, and each hop is a potential cache miss on unrelated memory.
Arrays win more often than textbooks suggest
A list wins on paper for front insertion, but arrays are contiguous and prefetch beautifully. For small and medium sizes, an array with memmove usually beats a linked list even at what the list is supposed to be good at.
Saved in this browser - no sign-up, nothing sent anywhere.
How a singly linked list works
An array stores elements shoulder to shoulder, so position 5 is one multiplication away but inserting at the front shifts everything. A singly linked list makes the opposite trade: each node stores a value plus the address of the next node, and nothing else. Inserting at the head is two pointer writes - point the new node at the old head, move head - whether the list holds 4 elements or 4 million.
The cost is that the address arithmetic disappears. To reach the fourth node you follow three next pointers; to find a value you may follow all of them. This variant keeps only a head pointer, so even appending at the tail walks the whole list first - 4 hops on a 4 node list before the single O(1) link.
Reach for it when you genuinely insert and delete at the front a lot, or when nodes must keep stable identities while order changes around them - which is exactly how the LRU cache uses its list. For plain sequential storage, arrays are contiguous, prefetch well, and usually win even at front insertion for small and medium sizes.
Step by step
- Start with four nodes holding 12, 37, 5, 84. head points at 12; each node knows only its successor's address.
- insertHead(9): allocate a node, point its next at 12, move head to it. Two writes, and the list reads 9, 12, 37, 5, 84.
- insertTail(60): there is no tail pointer, so follow next five times to reach 84, then link 60 on. The write was O(1); the walk was not.
- search(5): compare against 9, 12, and 37 - three misses - then find 5 on the fourth hop.
- deleteValue(37): walk while remembering the previous node. At 37, set 12's next to 5. One write; nothing in memory moves.
- The list is now 9, 12, 5, 84, 60. Only the head operations were constant time - everything else paid a walk.
Complexity
| Best case time | O(1) head insert |
|---|---|
| Average time | O(n) search |
| Worst case time | O(n) |
| Space | O(n) |
Reference implementation
Python
class Node:
def __init__(self, value):
self.value = value
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def insert_head(self, v):
n = Node(v)
n.next = self.head # O(1) - nothing shifts
self.head = n
def insert_tail(self, v):
n = Node(v)
if not self.head:
self.head = n
return
cur = self.head
while cur.next: # O(n) without a tail pointer
cur = cur.next
cur.next = n
def search(self, v):
cur, i = self.head, 0
while cur:
if cur.value == v:
return i
cur, i = cur.next, i + 1
return -1JavaScript
class Node {
constructor(value) { this.value = value; this.next = null; }
}
class LinkedList {
head = null;
insertHead(v) {
const n = new Node(v);
n.next = this.head;
this.head = n; // O(1)
}
search(v) {
let cur = this.head, i = 0;
while (cur) { // O(n) - no random access
if (cur.value === v) return i;
cur = cur.next; i++;
}
return -1;
}
}Common pitfalls
- Losing the list by reordering writes: assign head = n before n.next = head and the new node ends up pointing at itself.
- Forgetting the empty-list case: insertTail must check for a null head before walking, or the very first cur.next dereferences null.
- Deleting without tracking the predecessor - you cannot unlink a node from a singly linked list without a pointer to the node before it.
- Using a linked list for random access workloads: every index lookup is a pointer chase, and each hop is a potential cache miss on unrelated memory.
- Keeping no tail pointer when appends dominate - every append becomes an O(n) walk, which this variant demonstrates on purpose.
Where it is used
- Implementing stacks and queues where all activity stays at the ends.
- The chain inside a hash table bucket, where colliding keys link into a list.
- Interview staples - reversal, cycle detection and merging assume exactly this node-and-pointer layout.
- Free lists in allocators and object pools, where recycled memory is threaded into a chain.
Frequently asked questions
What is the time complexity of a singly linked list?
Insertion at the head is O(1) - two pointer writes regardless of length. Search is O(n) on average and O(n) worst case, because reaching any element means walking from the head. The structure itself takes O(n) space: one node per element, each carrying one extra pointer.
Is a linked list better than an array?
Usually not. A list wins on paper for front insertion, but arrays are contiguous and prefetch well, so for small and medium sizes an array with memmove typically beats a list even at what the list is supposed to be good at. Measure before switching.
Why can you not binary search a linked list?
Binary search needs to jump to the middle in O(1), and a list cannot - reaching node n/2 costs n/2 hops. Any attempt degenerates into O(n) walking, at which point a plain linear scan is simpler and no slower.
When does inserting at the tail cost O(n)?
When the list only keeps a head pointer, as this variant does: reaching the last node means following every next pointer first. Keeping a separate tail pointer makes appends O(1), at the cost of one more field to keep consistent on every mutation.