🚂 Analogy
A linked list is a train: each car holds cargo and a coupling to the next car. To find the 50th car you walk from the engine, car by car — there’s no teleporting to the middle. But to add or remove a car, you just unclip and reclip two couplings, no matter how long the train is.
A node points to the next node
Each node carries a value and a pointer to the next node; the last points to nil. The list keeps a Head:
graph LR H["Head"] --> A["1 • "] --> B["2 • "] --> C["3 • "] --> N["nil"]
type Node[T any] struct {
Val T
Next *Node[T]
}
type List[T any] struct {
Head *Node[T]
size int
}Prepend is O(1); access is O(n)
Adding to the front is a single pointer rewrite — no shifting, no reallocation. Walking to a position is linear. Build one and print it:
package main
import (
"fmt"
"strings"
)
type Node[T any] struct {
Val T
Next *Node[T]
}
type List[T any] struct {
Head *Node[T]
size int
}
// Prepend inserts at the front in O(1).
func (l *List[T]) Prepend(v T) {
l.Head = &Node[T]{Val: v, Next: l.Head}
l.size++
}
func (l *List[T]) String() string {
var b strings.Builder
for n := l.Head; n != nil; n = n.Next { // O(n) walk
fmt.Fprintf(&b, "%v -> ", n.Val)
}
b.WriteString("nil")
return b.String()
}
func main() {
l := &List[int]{}
for _, v := range []int{3, 2, 1} {
l.Prepend(v)
}
fmt.Println(l) // 1 -> 2 -> 3 -> nil
fmt.Println("size:", l.size)
}
The reversal classic
Reversing a list in place is the interview staple — three pointers, one pass, O(1) extra space:
package main
import "fmt"
type Node struct {
Val int
Next *Node
}
func reverse(head *Node) *Node {
var prev *Node
for head != nil {
next := head.Next // 1. stash the rest of the list
head.Next = prev // 2. flip this link backward
prev = head // 3. prev advances
head = next // 4. head advances
}
return prev // new head
}
func print(head *Node) {
for n := head; n != nil; n = n.Next {
fmt.Printf("%d -> ", n.Val)
}
fmt.Println("nil")
}
func main() {
// build 1 -> 2 -> 3 -> 4
var head *Node
for i := 4; i >= 1; i-- {
head = &Node{Val: i, Next: head}
}
print(head)
print(reverse(head))
}
Singly, doubly, and the standard library
A doubly linked list adds a Prev pointer, so you can walk backward and delete a node in O(1) given only that node. Go ships one in container/list — reach for it rather than rolling your own when you genuinely need list semantics (for example, the O(1) move-to-front in an LRU cache).
⚠️ In Go, a slice usually wins
Linked lists look elegant but each node is a separate heap allocation scattered across memory, so traversal thrashes the CPU cache — often slower than a slice even where Big-O says otherwise. Pointer chasing also pressures the GC. Reach for a linked list only when you truly need O(1) splicing at a held position (LRU, intrusive queues); otherwise a []T is simpler and faster.
See also
- arrays & slices — the cache-friendly default; why a slice usually wins.
- stacks & queues — built on lists (or slices) with a discipline.
- two pointers — the fast/slow technique behind cycle detection.
- Big-O — the O(1)-splice vs O(n)-access trade in context.
Next: two lists with a discipline — stacks & queues.
Related topics
A Go slice is a view over a backing array — how the (ptr, len, cap) header, append, growth, copy and re-slicing actually behave, and the aliasing traps.
linearStacks & QueuesLIFO and FIFO with O(1) push and pop — a stack on a Go slice, the balanced-brackets classic, and the head-index trick that keeps a queue's dequeue cheap.
complexityBig-O & ComplexityMeasure cost before you optimize — Big-O for time and space, the common growth classes, and how to read the complexity of real Go code.
Check your understanding
Score: 0 / 51. What is the cost of accessing the i-th element of a singly linked list?
Nodes are scattered in memory and reachable only through Next links, so there's no random access — finding index i means walking i hops from the head.
2. What does a linked list do in O(1) that a slice can't?
Splicing a node in or out is just a couple of pointer rewrites. A slice insert/delete in the middle must shift everything after it — O(n). (But a slice usually wins overall thanks to cache locality.)
3. In the standard reversal loop, why save `next := head.Next` before rewiring?
Reversal walks the list flipping each Next to point backward. Once you overwrite head.Next, the forward link is gone — so you stash next first, then advance to it.
4. How do you detect a cycle in a linked list in O(1) extra space?
Two pointers advance at different speeds; in a cycle the fast one laps the slow one and they collide, in O(n) time and O(1) space. A visited-set also works but costs O(n) space. The same fast/slow trick finds the list's middle in one pass.
5. What does a doubly linked list's Prev pointer buy you over a singly linked one?
To delete a node in a singly linked list you need its predecessor (an O(n) search, unless you tracked it). A Prev pointer makes that O(1) and lets you iterate in reverse — which is exactly why container/list (and LRU caches) use a doubly linked list.
Comments
Sign in with GitHub to join the discussion.