Linked Lists

Nodes and Pointers

Each node holds a value and a pointer to the next node. The list itself holds only a pointer to the first node; everything else is reached by following pointers.

Linked List vs Slice

The two structures make opposite trade-offs. The list wins only where it avoids shifting elements and you already hold a reference to the node — which is exactly the situation in an LRU cache or a text editor's cursor.

A Generic Node Type

With generics one node type serves every element type. The constraint comparable allows ==, which searching and removing by value require. Keeping the node type unexported forces callers to go through the list's methods, so the list's invariants (head, tail, and size stay consistent) cannot be broken from outside.

// node is unexported: only List's methods manipulate pointers.
type node[T comparable] struct {
	val  T
	next *node[T] // nil marks the end of the list
}

// List is usable as its zero value: head == tail == nil means empty.
type List[T comparable] struct {
	head, tail *node[T]
	size       int
}

Singly Linked List

A singly linked list can be walked in one direction only. Keeping a tail pointer in addition to head makes appending O(1), at the cost of one more pointer to keep correct in every operation.

Top: head and tail give O(1) access to both ends. Bottom: removing a node changes one pointer in its predecessor — which is why a singly linked list must find the node before the one being removed.

Push and Pop at the Ends

Every operation must handle the transition between empty and non-empty: the first push sets both head and tail, and popping the last node must reset both to nil. Forgetting the second half is the most common list bug.

func (l *List[T]) PushBack(v T) {
	n := &node[T]{val: v}
	if l.tail == nil { // empty list: n is both head and tail
		l.head, l.tail = n, n
	} else {
		l.tail.next = n
		l.tail = n
	}
	l.size++
}

func (l *List[T]) PopFront() (v T, ok bool) {
	if l.head == nil {
		return v, false // v is T's zero value
	}
	n := l.head
	l.head = n.next
	if l.head == nil { // removed the only node
		l.tail = nil
	}
	l.size--
	return n.val, true
}

Removing a Node

Removal changes the next pointer of the node before the victim, so the search stops one step early. Three cases need care: the victim is the head (no predecessor), the victim is the tail (the tail pointer must move back), and the value is absent.

func (l *List[T]) Remove(v T) bool {
	if l.head == nil {
		return false
	}
	if l.head.val == v { // no predecessor: reuse PopFront
		l.PopFront()
		return true
	}
	prev := l.head
	for prev.next != nil && prev.next.val != v {
		prev = prev.next
	}
	if prev.next == nil {
		return false // not found
	}
	victim := prev.next
	prev.next = victim.next // unlink
	if victim == l.tail {
		l.tail = prev // the tail moved back
	}
	l.size--
	return true
}

Iteration

Since Go 1.23 a collection can offer an iterator function that works with for … range. The function calls yield for each value and stops if yield returns false (the caller used break). The full list, with a self-checking test of every edge case above: 15_singly_linked_list.go.

// All lets callers write: for v := range list.All() { ... }
func (l *List[T]) All() func(yield func(T) bool) {
	return func(yield func(T) bool) {
		for n := l.head; n != nil; n = n.next {
			if !yield(n.val) {
				return // the loop body executed break
			}
		}
	}
}

Doubly Linked List

Adding a prev pointer to every node costs memory but gives two abilities: walking backward, and removing any node in O(1) without searching for its predecessor.

A sentinel node closes the list into a ring. Every real node always has a non-nil prev and next, so insertion and removal need no special cases.

Sentinel Nodes

A sentinel (or dummy) node is a node that holds no data and never leaves the list. sentinel.next is the first real node and sentinel.prev the last; in an empty list both point to the sentinel itself. The empty-list and end-of-list special cases disappear, and the code becomes shorter and harder to get wrong. Go's container/list is implemented exactly this way.

Linking and Unlinking in O(1)

Insertion writes four pointers and removal writes two. The order matters for insertion: set the new node's own pointers first, while the neighbors are still reachable.

// insertAfter links n directly after node at.
func insertAfter(n, at *Node) {
	n.prev = at
	n.next = at.next
	at.next.prev = n // at.next is never nil: the sentinel closes the ring
	at.next = n
}

