The linked list trap
You are building a buffer for a high-throughput logger. Messages arrive at irregular intervals. You need to append new entries and occasionally drop the oldest ones. A slice feels natural. You append. You slice off the front. It works. Then you profile the code. The garbage collector is running constantly. The slice is growing and shrinking. You recall the linked list from a computer science class. Constant time insertion. Constant time deletion. No shifting elements. No reallocation. You decide to implement one.
This is a common path. Linked lists solve a specific problem: efficient mutation in the middle of a sequence. They also introduce overhead that often outweighs the benefits in Go. Understanding how to build one reveals how Go manages memory, pointers, and performance. It also shows why the standard library rarely needs a custom linked list.
What a linked list actually is
A linked list is a chain of nodes. Each node holds a value and a reference to the next node. The list starts with a head pointer. The last node points to nil. To find the third element, you follow the chain from the head. You cannot jump to index 2. You must walk.
Think of a treasure hunt. Each clue tells you where to find the next clue. You cannot skip to the final clue without visiting the previous ones. The data is not stored in a contiguous block. It is scattered wherever the allocator placed it. This scattering has consequences for performance, which we will cover later.
Minimal implementation
Here is the simplest linked list. A node struct with a value and a next pointer. Methods to append and traverse.
package main
import "fmt"
// Node stores a value and a pointer to the next node.
type Node struct {
Value int
Next *Node
}
// Append walks to the end and attaches a new node.
func (n *Node) Append(value int) {
curr := n
// Walk until we hit the last node where Next is nil.
for curr.Next != nil {
curr = curr.Next
}
// Link the new node to the end.
curr.Next = &Node{Value: value}
}
func main() {
head := &Node{Value: 1}
head.Append(2)
head.Append(3)
// Verify the chain.
fmt.Println(head.Value, head.Next.Value, head.Next.Next.Value)
}
The Node struct defines the building block. Value holds the data. Next holds a pointer to the next node. The Append method walks the chain until it finds a node where Next is nil. It then creates a new node and links it. The main function creates a head node and appends two more. The output shows the values in order.
Notice the receiver. (n *Node) uses a pointer receiver. This is required because Append modifies the list structure. If you used a value receiver (n Node), the method would operate on a copy of the node. The original list would remain unchanged. The compiler allows value receivers on structs, so you won't get an error. You will get a silent bug where the list never grows. Always use a pointer receiver when the method mutates the receiver or its reachable state.
Convention aside: Receiver names should be short. (n *Node) matches the type name. (this *Node) or (self *Node) are common in other languages but violate Go style. The community expects one or two letters. Trust gofmt for formatting, but the receiver name is your choice. Pick something short and consistent.
Pointers are just addresses. The garbage collector does the heavy lifting.
Memory and performance reality
Linked lists have O(1) insertion complexity. That sounds great. Complexity theory ignores constant factors. In Go, those constants matter.
In a slice, elements sit side by side in memory. The CPU can prefetch the next chunk of data. Accessing sequential elements is fast because they likely reside in the CPU cache. In a linked list, nodes are scattered. Each node lives wherever the allocator put it. Following a pointer requires a memory lookup. If the next node is in a different cache line, the CPU stalls. This is called a cache miss. Pointer chasing kills performance on modern hardware.
Allocation overhead adds up. &Node{Value: value} allocates a new object. If the pointer escapes the function scope, the compiler places it on the heap. A list of 1000 elements requires 1000 allocations. A slice of 1000 elements requires one allocation. The allocator is fast, but it is not free. The garbage collector must track every node. More objects mean more work for the GC.
Slices often outperform linked lists even for insertions because the data fits in cache and the allocation cost is amortized. The linked list wins only when you need frequent mutations at arbitrary positions and you already hold a pointer to the target node. Even then, the cache penalty can dominate.
Realistic pattern: a queue
A common use case for linked lists is a queue. You need fast enqueue and dequeue operations. A naive linked list walks to the end for every enqueue. That makes enqueue O(N). You need to track the tail to achieve O(1).
Here is a queue struct that tracks both ends.
package main
// Queue holds head and tail pointers for O(1) operations.
type Queue struct {
head *Node
tail *Node
}
// Enqueue adds a value to the tail.
func (q *Queue) Enqueue(value int) {
newNode := &Node{Value: value}
if q.tail == nil {
// List is empty. Set both head and tail.
q.head = newNode
q.tail = newNode
return
}
// Link the new node after the current tail.
q.tail.Next = newNode
// Update tail pointer to the new node.
q.tail = newNode
}
The Queue struct holds both head and tail. Enqueue adds to the tail in O(1). It updates the tail pointer. If the list is empty, it sets both pointers. This avoids walking the list.
Dequeue removes from the head.
// Dequeue removes from the head and returns the value.
func (q *Queue) Dequeue() (int, bool) {
if q.head == nil {
// Return false if the queue is empty.
return 0, false
}
value := q.head.Value
// Advance head to the next node.
q.head = q.head.Next
if q.head == nil {
// List is now empty. Reset tail.
q.tail = nil
}
return value, true
}
Dequeue removes from the head in O(1). It advances the head pointer. If the list becomes empty, it resets tail to nil. This maintains the invariant that tail points to the last node or nil. The old head node becomes unreachable. The garbage collector reclaims it.
Track head and tail. Walking the list every time defeats the purpose.
Generics and type safety
Go 1.18 introduced generics. You can make the linked list work with any type. This avoids type assertions and makes the code reusable.
package main
// Node[T] stores a value of type T and a pointer to the next node.
type Node[T any] struct {
Value T
Next *Node[T]
}
// Append adds a value to the end of the list.
func (n *Node[T]) Append(value T) {
curr := n
for curr.Next != nil {
curr = curr.Next
}
curr.Next = &Node[T]{Value: value}
}
The Node[T] struct uses a type parameter. Value has type T. Next points to *Node[T]. The Append method accepts a value of type T. This keeps the list type-safe. You cannot append a string to a list of integers. The compiler enforces the type at compile time.
Generics add flexibility, but they do not change the performance characteristics. The cache misses and allocation overhead remain. The standard library's container/list is already generic. You rarely need to write your own generic linked list.
Pitfalls and errors
Linked lists are prone to subtle bugs. The compiler cannot catch all of them.
The most common error is dereferencing a nil pointer. If you access head.Next.Value without checking head.Next, the program crashes with panic: runtime error: invalid memory address or nil pointer dereference. Always check for nil before following a pointer. A traversal loop should test curr != nil before accessing fields.
Another trap is the infinite loop. If you accidentally set curr.Next = curr, the list cycles. A traversal loop never terminates. The compiler cannot detect cycles. You must ensure your logic breaks the chain correctly. A cycle does not leak memory in Go. The garbage collector handles cycles by tracing references. The memory is reclaimed when the cycle becomes unreachable. This differs from languages with manual memory management where a cycle causes a leak.
Value receiver bugs are silent. If you define func (n Node) Append(value int), the method compiles. It modifies a copy of the node. The caller sees no change. The compiler does not warn. You must review the receiver type carefully. Pointer receivers are the norm for methods that mutate state.
A nil pointer panic is a logic error. Check your bounds before you dereference.
Decision matrix
You rarely need a custom linked list in Go. The standard library provides container/list. It implements a doubly-linked list. It supports forward and backward traversal. It has methods for moving elements. It is generic and well-tested. If you need a linked list, use container/list. Writing your own is a good exercise, but production code should reuse the standard library.
Use a slice when you need random access by index. Use a slice when you append frequently and don't delete from the middle. Use a slice when performance matters and data fits in cache. Use a linked list when you need O(1) insertion or deletion at arbitrary positions and you already hold a pointer to the target node. Use container/list when you need a doubly-linked list with move operations. Use a slice when you are unsure. Slices are the default choice in Go. Linked lists are a niche tool for specific mutation patterns.
Slices win on cache. Linked lists win on mutation. Pick the tool, not the nostalgia.