Linked lists

Nodes joined by pointers: reversal, the dummy head, fast and slow pointers, and an LRU cache built from a map and a list.

The node#

type ListNode struct {
	Val  int
	Next *ListNode // nil marks the end
}

A list is just a pointer to its first node (the head). An empty list is a nil head.

head -> [1] -> [2] -> [3] -> nil

Operation	Slice	Linked list
read index k	O(1)	O(k)
insert/delete at front	O(n)	O(1)
insert/delete after a known node	O(n)	O(1)
memory locality	excellent	poor (nodes scattered)

Try it

Build a list from a slice, walk it, and insert in the middle by rewiring two pointers:

list_basics.go

package main
 
import (
	"fmt"
	"strings"
)
 
type ListNode struct {
	Val  int
	Next *ListNode
}
 
func fromSlice(vals []int) *ListNode {
	dummy := &ListNode{}
	tail := dummy
	for _, v := range vals {
		tail.Next = &ListNode{Val: v}
		tail = tail.Next
	}
	return dummy.Next
}
 
func show(head *ListNode) string {
	var b strings.Builder
	for n := head; n != nil; n = n.Next {
		fmt.Fprintf(&b, "[%d] -> ", n.Val)
	}
	return b.String() + "nil"
}
 
func main() {
	head := fromSlice([]int{1, 2, 4})
	fmt.Println(show(head))
 
	// Insert 3 after the node holding 2: O(1) once we hold that node.
	two := head.Next
	two.Next = &ListNode{Val: 3, Next: two.Next}
	fmt.Println(show(head))
 
	// Delete the node after the head: skip over it.
	head.Next = head.Next.Next
	fmt.Println(show(head))
}

Output

[1] -> [2] -> [4] -> nil
[1] -> [2] -> [3] -> [4] -> nil
[1] -> [3] -> [4] -> nil

Technique 1: reverse in place#

Walk the list, turning each Next pointer around. Three variables: prev (the reversed part), cur (the node being moved) and next (saved before we overwrite cur.Next).

Trace 1 -> 2 -> 3:

step	prev	cur	next (saved)	after `cur.Next = prev`
start	nil	1
1	nil	1	2	`1 -> nil`; move: prev = 1, cur = 2
2	1	2	3	`2 -> 1 -> nil`; prev = 2, cur = 3
3	2	3	nil	`3 -> 2 -> 1 -> nil`; prev = 3, cur = nil

When cur is nil, prev is the new head.

Run the trace

reverse_trace.go

package main
 
import (
	"fmt"
	"strings"
)
 
type ListNode struct {
	Val  int
	Next *ListNode
}
 
func show(head *ListNode) string {
	var b strings.Builder
	for n := head; n != nil; n = n.Next {
		fmt.Fprintf(&b, "%d -> ", n.Val)
	}
	return b.String() + "nil"
}
 
func main() {
	head := &ListNode{1, &ListNode{2, &ListNode{3, nil}}}
	var prev *ListNode
	cur := head
	for step := 1; cur != nil; step++ {
		next := cur.Next // save before overwriting
		cur.Next = prev  // turn the pointer around
		prev, cur = cur, next
		fmt.Printf("step %d: reversed part %-18s rest %s\n", step, show(prev), show(cur))
	}
	fmt.Println("new head:", prev.Val)
}

Output

step 1: reversed part 1 -> nil           rest 2 -> 3 -> nil
step 2: reversed part 2 -> 1 -> nil      rest 3 -> nil
step 3: reversed part 3 -> 2 -> 1 -> nil rest nil
new head: 3

Technique 2: the dummy head#

When building a new list (merging, filtering, removing nodes), the first node is a special case: there is nothing before it to attach to. A dummy node removes that case:

dummy := &ListNode{}
tail := dummy
// ... tail.Next = node; tail = tail.Next
return dummy.Next

Try it: remove every node with a value

Without the dummy, removing a leading 6 would need its own if that moves head. With it, every node, including the first, has a node before it:

dummy.go

package main
 
import "fmt"
 
type ListNode struct {
	Val  int
	Next *ListNode
}
 