// unlink removes n; its neighbors now point past it.
func unlink(n *Node) {
	n.prev.next = n.next
	n.next.prev = n.prev
	n.prev, n.next = nil, nil // a detached node must not be walked
}

The demo builds a playlist with a map from song name to node, so "move this song to the front" costs O(1): a map lookup, an unlink, and an insert. It also checks the invariant n.next.prev == n after every operation: 17_doubly_linked_list.go. This map-plus-list combination is exactly an LRU cache, built in Phase 4.

container/list

The standard library's container/list is a doubly linked list with a sentinel. It stores values as any, so each read needs a type assertion (e.Value.(string)), and its methods such as MoveToFront and Remove take the *list.Element you received when inserting. Use it when you need O(1) moves of elements you hold references to; for plain sequences, use a slice.

Pointer Techniques

Five techniques solve most linked-list problems. All of them run in O(n) time and O(1) extra space. The demo implements each and checks the results: 16_list_algorithms.go.

Reversal with Three Pointers

Reversing flips every next pointer. Before flipping cur.next, save it — otherwise the rest of the list is lost. The four lines inside the loop are worth memorizing in this exact order.

func reverse(head *Node) *Node {
	var prev *Node
	cur := head
	for cur != nil {
		next := cur.Next // 1. save the rest of the list
		cur.Next = prev  // 2. flip this pointer
		prev = cur       // 3. advance prev
		cur = next       // 4. advance cur
	}
	return prev // the old tail is the new head
}

Slow and Fast Pointers

Move one pointer one step at a time and another two steps. When the fast pointer reaches the end, the slow pointer is at the middle. If the list has a cycle, the fast pointer never reaches the end; inside the cycle it gains one step per iteration on the slow pointer, so the two must meet. This is Floyd's cycle detection, which needs O(1) memory where a set of visited nodes would need O(n).

func hasCycle(head *Node) bool {
	slow, fast := head, head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
		if slow == fast { // same node (pointer identity), not same value
			return true
		}
	}
	return false
}

Gap Pointers and Dummy Heads

To remove the n-th node from the end in one pass, start a lead pointer n + 1 steps ahead of a trail pointer and advance both until the lead falls off the end; the trail then sits just before the victim. Starting both at a dummy node placed before the head makes removing the head itself an ordinary case, and the function returns dummy.Next as the (possibly new) head.

Merging by Relinking

Merging two sorted lists needs no new nodes: repeatedly take the smaller head and append it to a result built behind a dummy node. When one list runs out, attach the rest of the other in a single pointer write. This is the merge step of merge sort on linked lists, which runs in O(n log n) with O(1) extra space for the merge itself.

Common Pitfalls

Almost every list bug is a pointer written in the wrong order or a case that was not considered.

Losing the Rest of the List

Writing cur.Next = prev before saving cur.Next disconnects everything after cur. Before any pointer write, ask: "do I still hold a reference to every node I will need?"

nil Dereferences

fast.Next.Next panics if fast.Next is nil. Check every pointer you dereference, in the order you dereference it: fast != nil && fast.Next != nil. Sentinel nodes remove many of these checks.

Walking a Cyclic List

Printing or measuring a list that contains a cycle loops forever. Code that may receive untrusted or corrupted lists should detect cycles first or cap the number of steps.

Practice Lab

Draw the pointers on paper before coding each exercise; list bugs are much easier to see in a diagram than in code.

Run the Demos

1. In 15_singly_linked_list.go, delete the line l.tail = prev in Remove. Which checks fail, and why?
2. In 17_doubly_linked_list.go, delete the line at.next.prev = n in insertAfter. Run it: songs land in the wrong order, checkLinks fails, and the program finally panics on a nil pointer. Trace why one missing write corrupts every later operation.

Exercises

1. Cycle start. Extend Floyd's algorithm to return the node where the cycle begins. (After the pointers meet, move one to the head and advance both one step at a time.)
2. Reverse in groups. Reverse the nodes of a list in groups of k, leaving a final group shorter than k unchanged.
3. Sort a list. Implement merge sort on a singly linked list using middle to split and mergeSorted to combine.
4. Intersection. Two lists merge into one shared tail. Find the first shared node in O(n + m) time and O(1) space.

Next lesson: Stacks & Queues.