A doubly linked list adds one pointer per node and gets one operation in return: given a node, unlink it in constant time. A singly linked list cannot do that at all, because a node has no way to name whatever points at it, so removing a node means finding its predecessor and finding its predecessor means walking from the head. Everything else about the structure follows from that one operation, including the reason its commonest real use is not a list of values but a handle that a map gives out.
A ring with one node that holds nothing
Each node holds a value, the address of the next node and the address of the previous one. The invariant that makes it a doubly linked list rather than two unrelated chains is that the two directions agree: for every node n in the structure, n.next.prev == n and n.prev.next == n. Break one of those and a forward walk and a backward walk return different sequences, with nothing in a debugger print of a single node to say which of the two directions is the broken one. That is why the test section below opens with a checker that walks both ways and compares.
The textbook version keeps a head pointer and a tail pointer and terminates both ends with nil. It works, and it is the reason the operations read so badly. Inserting a node is four cases: into an empty list, before the current head, after the current tail, and in the middle, each with its own nil test and its own head or tail assignment. Removal is the same four. Most of the code is end cases, the end cases are where the bugs are, and the end cases are the part nobody covers in the tests because they are tedious to set up.
The circular list with a single sentinel deletes all of them. Add one node that holds no value, call it the root, and close the chain through it. The root’s next is the first element and the root’s prev is the last. An empty list is a root whose next and prev both point at the root itself. No pointer in the structure is ever nil, and there is no head pointer and no tail pointer, because the root is both. The end of the list is a node you can recognise rather than a nil: the iterator stops when the next node is the root.
What that leaves is one insertion routine and one removal routine with no branches in either. Linking a new node in after some node at is four writes, every one unconditional, because at is never nil and at.next is never nil even when at is the root of an empty list. Pushing at the front is that routine with at set to the root; pushing at the back is the same routine with at set to root.prev. Unlinking is two writes, nd.prev.next = nd.next and nd.next.prev = nd.prev. They are correct for the first node, the last node and the only node without a test: in each of those cases the neighbour being patched is the root, and patching the root is exactly right. One extra node that never holds a value removes every special case in the implementation.
Two pointers per node, and a dependent load per step
Insertion next to a held node, removal of a held node, pushing and popping at either end, and moving a node are all constant time. Indexing is O(n) and searching is O(n), the same as the singly linked list, because the extra pointer adds no way to reach position k without visiting k nodes. A backward walk of the whole list is O(n) rather than the O(n²) it would be on a singly linked list. That is the other thing the prev pointer gives: iterating from the back, not just reaching it.
Space is two pointers per element, sixteen bytes on a 64-bit build. A third word goes on top if each node carries a reference to the list it belongs to, which is what lets removal reject a node that is not in this list. That is 24 bytes of bookkeeping around the value, before any alignment padding the compiler adds. For a list of bytes the overhead is more than twenty times the payload. For a list of 300-byte structs it rounds to nothing. Element size decides whether the overhead is an argument.
The running cost is the one the complexity table does not contain. Every nd = nd.next is a load whose address came out of the previous load, so the processor cannot begin the second until the first returns and a traversal is a chain of serialised round trips. A slice is the opposite shape, since the address of element i+1 is the address of element i plus a constant the compiler knows, and the hardware fetches ahead. Both of this structure’s pointers chase the same way. The backward walk of a list built front to back goes in the opposite order to the one the nodes were allocated in, which is about the least prefetcher-friendly order a walk can take. Do not take a ratio for that from me. Take the benchmark below, run it on the machine you deploy to, and read the number there.
Constant time for removal means a constant number of pointer writes, and the writes are not where the time goes. Unlinking a node touches three nodes, whatever the length of the list: two writes patch the neighbours, and clearing the removed node’s own links accounts for the rest. Reaching those two neighbours is two dereferences into wherever the allocator put them, and if neither is in cache that pair of misses dominates everything else the operation does. The operation is constant time and the constant is a cache miss.
Allocation is one object per node, because the node outlives the call that created it. The sentinel is the Go-specific part: embedding the root in the list struct by value means insert takes &l.root, so the list struct cannot stay on the stack once a node is linked into it. Escape analysis is an implementation choice rather than a language guarantee, and go build -gcflags=-m prints the decision the compiler made rather than the one you expected. What is reliable is the shape: n elements is n allocations, where the equivalent slice built with make([]T, 0, n) is one. allocs/op under -benchmem is a property of the code, and it does not move when you change machines.
The collector has more to do here than with a singly linked list. A node with three pointer fields is three slots the collector traces, and it traces them one dependent load at a time, so a long-lived list of a million nodes is a million objects to scan. A slice of a million pointer-free structs is one object the collector looks at once.
When the handle is the thing you hold
Reach for a doubly linked list when something outside the list holds a position in it, and that position has to be removable or movable without a search.
The LRU cache is the canonical case and it is worth walking through, because the structure is chosen by elimination. A cache needs three operations in constant time: find an entry by key, mark an entry as most recently used, and evict the least recently used. A map does the first and holds no order at all. A slice does the ordering and makes the mark-as-used step a shift of everything between the old position and the end. The combination that works is a map from key to node, plus a doubly linked list holding the entries in use order with the most recent at the front. A hit is a map lookup followed by a move of that node to the front, and the move is the operation that needs the prev pointer. Without it, relinking the node means finding what precedes it, which is the walk the cache was built to avoid. Eviction is the node at the back, which the root’s prev names directly.
The map in that design finds nodes and carries none of the ordering, and it cannot be made to. Go’s map iteration order is unspecified and the runtime randomises it deliberately, so any attempt to read a least-recently-used entry by ranging the map is broken whether or not it has produced a wrong answer yet. The list holds the order; the map holds the index into it.
The second case is an object that moves between lists over its life, which is most of what a scheduler or a connection pool does. A connection is idle, then active, then idle again, and each move is a removal from one list and an insertion into another, with no traversal at either end. Several parts of the program hold the address of that connection throughout, and every one of those addresses stays correct for the object’s whole life, because a node never moves in memory once it is allocated. The slice version has to store pointers, which puts back the per-object allocation, or store values, in which case every append invalidates every &pool[i] anyone kept.
The third case is a cursor. Where a program sits at a position in a sequence and moves either way from it, the operation set is exactly next and prev. That is a playlist, a browser history, or a sequence of editing operations with an undo position in the middle of it. Insertion at the cursor is constant time and the positions either side of it keep their addresses, so a bookmark into the sequence survives the edit.
When a slice or a ring buffer is better
Use a slice whenever the access pattern is walking from one end, indexing by position, or appending at the back. That covers the large majority of collections in any program. The reasons are in the amortised growth argument and in the cache behaviour above, and there is a third: the standard library ships slices.Sort, slices.BinarySearch, slices.Index, slices.Compact and the rest for slices, and nothing equivalent for your node type. Choosing a list means writing and testing the replacements.
The alternative that actually competes is the ring buffer, and it beats a doubly linked list at the job the list is most often chosen for. A deque needs constant-time push and pop at both ends, and a ring buffer over a single array gives that with contiguous storage, one allocation, no pointer per element and nothing for the collector to trace. Two indices and a modulo are the whole implementation. The list wins over it in one situation: when elements have to be removed from the middle, which a ring buffer cannot do without shifting. If every removal is at an end, the list is carrying two pointers per node for nothing.
For lookup by key, a map. For the smallest element, or a range of elements, or the successor of a value, an ordered structure: a sorted slice with slices.BinarySearch while the data is small or rarely written, a balanced tree when it is neither. A list has no way to find a position, so every ordered query over one degrades to a linear scan. For a priority queue, container/heap over a slice. It is a correct implementation of an algorithm worth not rewriting, it needs five methods on your own type, and it puts any at the element boundary, since that package predates generics too.
For a stack, or a free list of recycled objects, one pointer is enough and the singly linked version is smaller and simpler. And where the structure is a long-lived chain of small values, the index arena from the singly linked case still applies: keep values in one slice and the two links in parallel slices of int32. That halves the link width, collapses n allocations into three, and removes every pointer the collector would have had to scan. An index also survives the arena growing, where &a.value[i] does not, because append may move the backing array out from under a pointer taken before the call.
If nothing outside the structure is holding a node, nothing needs the prev pointer, and the structure should be something contiguous.
Why container/list disappoints
The standard library has a doubly linked list, and it is built the way described above. container/list is a circular list closed through a single root element, and its zero value is documented as an empty list ready to use. It provides PushFront, PushBack, InsertBefore, InsertAfter, Remove, MoveToFront, MoveToBack, MoveBefore and MoveAfter, more of the operation set than most hand-rolled versions ever get around to implementing. It is correct, it is tested, and the awkward part is one field.
list.Element declares Value any. The package was written long before Go had type parameters. The Go 1 compatibility promise means that field cannot change type without breaking every program that reads it, so the list is a list of interface values and will stay one. Three consequences follow, and they are all qualitative because the Go specification does not define how an interface value is laid out.
Storing a value in an any requires the implementation to make that value referenceable. Putting an int or a struct into Element.Value generally copies it somewhere the interface can point at, which for most value types means an allocation per element on top of the node. A pointer-shaped value avoids the copy, since the implementation can hold the pointer directly, and current runtimes also special-case some small integers. Both of those are implementation behaviour that has changed before and could change again, so write a benchmark with -benchmem and read allocs/op for your element type rather than reasoning about it.
Reading an element back needs a type assertion, e.Value.(int), which checks a type descriptor at run time on every read. Between the write and that check there is no concrete type for the compiler to work with, so nothing the code does with the element can be specialised to it. And the assertion’s failure mode moved from compile time to run time. Put a string into a list the rest of the program asserts to int, and the mistake is a panic in production rather than an error in the build.
A generic node type with the same ring and the same sentinel is about seventy lines. It stores T directly with no box and no assertion, the node is smaller, and slices.Collect works on an iter.Seq[T] method, so the standard library comes back. That is the argument for writing it, and it is not an argument for always writing it. container/list is the right call for a short list, and for a thirty-line tool rather than a hot path. It is also right when the elements are pointers or already interface values, so the box adds nothing. And it is right when a reviewer will recognise the standard-library type where they would have to read yours. The failing is narrow and specific: it puts an interface at the element boundary, and a measurement on your own element type is the only way to know whether that matters where you are using it.
Writing one in Go
The type is two structs, and the comment on the second one is the invariant.
// Package dlist is a generic doubly linked list built as a ring closed
// through a single sentinel, so no pointer in the structure is ever nil and
// no operation has an end case.
package dlist
import (
"fmt"
"iter"
)
// Node is exported because callers hold node addresses and remove by address,
// which is the reason to choose this structure over something contiguous.
type Node[T any] struct {
next, prev *Node[T]
list *List[T] // nil once the node has been removed
Value T
}
// Next returns the following node, or nil at the end of the list. The ring
// closes through the sentinel and callers never see it.
func (n *Node[T]) Next() *Node[T] {
if n.list == nil || n.next == &n.list.root {
return nil
}
return n.next
}
func (n *Node[T]) Prev() *Node[T] {
if n.list == nil || n.prev == &n.list.root {
return nil
}
return n.prev
}
// List is a ring of nodes closed through root, which holds no value. The
// invariants, which check() verifies and every test below calls: for every
// node in the ring, next.prev and prev.next are the node itself; the ring
// holds exactly n nodes besides root; and every node's list field is this
// list.
//
// Use it through a pointer and never copy it. Nodes hold the address of
// root, so a copy is a list whose nodes all link back into the original, and
// a method with a value receiver would get that copy.
type List[T any] struct {
root Node[T]
n int
}
// lazyInit closes the ring on first use, so a declared List works with no
// constructor. The alternative is an exported New that callers forget.
func (l *List[T]) lazyInit() {
if l.root.next == nil {
l.root.next = &l.root
l.root.prev = &l.root
}
}
func (l *List[T]) Len() int { return l.n }
insert and Remove are where the sentinel does its work, and the absence of branches in them is the thing to read.
// insert links nd in after at. Four writes, none of them conditional: at is
// never nil and at.next is never nil, even when at is the root of an empty
// list, so there is no empty case, no front case and no back case.
func (l *List[T]) insert(nd, at *Node[T]) *Node[T] {
nd.prev = at
nd.next = at.next
nd.prev.next = nd
nd.next.prev = nd
nd.list = l
l.n++
return nd
}
func (l *List[T]) PushFront(v T) *Node[T] {
l.lazyInit()
return l.insert(&Node[T]{Value: v}, &l.root)
}
func (l *List[T]) PushBack(v T) *Node[T] {
l.lazyInit()
return l.insert(&Node[T]{Value: v}, l.root.prev)
}
// InsertAfter returns nil when at belongs to another list, which is what the
// list field is for: without it, splicing a node into the wrong list corrupts
// both and reports nothing.
func (l *List[T]) InsertAfter(at *Node[T], v T) *Node[T] {
if at == nil || at.list != l {
return nil
}
return l.insert(&Node[T]{Value: v}, at)
}
// Remove unlinks nd and returns its value. Two writes into its neighbours and
// no traversal, wherever nd sits and however long the list is. Clearing nd's
// own pointers stops a caller still holding it from walking the live list and
// lets the collector free the rest of the ring if this was the last reference.
func (l *List[T]) Remove(nd *Node[T]) T {
if nd.list == l {
nd.prev.next = nd.next
nd.next.prev = nd.prev
nd.next = nil
nd.prev = nil
nd.list = nil
l.n--
}
return nd.Value
}
// MoveToFront relinks nd directly after root with no allocation. This is the
// operation an LRU cache runs on every hit, and the one that needs prev.
func (l *List[T]) MoveToFront(nd *Node[T]) {
if nd.list != l || l.root.next == nd {
return
}
nd.prev.next = nd.next
nd.next.prev = nd.prev
nd.prev = &l.root
nd.next = l.root.next
nd.prev.next = nd
nd.next.prev = nd
}
Both traversals are iterators, so slices.Collect, slices.Sorted and a plain range loop all work on them. The length test at the top of each is what holds them up. An uninitialised list has a nil root.next, and without the test the loop dereferences it.
func (l *List[T]) Front() *Node[T] {
if l.n == 0 {
return nil
}
return l.root.next
}
func (l *List[T]) Back() *Node[T] {
if l.n == 0 {
return nil
}
return l.root.prev
}
func (l *List[T]) All() iter.Seq[T] {
return func(yield func(T) bool) {
if l.n == 0 {
return
}
for nd := l.root.next; nd != &l.root; nd = nd.next {
if !yield(nd.Value) {
return
}
}
}
}
func (l *List[T]) Backward() iter.Seq[T] {
return func(yield func(T) bool) {
if l.n == 0 {
return
}
for nd := l.root.prev; nd != &l.root; nd = nd.prev {
if !yield(nd.Value) {
return
}
}
}
}
The checker is the part that makes the rest testable. It verifies both link directions at every node, compares the cached length against the ring, and then collects both walks and asserts one is the reverse of the other, which is the property a single-direction walk cannot see.
// check verifies the invariants. The length guards inside both loops are
// there because a broken ring does not terminate, and a test that hangs is
// worse than one that fails.
func (l *List[T]) check() error {
if l.n == 0 {
if l.root.next != nil && (l.root.next != &l.root || l.root.prev != &l.root) {
return fmt.Errorf("empty list does not close on itself")
}
return nil
}
forward := make([]*Node[T], 0, l.n)
for nd := l.root.next; nd != &l.root; nd = nd.next {
if len(forward) > l.n {
return fmt.Errorf("forward walk passed %d nodes without reaching root", l.n)
}
if nd.next.prev != nd {
return fmt.Errorf("node %v: next.prev is some other node", nd.Value)
}
if nd.prev.next != nd {
return fmt.Errorf("node %v: prev.next is some other node", nd.Value)
}
if nd.list != l {
return fmt.Errorf("node %v: list field names a different list", nd.Value)
}
forward = append(forward, nd)
}
if len(forward) != l.n {
return fmt.Errorf("cached length %d, %d nodes in the ring", l.n, len(forward))
}
backward := make([]*Node[T], 0, l.n)
for nd := l.root.prev; nd != &l.root; nd = nd.prev {
if len(backward) > l.n {
return fmt.Errorf("backward walk passed %d nodes without reaching root", l.n)
}
backward = append(backward, nd)
}
if len(backward) != len(forward) {
return fmt.Errorf("%d nodes forward, %d backward", len(forward), len(backward))
}
for i := range forward {
if forward[i] != backward[len(backward)-1-i] {
return fmt.Errorf("the two orders disagree at position %d", i)
}
}
return nil
}
The rest of the structure is mechanical from here: InsertBefore is insert(nd, at.prev), MoveToBack is MoveToFront with root.prev as the anchor, and splicing one list into another is a handful more pointer writes with the two lengths added.
An LRU cache on top of it is twenty lines. It leans on exactly the two properties a slice does not have: a node address that stays valid for the life of the entry, and a relink with no search.
type entry[K comparable, V any] struct {
key K
value V
}
// Cache holds use order in the list, most recent at the front, and uses the
// map only to find a node. The map cannot hold the order: Go randomises map
// iteration, so there is no least-recently-used end to read from it.
type Cache[K comparable, V any] struct {
capacity int
index map[K]*Node[entry[K, V]]
order List[entry[K, V]]
}
func NewCache[K comparable, V any](capacity int) *Cache[K, V] {
return &Cache[K, V]{
capacity: capacity,
index: make(map[K]*Node[entry[K, V]], capacity),
}
}
// Get mutates the list, so it is a write and needs a write lock when the
// cache is shared. An RWMutex read lock around this is a data race, and
// go test -race reports it with both stacks.
func (c *Cache[K, V]) Get(k K) (V, bool) {
nd, ok := c.index[k]
if !ok {
var zero V
return zero, false
}
c.order.MoveToFront(nd)
return nd.Value.value, true
}
func (c *Cache[K, V]) Put(k K, v V) {
if nd, ok := c.index[k]; ok {
nd.Value.value = v
c.order.MoveToFront(nd)
return
}
c.index[k] = c.order.PushFront(entry[K, V]{key: k, value: v})
if c.order.Len() > c.capacity {
oldest := c.order.Back()
delete(c.index, oldest.Value.key)
c.order.Remove(oldest)
}
}
How to test it
The invariant checker runs after every mutation in every test below. The failures that matter in this structure are a ring that no longer closes and two directions that no longer agree, and neither shows up in a comparison of contents. Everything here is in dlist_test.go in the same package, so it can reach check, root and the unexported link fields.
package dlist
import (
"container/list"
"math/rand/v2"
"slices"
"testing"
)
// fromSlice builds a list in order and returns the node addresses, so a test
// can remove at a named position without walking to it.
func fromSlice[T any](vs []T) (*List[T], []*Node[T]) {
l := &List[T]{}
nodes := make([]*Node[T], len(vs))
for i, v := range vs {
nodes[i] = l.PushBack(v)
}
return l, nodes
}
func collectBoth[T comparable](t *testing.T, l *List[T], want []T) {
t.Helper()
if err := l.check(); err != nil {
t.Fatal(err)
}
if got := slices.Collect(l.All()); !slices.Equal(got, want) {
t.Fatalf("forward %v, want %v", got, want)
}
reversed := slices.Clone(want)
slices.Reverse(reversed)
if got := slices.Collect(l.Backward()); !slices.Equal(got, reversed) {
t.Fatalf("backward %v, want %v", got, reversed)
}
}
The table-driven tests cover the positions where a nil-terminated implementation would have needed a special case. They pass trivially here, which is the evidence for the sentinel: there is no front case, no back case and no only-element case left in the code to get wrong.
func TestRemove(t *testing.T) {
tests := []struct {
name string
in []int
at int
want []int
}{
{"front", []int{1, 2, 3}, 0, []int{2, 3}},
{"middle", []int{1, 2, 3}, 1, []int{1, 3}},
{"back", []int{1, 2, 3}, 2, []int{1, 2}},
{"only element", []int{1}, 0, nil},
}
for _, tt := range tests {
t.Run(tt.name, func(t *testing.T) {
l, nodes := fromSlice(tt.in)
victim := nodes[tt.at]
if got := l.Remove(victim); got != tt.in[tt.at] {
t.Errorf("Remove returned %d, want %d", got, tt.in[tt.at])
}
collectBoth(t, l, tt.want)
if victim.Next() != nil || victim.Prev() != nil {
t.Error("the removed node still names a position in the list")
}
if l.Remove(victim); l.Len() != len(tt.want) {
t.Error("removing the same node twice changed the length")
}
})
}
}
The claim that removal is constant time is a claim about how much work the operation does, and timing it would measure the machine instead. Count the links it changes: three nodes, whatever the length. This is the test that would catch a Remove that walked from the head to find the predecessor, which is the mistake that turns this structure back into a singly linked list with wasted memory.
func TestRemoveTouchesThreeNodes(t *testing.T) {
for _, n := range []int{8, 1000, 100000} {
vs := make([]int, n)
for i := range vs {
vs[i] = i
}
l, nodes := fromSlice(vs)
type links struct{ prev, next *Node[int] }
before := make(map[*Node[int]]links, n)
for _, nd := range nodes {
before[nd] = links{nd.prev, nd.next}
}
l.Remove(nodes[n/2])
// Ranging a map is fine here: this loop counts, and a count does not
// depend on the order the runtime hands the keys back.
changed := 0
for nd, was := range before {
if nd.prev != was.prev || nd.next != was.next {
changed++
}
}
if changed != 3 {
t.Errorf("n=%d: Remove changed %d nodes, want 3", n, changed)
}
if err := l.check(); err != nil {
t.Fatal(err)
}
}
}
The test that finds the most is a randomised operation sequence against a reference, and for a list the reference is a slice. Generate operations, apply each one to both, and compare both directions after every single one, so a failure names the operation that broke the invariant rather than the one that noticed. The reference stays a few lines because slices.Insert and slices.Delete do its work, which also means a bug in the list cannot appear identically in the reference.
func TestMatchesSliceReference(t *testing.T) {
rng := rand.New(rand.NewPCG(11, 13)) // fixed seed, so a failure replays
for range 400 {
l := &List[int]{}
var nodes []*Node[int]
var ref []int
for range rng.IntN(60) {
switch rng.IntN(5) {
case 0:
v := rng.IntN(100)
nodes = slices.Insert(nodes, 0, l.PushFront(v))
ref = slices.Insert(ref, 0, v)
case 1:
v := rng.IntN(100)
nodes = append(nodes, l.PushBack(v))
ref = append(ref, v)
case 2:
if len(ref) == 0 {
continue
}
i := rng.IntN(len(ref))
l.Remove(nodes[i])
nodes = slices.Delete(nodes, i, i+1)
ref = slices.Delete(ref, i, i+1)
case 3:
if len(ref) == 0 {
continue
}
i := rng.IntN(len(ref))
nd, v := nodes[i], ref[i]
l.MoveToFront(nd)
nodes = slices.Insert(slices.Delete(nodes, i, i+1), 0, nd)
ref = slices.Insert(slices.Delete(ref, i, i+1), 0, v)
case 4:
if len(ref) == 0 {
continue
}
i := rng.IntN(len(ref))
v := rng.IntN(100)
nodes = slices.Insert(nodes, i+1, l.InsertAfter(nodes[i], v))
ref = slices.Insert(ref, i+1, v)
}
collectBoth(t, l, ref)
if l.Len() != len(ref) {
t.Fatalf("length %d, reference length %d", l.Len(), len(ref))
}
}
}
}
One hazard in that test is worth naming, because it belongs to Go rather than to linked lists and it catches people regularly. slices.Delete and slices.Insert return a slice that may share its backing array with the one passed in, so the results have to be assigned back. Read nodes after an unassigned slices.Delete and you see a mixture of the old and new orders. The reference is aliasing-sensitive in exactly the way the structure under test is not, which is a fair description of why both exist.
Where the claim is about cost, the test is a benchmark and the result is a measurement on one machine rather than a fact about Go. This one puts the generic list beside container/list on the same work. Read allocs/op first, because the allocation count is a property of the code and will say the same thing on your laptop and in your cluster, where the nanoseconds will not.
var sink int
func BenchmarkBuild(b *testing.B) {
const n = 1024
b.Run("dlist", func(b *testing.B) {
b.ReportAllocs()
for range b.N {
l := &List[int]{}
for i := range n {
l.PushBack(i)
}
sink = l.Len()
}
})
b.Run("container/list", func(b *testing.B) {
b.ReportAllocs()
for range b.N {
l := list.New()
for i := range n {
l.PushBack(i)
}
sink = l.Len()
}
})
}
func BenchmarkTraverse(b *testing.B) {
const n = 1 << 14
mine := &List[int]{}
theirs := list.New()
for i := range n {
mine.PushBack(i)
theirs.PushBack(i)
}
b.Run("dlist", func(b *testing.B) {
for range b.N {
total := 0
for v := range mine.All() {
total += v
}
sink = total
}
})
b.Run("container/list", func(b *testing.B) {
for range b.N {
total := 0
for e := theirs.Front(); e != nil; e = e.Next() {
total += e.Value.(int)
}
sink = total
}
})
b.Run("backward", func(b *testing.B) {
for range b.N {
total := 0
for v := range mine.Backward() {
total += v
}
sink = total
}
})
}
Both lists in BenchmarkTraverse are built once, outside the timed loop, so their nodes were allocated consecutively and are laid out about as well as a list ever manages. A list that has grown and shrunk for hours has its nodes scattered, and it traverses worse than this. The backward case is in there because it is the one measurement that is specific to this structure: the same nodes, visited in the reverse of their allocation order, on hardware built to reward the forward one.
The structure has no internal synchronisation, and the use that catches people is the LRU cache above. Get looks like a read and writes four pointers, so two goroutines calling it concurrently under a read lock are a data race on the list even when they ask for different keys. go test -race reports it with both stacks the first time the test exercises it, and the fix is a full mutex or an eviction policy that does not reorder on a hit. Running the randomised test above under -race takes seconds, and it is the one place a concurrency bug in this code will show itself before production does.