func removeElements(head *ListNode, val int) *ListNode {
	dummy := &ListNode{Next: head}
	prev := dummy
	for prev.Next != nil {
		if prev.Next.Val == val {
			prev.Next = prev.Next.Next // unlink; prev stays to check the new next
		} else {
			prev = prev.Next
		}
	}
	return dummy.Next
}
 
func main() {
	var head *ListNode
	for _, v := range []int{6, 6, 1, 6, 2, 6} { // prepending reverses: the list is 6 2 6 1 6 6
		head = &ListNode{v, head}
	}
	for n := removeElements(head, 6); n != nil; n = n.Next {
		fmt.Print(n.Val, " ")
	}
	fmt.Println()
}

Output

2 1

Technique 3: fast and slow pointers#

Two pointers moving at different speeds reveal structure:

Middle: fast moves 2, slow moves 1. When fast reaches the end, slow is in the middle.
Cycle: if the list loops, fast eventually laps slow and they meet. If fast hits nil, there is no cycle. This is Floyd's algorithm, O(n) time and O(1) space.
n-th from the end: move a lead pointer n steps ahead, then move both; when lead reaches the end, the trailing pointer is in position.

Run the trace

fastslow_trace.go

package main
 
import "fmt"
 
type ListNode struct {
	Val  int
	Next *ListNode
}
 
func build(n int) *ListNode {
	var head *ListNode
	for v := n; v >= 1; v-- {
		head = &ListNode{v, head}
	}
	return head
}
 
func middle(head *ListNode) *ListNode {
	slow, fast := head, head
	for fast != nil && fast.Next != nil {
		slow, fast = slow.Next, fast.Next.Next
		fv := "nil"
		if fast != nil {
			fv = fmt.Sprint(fast.Val)
		}
		fmt.Printf("  slow=%d fast=%s\n", slow.Val, fv)
	}
	return slow
}
 
func hasCycle(head *ListNode) bool {
	slow, fast := head, head
	for steps := 1; fast != nil && fast.Next != nil; steps++ {
		slow, fast = slow.Next, fast.Next.Next
		if slow == fast {
			fmt.Printf("  met at node %d after %d steps\n", slow.Val, steps)
			return true
		}
	}
	return false
}
 
func main() {
	fmt.Println("middle of 1..5:")
	fmt.Println("  ->", middle(build(5)).Val)
 
	head := build(6)
	tail := head
	for tail.Next != nil {
		tail = tail.Next
	}
	tail.Next = head.Next.Next // 6 points back to 3: a cycle
	fmt.Println("cycle check:")
	fmt.Println("  ->", hasCycle(head))
}

Output

middle of 1..5:
  slow=2 fast=3
  slow=3 fast=5
  -> 3
cycle check:
  met at node 5 after 4 steps
  -> true

Technique 4: LRU cache with map + list#

An LRU (least recently used) cache holds capacity items and evicts the one unused for longest. It needs O(1) lookup (a map) and O(1) "move to most recent" and "remove least recent" (a doubly linked list). Go's container/list is a doubly linked list:

Operation	Steps
Get(key)	look up the element in the map; move it to the front
Put(key, val)	update and move to front, or insert at front; if over capacity, remove the back element and delete its key from the map

container/list in two minutes

These are the operations the LRU cache relies on. Each *list.Element is a handle you can keep in a map and later move or remove in O(1):

containerlist.go

package main
 
import (
	"container/list"
	"fmt"
)
 
func show(l *list.List) {
	for e := l.Front(); e != nil; e = e.Next() {
		fmt.Print(e.Value, " ")
	}
	fmt.Println()
}
 
func main() {
	l := list.New()
	l.PushBack("a")
	l.PushBack("b")
	c := l.PushBack("c")
	show(l)
 
	l.MoveToFront(c) // "c" was just used
	show(l)
 
	oldest := l.Back() // least recently used
	l.Remove(oldest)
	fmt.Print("evicted ", oldest.Value, ": ")
	show(l)
}

Output

a b c 
c a b 
evicted b: c a

The full program#

lists.go

package main
 
import (
	"container/list"
	"fmt"
)
 
type ListNode struct {
	Val  int
	Next *ListNode
}
 
