A singly linked list is one pointer per element and nothing else. Most courses teach it early and almost no production Go program chooses it, and the reason for that gap is not in the complexity table. It is in what one dependent load after another does to hardware built to fetch ahead.
One value, one pointer, and a nil at the end
A node holds a value and the address of the next node. The last node’s next pointer is nil. The list itself is a single pointer to the first node, so an empty list is a nil pointer and no allocation at all.
The invariant that makes it a list rather than something else is that the chain from the head reaches every node exactly once and ends. Allow a node’s next pointer to point back at an earlier node and the chain never terminates, which turns every traversal into an infinite loop and makes the length undefined. Allow two nodes to point at the same successor and two chains share a tail. Unlinking a node through one of them changes the other, and the length each has cached stops matching what either can reach. Those two failures are most of the correctness surface, and neither shows up in a debugger print of any single node, which is why the tests further down start with a reachability check rather than a comparison of contents.
What follows from one pointer per node is the operation set. Reaching element k means following k pointers, because there is no arithmetic that gets you from the address of the first node to the address of the fifth. Adding or removing at the front is a pointer write and a head assignment. Adding or removing after a node whose address you already hold is two pointer writes and touches no other node. The nodes before it and after it stay exactly where they are in memory, at exactly the addresses anything else is holding. Adding at the back means walking the whole list first, unless you keep a tail pointer. Removing the last node means walking it regardless: you need the node in front of the victim, and a singly linked node has no way to name its predecessor.
The sentinel is a design choice, not part of the structure. A list with a dummy first node never has a nil head, so insertion and removal need no special case for position zero; it carries one node that holds no value and one extra dereference on every operation. The implementation below goes without one, which is why PushFront and RemoveAfter end up as different methods doing a similar job.
What the pointer chase costs
Traversal is O(n) and indexing is O(n), front insertion and removal are O(1), splicing after a known node is O(1), and appending at the back is O(n) without a tail pointer and O(1) with one. The complexity table is the easy half, and on modern hardware it is not the half that decides anything.
The half that does is the dependent load. Each n = n.Next is a load whose address came out of the previous load. The processor cannot start the second load until the first has returned a value, so a traversal of a thousand nodes is a thousand serialised round trips to wherever those nodes happen to live. Walking a slice is the opposite shape. The address of element i+1 is the address of element i plus a constant fixed at compile time, so the hardware issues those loads ahead of the loop and the data arrives before the loop asks for it. A cache line on common hardware holds 64 bytes, which is eight 64-bit integers, so a slice of integers brings seven more elements along with every miss. A list of the same integers brings one node per miss, and that node is two words of which one is the pointer you needed to find the next one.
That is why a slice beats a list at insertion in the middle far further up the length curve than the complexity bound suggests: the shift is a block memory move the hardware is built for, and the list’s constant-time splice still has to get to the position, one dependent load at a time. Do not take a factor from me for that, because it depends on your element size, your list’s allocation history and your machine. Run the benchmark further down on the hardware you deploy to and read your own number.
Space overhead is one pointer per element, eight bytes on a 64-bit build, plus whatever the allocator rounds each node up to and whatever bookkeeping it keeps per object. On a 64-bit build a Node[bool] measures sixteen bytes for one byte of value, once the pointer and the padding behind the bool are counted; a Node wrapping a 200-byte struct measures 208. Element size is the first thing to check when someone tells you a list is wasteful.
Allocation is the cost that is specific to Go. &Node[T]{...} inside a method that stores the address in the list escapes to the heap, because the compiler cannot prove the pointer stops being reachable when the call returns. That is not a quirk to work around; it is correct, and it is what makes the node’s address stable. Escape analysis rules are an implementation choice rather than a language guarantee, and go build -gcflags=-m prints the decision the compiler actually made, which is the only honest way to know. What is reliable is the shape. A list of n elements built one node at a time is n allocations. The equivalent slice built with make([]T, 0, n) is one, or none on a run where the compiler keeps the array on the stack. Allocation count shows up in -benchmem as allocs/op, it does not move with the clock speed of the machine, and it is the number to compare.
The garbage collector also walks every node. A pointer field has to be scanned, so a long-lived list of a million nodes gives the collector a million objects to trace, each one a dependent load for the collector too. A slice of a million pointer-free structs is one object with no pointers in it, and the collector skips the contents entirely.
Where the splice is worth it
Reach for a linked list when something outside the structure holds a reference to an element and that reference has to stay valid while the collection changes.
The clearest version is the intrusive list, where the link field lives inside an object that already exists for its own reasons. An idle-connection pool is the standard example. A connection is a real object with a socket and a deadline, several parts of the program hold a pointer to it, and the pool needs it on a list of idle connections and off again. Give the connection a next field and the pool is a head pointer. No node is allocated, because the node is the connection; nothing is copied when the connection moves between lists, because only two pointers change; and every pointer anyone else is holding stays correct, because the object never moves. Try the same thing with a slice of connections and either you store pointers, which reintroduces the per-object allocation you were trying to avoid, or you store values and every append invalidates every &pool[i] anybody kept.
A free list is the same mechanism turned inwards. When a structure recycles fixed-size objects, the objects not currently in use can be chained together through a field they already have, and allocation becomes “take the head, advance the head” with no allocator call at all. The chain lives in memory the free objects were occupying anyway, so the bookkeeping needs no storage of its own, and the structure is a singly linked list because nothing ever needs to walk it backwards.
The third case is a queue of work where producers only ever add at one end and a consumer only ever takes from the other. A list does that in constant time at both ends with a head and a tail pointer, never reallocates, and never drags a backing array behind it. The slice-based alternative needs a ring buffer, because popping with q = q[1:] walks the data pointer forward and leaves the elements behind it allocated and unreachable, so a long-running queue holds the whole array alive. A ring buffer is a better answer than a list for a bounded queue; the list wins where the queue has no bound and the arrival pattern is bursty, since it grows one node at a time rather than doubling.
Then there is the case where a list is not the data structure but the shape of the data. A chain of handlers is one. So is a parsed cons list, and so is a stack of lexical scopes where each inner scope points at the one enclosing it. So is an immutable list shared between versions, where pushing onto the front of a shared tail changes nothing for whoever is holding that tail. All of them are singly linked lists because the domain is a chain. Reaching for a slice there means reconstructing the chain from indices, which is more code and no faster.
When a slice wins, which is most of the time
Use a slice whenever you walk the collection start to finish, index by position, or append at the end. That is the overwhelming majority of collections in any program, and the slice header is three words over a contiguous array precisely so that those three operations are a pointer add, a bounds check and an amortised write. A list is worse at all three. The standard library is written for slices too: slices.Sort, slices.BinarySearch, slices.Index, slices.Reverse, slices.Compact and slices.Collect all exist for slices and not for your list type, so choosing a list means writing and testing the equivalents yourself.
Use a map when you look elements up by key. A list search is a linear walk with a dependent load per step, which is the worst possible shape for a lookup. The one map behaviour to carry with you: iteration order is unspecified and the runtime deliberately randomises it, so code that ranges over a map and expects stable output is broken whether or not it has failed yet. Where the output order matters, collect the keys into a slice, sort it, and iterate that.
Do not reach for container/list. It is a doubly linked list whose Element.Value field is declared as any. Every element you store goes through an interface value, and small values get boxed on the way in. You type-assert on the way out, with no compile-time check that the assertion matches. Generics removed the reason that package was written the way it was, and a thirty-line generic node type gives you type safety, no boxing and a smaller node. The same caution applies to container/heap, whose interface also predates generics: the algorithm in it is correct and worth using, and using it means implementing five methods on your own type and accepting any at the element boundary.
The replacement that deserves more attention than it gets is a slice of nodes linked by integer indices. Keep the values in one slice and the next-links in a parallel slice of int32, and a “pointer” becomes an index. The whole structure is then two allocations instead of one per node, and the links are half the width of a pointer on a 64-bit build. The collector has nothing to scan at all when the value type carries no pointers of its own, because neither slice holds any. And an index survives the arena growing, where &a.value[i] would be left pointing at the abandoned backing array.
Traversal is still a dependent load, so this is not a cure for the chase; the nodes are just far more likely to be near each other, and the per-node allocation and collection work is gone. What you give up is what a stale link means. Go bounds-checks every index, so a stale index past the end of the arena panics, but one still inside it names whatever now occupies that slot and the traversal carries on with a plausible wrong value. A stale pointer at least still names the node it always named, and keeps that node alive while anyone holds it. The arena version wins often enough that it is worth writing before the pointer version.
The last reason to avoid a list is the one that does not appear in any analysis: it is harder to get right. Every operation is a pointer manipulation with an off-by-one neighbour, the failure modes are a cycle and a leak rather than a wrong value, and a bug produces a hang or a corrupted traversal instead of a failed assertion.
Writing it in Go
The type is two structs and the invariant is the comment on the second one.
// Package listkit is a singly linked list written out so the pointer
// manipulation is visible. Prefer a slice unless something outside the
// structure holds a node address that has to survive mutation.
package listkit
import (
"errors"
"fmt"
"iter"
)
// Node is exported because callers hold node addresses: that stability is the
// reason to use this structure rather than a slice.
type Node[T any] struct {
Next *Node[T]
Value T
}
// List holds the head of the chain and a cached length. The invariant, which
// check() verifies and every test below calls: following Next from head
// reaches exactly n nodes and then nil, and reaches no node twice.
type List[T any] struct {
head *Node[T]
n int
}
func (l *List[T]) Len() int { return l.n }
// PushFront links v in at the head and returns the node, so the caller can
// splice after it later without walking.
func (l *List[T]) PushFront(v T) *Node[T] {
nd := &Node[T]{Next: l.head, Value: v}
l.head = nd
l.n++
return nd
}
func (l *List[T]) PopFront() (T, bool) {
var zero T
if l.head == nil {
return zero, false
}
nd := l.head
l.head = nd.Next
nd.Next = nil // so a caller still holding nd cannot walk the live list
l.n--
return nd.Value, true
}
InsertAfter and RemoveAfter are the two operations the structure exists for. Neither walks, neither moves another element, and neither invalidates an address anybody is holding.
// InsertAfter splices a new node in after at. Two pointer writes, no
// traversal, and every other node keeps its address.
func (l *List[T]) InsertAfter(at *Node[T], v T) *Node[T] {
nd := &Node[T]{Next: at.Next, Value: v}
at.Next = nd
l.n++
return nd
}
// RemoveAfter unlinks at.Next and returns it, or nil when at is the last
// node. It is RemoveAfter rather than Remove because a singly linked node
// cannot name its predecessor, so removing a given node means finding the one
// in front of it, which is a walk. That asymmetry is the structure, not an
// omission in this API.
func (l *List[T]) RemoveAfter(at *Node[T]) *Node[T] {
victim := at.Next
if victim == nil {
return nil
}
at.Next = victim.Next
victim.Next = nil
l.n--
return victim
}
// All yields the values from head to tail. Returning iter.Seq means
// slices.Collect, slices.Sorted and a plain range loop all work on it.
func (l *List[T]) All() iter.Seq[T] {
return func(yield func(T) bool) {
for nd := l.head; nd != nil; nd = nd.Next {
if !yield(nd.Value) {
return
}
}
}
}
Reversal in place is three pointers and one pass. It is worth writing out because it is the operation a list does better than a slice of pointers would: nothing is copied, nothing is allocated, and every node keeps its address while the order changes completely.
// Reverse reverses the chain in place in one pass. prev trails cur, next is
// held because cur.Next is about to be overwritten.
func (l *List[T]) Reverse() {
var prev *Node[T]
cur := l.head
for cur != nil {
next := cur.Next
cur.Next = prev
prev = cur
cur = next
}
l.head = prev
}
The cycle check is Floyd’s two-pointer walk: one pointer advances one node per step, the other two. If the chain ends, the fast pointer reaches nil. If it loops, the fast pointer gains one node per step on the slow one inside the loop and must eventually land on it. It needs no extra memory, so the invariant checker can call it after every mutation without building a set of visited addresses each time.
// HasCycle reports whether the chain from head revisits a node. Floyd's
// algorithm: constant space, and at most a linear number of steps.
func HasCycle[T any](head *Node[T]) bool {
slow, fast := head, head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
if slow == fast {
return true
}
}
return false
}
// check verifies the invariant. Cycle first, because the node count below
// would not terminate otherwise.
func (l *List[T]) check() error {
if HasCycle(l.head) {
return errors.New("chain from head revisits a node")
}
reachable := 0
for nd := l.head; nd != nil; nd = nd.Next {
reachable++
}
if reachable != l.n {
return fmt.Errorf("cached length %d, %d nodes reachable", l.n, reachable)
}
return nil
}
Two Go-specific traps in this code. Every method takes a pointer receiver, and the code does not work without it. A value receiver gets a copy of the List struct. PushFront on one would allocate the node, link it to the right successor, then assign the new head to a struct that goes out of scope on return. The element is lost and the caller’s n never moves. It compiles and it does nothing. And nd.Next = nil in PopFront and RemoveAfter is not tidiness. A caller holding the removed node could otherwise walk from it into the live list, and the collector could not free the tail while that one node was alive.
The arena version is the same structure with indices instead of pointers.
// Arena keeps every node's value in one slice and every next-link in a
// parallel slice of int32. Two allocations for the whole structure, half the
// link width of a pointer build, and nothing for the collector to scan when T
// contains no pointers of its own.
type Arena[T any] struct {
value []T
next []int32
head int32
}
const nilIndex int32 = -1
func NewArena[T any](capacity int) *Arena[T] {
return &Arena[T]{
value: make([]T, 0, capacity),
next: make([]int32, 0, capacity),
head: nilIndex,
}
}
// PushFront appends the node and links it in at the head. An index returned
// here stays valid when the arena's slices grow; &a.value[i] would not.
func (a *Arena[T]) PushFront(v T) int32 {
a.value = append(a.value, v)
a.next = append(a.next, a.head)
a.head = int32(len(a.value) - 1)
return a.head
}
func (a *Arena[T]) InsertAfter(at int32, v T) int32 {
a.value = append(a.value, v)
a.next = append(a.next, a.next[at])
i := int32(len(a.value) - 1)
a.next[at] = i
return i
}
func (a *Arena[T]) All() iter.Seq[T] {
return func(yield func(T) bool) {
for i := a.head; i != nilIndex; i = a.next[i] {
if !yield(a.value[i]) {
return
}
}
}
}
Removal in an arena needs a free list of its own, chaining the dead slots through the same next slice, which is the free-list pattern applied to the structure’s own storage. The rest of the implementation is mechanical once those four methods are in place.
How to test it
The invariant checker comes first, and every other test calls it. The two failures that matter here are a cycle and a length that has drifted from reality, and neither shows up in a comparison of contents. Everything below lives in listkit_test.go in the same package, so it can reach the unexported check and head.
package listkit
import (
"math/rand/v2"
"slices"
"sync"
"testing"
)
// fromSlice builds a list in order and returns the node addresses, so a test
// can splice at a named position without walking.
func fromSlice[T any](vs []T) (*List[T], []*Node[T]) {
l := &List[T]{}
nodes := make([]*Node[T], len(vs))
var prev *Node[T]
for i, v := range vs {
if prev == nil {
prev = l.PushFront(v)
} else {
prev = l.InsertAfter(prev, v)
}
nodes[i] = prev
}
return l, nodes
}
Table-driven tests cover the cases you can name. For a singly linked list those are the positions where the pointer manipulation differs: the head, the middle, the last node, and a single-element list where the head is also the last node.
func TestRemoveAfter(t *testing.T) {
tests := []struct {
name string
in []int
at int // index of the node to remove after
want []int
}{
{"middle", []int{1, 2, 3, 4}, 1, []int{1, 2, 4}},
{"after the head", []int{1, 2, 3}, 0, []int{1, 3}},
{"last node has no successor", []int{1, 2, 3}, 2, []int{1, 2, 3}},
{"single element", []int{1}, 0, []int{1}},
}
for _, tt := range tests {
t.Run(tt.name, func(t *testing.T) {
l, nodes := fromSlice(tt.in)
removed := l.RemoveAfter(nodes[tt.at])
if err := l.check(); err != nil {
t.Fatal(err)
}
if got := slices.Collect(l.All()); !slices.Equal(got, tt.want) {
t.Errorf("RemoveAfter(node %d) left %v, want %v", tt.at, got, tt.want)
}
if removed != nil && removed.Next != nil {
t.Error("the removed node still points into the live list")
}
})
}
}
A property test asserts a relationship over generated inputs rather than a value over a chosen one, and reversal has the obvious one: applied twice it is the identity. It catches the classic reversal bug, which is losing the tail by overwriting cur.Next before reading it, on the first input longer than two elements.
func TestReverseTwiceIsIdentity(t *testing.T) {
rng := rand.New(rand.NewPCG(7, 11)) // fixed seed, so a failure replays
for range 2000 {
want := randomInts(rng, rng.IntN(24))
l, _ := fromSlice(want)
l.Reverse()
l.Reverse()
if err := l.check(); err != nil {
t.Fatal(err)
}
if got := slices.Collect(l.All()); !slices.Equal(got, want) {
t.Fatalf("reverse twice changed the list: %v became %v", want, got)
}
if l.Len() != len(want) {
t.Fatalf("length %d after two reversals, want %d", l.Len(), len(want))
}
}
}
func randomInts(rng *rand.Rand, n int) []int {
out := make([]int, n)
for i := range out {
out[i] = rng.IntN(100)
}
return out
}
The test that finds the most is a randomised comparison against a reference, and for a list the reference is a slice. Generate an operation sequence, apply each operation to both, and compare after every one. The slice version is correct by inspection and allocates far too much to ship, which is what makes it the reference.
func TestMatchesSliceReference(t *testing.T) {
rng := rand.New(rand.NewPCG(3, 5))
for range 500 {
var l List[int]
var ref []int
for range rng.IntN(40) {
switch rng.IntN(4) {
case 0:
v := rng.IntN(100)
l.PushFront(v)
ref = append([]int{v}, ref...)
case 1:
got, ok := l.PopFront()
if ok != (len(ref) > 0) {
t.Fatalf("PopFront ok = %v with %d reference elements", ok, len(ref))
}
if ok {
if got != ref[0] {
t.Fatalf("PopFront = %d, want %d", got, ref[0])
}
ref = ref[1:]
}
case 2:
l.Reverse()
slices.Reverse(ref)
case 3:
if len(ref) == 0 {
continue
}
i := rng.IntN(len(ref))
at := l.head
for range i {
at = at.Next
}
v := rng.IntN(100)
l.InsertAfter(at, v)
ref = slices.Insert(ref, i+1, v)
}
if err := l.check(); err != nil {
t.Fatal(err)
}
if got := slices.Collect(l.All()); !slices.Equal(got, ref) {
t.Fatalf("list %v, reference %v", got, ref)
}
}
}
}
Two things about that test are deliberate. slices.Reverse and slices.Insert do the reference’s work, so the reference is three lines rather than thirty and there is no chance of the same bug appearing in both implementations. And check runs after every single operation rather than at the end, so a failure names the operation that broke the invariant instead of the one that happened to notice.
A fuzz target pushes the same idea further by letting the fuzzing engine choose the sequence, and it reaches orderings a uniform generator will not. The input bytes are the program: one byte selects the operation, the next is the value.
func FuzzOperationSequence(f *testing.F) {
f.Add([]byte{0, 1, 0, 2, 2, 0, 0, 3, 1, 0})
f.Fuzz(func(t *testing.T, ops []byte) {
var l List[byte]
var ref []byte
for i := 0; i+1 < len(ops); i += 2 {
switch ops[i] % 3 {
case 0:
l.PushFront(ops[i+1])
ref = append([]byte{ops[i+1]}, ref...)
case 1:
if _, ok := l.PopFront(); ok {
ref = ref[1:]
}
case 2:
l.Reverse()
slices.Reverse(ref)
}
if err := l.check(); err != nil {
t.Fatalf("after op %d: %v", i/2, err)
}
if got := slices.Collect(l.All()); !slices.Equal(got, ref) {
t.Fatalf("after op %d: list %v, reference %v", i/2, got, ref)
}
}
})
}
Where a claim is about cost, the test is a benchmark, and the result is a measurement on one machine rather than a fact about Go. Build a list and a slice of the same length, sum both, and read the ratio on the hardware you deploy to. The allocation columns are more durable than the time columns, because allocs/op is a property of the code and nanoseconds are a property of the machine.
var sink int
func BenchmarkSum(b *testing.B) {
const n = 1 << 16
flat := make([]int, n)
for i := range flat {
flat[i] = i
}
l, _ := fromSlice(flat)
b.Run("slice", func(b *testing.B) {
for range b.N {
total := 0
for _, v := range flat {
total += v
}
sink = total
}
})
b.Run("list", func(b *testing.B) {
for range b.N {
total := 0
for nd := l.head; nd != nil; nd = nd.Next {
total += nd.Value
}
sink = total
}
})
}
func BenchmarkBuild(b *testing.B) {
const n = 4096
b.Run("slice", func(b *testing.B) {
b.ReportAllocs()
for range b.N {
s := make([]int, 0, n)
for i := range n {
s = append(s, i)
}
sink = len(s)
}
})
b.Run("list", func(b *testing.B) {
b.ReportAllocs()
for range b.N {
var l List[int]
for i := range n {
l.PushFront(i)
}
sink = l.Len()
}
})
}
BenchmarkSum builds its list once, outside the timed loop, which means the nodes were allocated consecutively and are about as well laid out as a list ever gets. A list that has been built and torn down over hours has its nodes scattered across the heap and traverses worse, so this benchmark reports the list’s best case. If it already loses, the real case loses by more.
The list has no internal synchronisation, so the last test pins down which concurrent uses are safe. Concurrent traversal of a list nobody is mutating is safe, because following Next is a read. Concurrent PushFront writes l.head and l.n from several goroutines and is a data race even when no two goroutines touch the same node, and go test -race reports it with both stacks.
func TestConcurrentTraversalIsSafe(t *testing.T) {
l, _ := fromSlice([]int{1, 2, 3, 4, 5, 6, 7, 8})
var wg sync.WaitGroup
for range 8 {
wg.Add(1)
go func() {
defer wg.Done()
total := 0
for nd := l.head; nd != nil; nd = nd.Next {
total += nd.Value
}
if total != 36 {
t.Errorf("traversal summed to %d, want 36", total)
}
}()
}
wg.Wait()
}
Run that under -race and it is clean. Replace the traversal with l.PushFront(1) and it still passes under a plain go test most of the time. That is the shape of every linked-list bug worth worrying about: a pointer write that is wrong only sometimes, in a structure whose invariant nothing checks unless you write the checker.