func fromSlice(vals []int) *ListNode {
	dummy := &ListNode{}
	tail := dummy
	for _, v := range vals {
		tail.Next = &ListNode{Val: v}
		tail = tail.Next
	}
	return dummy.Next
}
 
func toSlice(head *ListNode) []int {
	var out []int
	for n := head; n != nil; n = n.Next {
		out = append(out, n.Val)
	}
	return out
}
 
func reverseList(head *ListNode) *ListNode {
	var prev *ListNode
	for cur := head; cur != nil; {
		next := cur.Next
		cur.Next = prev
		prev, cur = cur, next
	}
	return prev
}
 
func mergeTwoLists(a, b *ListNode) *ListNode {
	dummy := &ListNode{}
	tail := dummy
	for a != nil && b != nil {
		if a.Val <= b.Val {
			tail.Next, a = a, a.Next
		} else {
			tail.Next, b = b, b.Next
		}
		tail = tail.Next
	}
	if a != nil {
		tail.Next = a
	} else {
		tail.Next = b
	}
	return dummy.Next
}
 
func middle(head *ListNode) *ListNode {
	slow, fast := head, head
	for fast != nil && fast.Next != nil {
		slow, fast = slow.Next, fast.Next.Next
	}
	return slow
}
 
func hasCycle(head *ListNode) bool {
	slow, fast := head, head
	for fast != nil && fast.Next != nil {
		slow, fast = slow.Next, fast.Next.Next
		if slow == fast {
			return true
		}
	}
	return false
}
 
type entry struct{ key, val int }
 
type LRUCache struct {
	cap   int
	order *list.List // front = most recently used
	items map[int]*list.Element
}
 
func NewLRU(capacity int) *LRUCache {
	return &LRUCache{cap: capacity, order: list.New(), items: map[int]*list.Element{}}
}
 
func (c *LRUCache) Get(key int) int {
	el, ok := c.items[key]
	if !ok {
		return -1
	}
	c.order.MoveToFront(el)
	return el.Value.(entry).val
}
 
func (c *LRUCache) Put(key, val int) {
	if el, ok := c.items[key]; ok {
		el.Value = entry{key, val}
		c.order.MoveToFront(el)
		return
	}
	c.items[key] = c.order.PushFront(entry{key, val})
	if c.order.Len() > c.cap {
		oldest := c.order.Back()
		c.order.Remove(oldest)
		delete(c.items, oldest.Value.(entry).key)
	}
}
 
func main() {
	fmt.Println(toSlice(reverseList(fromSlice([]int{1, 2, 3}))))
	fmt.Println(toSlice(mergeTwoLists(fromSlice([]int{1, 4, 6}), fromSlice([]int{2, 3, 7}))))
	fmt.Println(middle(fromSlice([]int{1, 2, 3, 4, 5})).Val)
 
	loop := fromSlice([]int{1, 2, 3, 4})
	loop.Next.Next.Next.Next = loop.Next // 4 points back to 2
	fmt.Println(hasCycle(loop), hasCycle(fromSlice([]int{1, 2})))
 
	c := NewLRU(2)
	c.Put(1, 10)
	c.Put(2, 20)
	c.Get(1)     // 1 is now most recent
	c.Put(3, 30) // evicts 2
	fmt.Println(c.Get(1), c.Get(2), c.Get(3))
}

Output

[3 2 1]
[1 2 3 4 6 7]
3
true false
10 -1 30

Complexity#

Operation	Time	Space
reverse	O(n)	O(1)
merge two sorted lists	O(n + m)	O(1)
middle, cycle check	O(n)	O(1)
LRU Get / Put	O(1)	O(capacity)

Summary#

A linked list trades O(1) inserts next to a known node for O(n) indexing and poor cache locality.
Reverse with prev, cur, next; save next before rewiring.
A dummy head removes first-node special cases.
Fast and slow pointers find middles, cycles and positions from the end in O(1) space.
Map + container/list gives an O(1) LRU cache.

The node#

Try it

Technique 1: reverse in place#

Run the trace

Technique 2: the dummy head#

Try it: remove every node with a value

Technique 3: fast and slow pointers#

Run the trace

Technique 4: LRU cache with map + list#

container/list in two minutes

The full program#

Complexity#

Summary#

Check your understanding

Practice in Go