Linked Lists

Updated

October 31, 2026

Linked Lists

A linked list arranges elements as independent heap nodes connected through pointers rather than contiguous memory slots. The boring default in Go is to use contiguous slices ([]T) for virtually every collection, but linked lists provide valuable insights into pointer semantics, bidirectional node manipulation, and \(O(1)\) insertions without memory shifting.

Linked Lists Diagram

Mental model

In a singly linked list, each node holds a payload value and a single next pointer. In a doubly linked list, each node holds both next and prev pointers.

Singly Linked:
[Head] -> [Data: 101 | Next] -> [Data: 102 | Next] -> nil

Doubly Linked:
nil <- [Prev | Data: 101 | Next] <===> [Prev | Data: 102 | Next] -> nil

Slice vs Linked List: The Hardware Reality

Why is []T almost always faster in Go than a linked list?

Feature Go Slice ([]T) Doubly Linked List
Contiguity Single continuous memory block Scattered heap allocations
CPU Cache Prefetched into L1/L2 cache lines Cache miss on nearly every pointer hop
Memory Overhead Zero extra bytes per element 16–24 bytes of pointers per node
Insertion at Head \(O(n)\) (shifts memory) \(O(1)\) (rewires pointers)
Random Access \(O(1)\) by index s[i] \(O(n)\) traversal from head/tail

Use linked lists when you must splice elements into arbitrary positions without reallocating or copying large structures (such as an LRU cache).

Worked examples

Case 1: Singly linked list with in-place reversal

Save as singly_linked.go. Build a generic singly linked list for desk dispatch tickets and reverse it in place without allocating new nodes.

// singly_linked.go
package main

import "fmt"

type Node[T any] struct {
    Value T
    Next  *Node[T]
}

type SinglyList[T any] struct {
    Head *Node[T]
    len  int
}

func (l *SinglyList[T]) Prepend(val T) {
    newNode := &Node[T]{Value: val, Next: l.Head}
    l.Head = newNode
    l.len++
}

func (l *SinglyList[T]) Append(val T) {
    newNode := &Node[T]{Value: val}
    if l.Head == nil {
        l.Head = newNode
        l.len++
        return
    }
    curr := l.Head
    for curr.Next != nil {
        curr = curr.Next
    }
    curr.Next = newNode
    l.len++
}

func (l *SinglyList[T]) Reverse() {
    var prev *Node[T]
    curr := l.Head
    for curr != nil {
        next := curr.Next
        curr.Next = prev
        prev = curr
        curr = next
    }
    l.Head = prev
}

func (l *SinglyList[T]) Print() {
    curr := l.Head
    for curr != nil {
        fmt.Printf("[%v] -> ", curr.Value)
        curr = curr.Next
    }
    fmt.Println("nil")
}

func main() {
    list := &SinglyList[string]{}
    list.Append("Ticket-101")
    list.Append("Ticket-102")
    list.Append("Ticket-103")

    fmt.Print("Original list: ")
    list.Print()

    list.Reverse()
    fmt.Print("Reversed list: ")
    list.Print()
}

Run:

go run singly_linked.go

Output:

Original list: [Ticket-101] -> [Ticket-102] -> [Ticket-103] -> nil
Reversed list: [Ticket-103] -> [Ticket-102] -> [Ticket-101] -> nil

Case 2: Doubly linked list with O(1) removal

Save as doubly_linked.go. Implement a doubly linked list where any node can unlink itself in \(O(1)\) time.

// doubly_linked.go
package main

import "fmt"

type DNode[T any] struct {
    Value T
    Prev  *DNode[T]
    Next  *DNode[T]
}

type DoublyList[T any] struct {
    Head *DNode[T]
    Tail *DNode[T]
    len  int
}

func (l *DoublyList[T]) PushBack(val T) *DNode[T] {
    node := &DNode[T]{Value: val, Prev: l.Tail}
    if l.Tail != nil {
        l.Tail.Next = node
    } else {
        l.Head = node
    }
    l.Tail = node
    l.len++
    return node
}

func (l *DoublyList[T]) Remove(node *DNode[T]) {
    if node == nil {
        return
    }
    if node.Prev != nil {
        node.Prev.Next = node.Next
    } else {
        l.Head = node.Next
    }

    if node.Next != nil {
        node.Next.Prev = node.Prev
    } else {
        l.Tail = node.Prev
    }

    node.Next = nil
    node.Prev = nil
    l.len--
}

func (l *DoublyList[T]) PrintForward() {
    curr := l.Head
    for curr != nil {
        fmt.Printf("[%v] <-> ", curr.Value)
        curr = curr.Next
    }
    fmt.Println("nil")
}

func main() {
    list := &DoublyList[int]{}
    n1 := list.PushBack(101)
    n2 := list.PushBack(102)
    n3 := list.PushBack(103)

    fmt.Print("Initial: ")
    list.PrintForward()

    fmt.Printf("Removing middle node: %d\n", n2.Value)
    list.Remove(n2)
    list.PrintForward()

    fmt.Printf("Removing head node: %d\n", n1.Value)
    list.Remove(n1)
    list.PrintForward()

    fmt.Printf("Final tail: %d\n", list.Tail.Value)
    _ = n3
}

Run:

go run doubly_linked.go

Output:

Initial: [101] <-> [102] <-> [103] <-> nil
Removing middle node: 102
[101] <-> [103] <-> nil
Removing head node: 101
[103] <-> nil
Final tail: 103

The trap

The classic trap when modifying a linked list is accidentally dropping the head pointer before wiring the new node, or creating a circular pointer loop during reversal.

// bad_prepend.go
package main

import "fmt"

type ItemNode struct {
    ID   int
    Next *ItemNode
}

func badPrepend(head *ItemNode, id int) {
    // TRAP: In Go, arguments are passed by value.
    // Assigning head = newNode only changes the local copy of the pointer!
    newNode := &ItemNode{ID: id, Next: head}
    head = newNode
    _ = head
}

func goodPrepend(head **ItemNode, id int) {
    newNode := &ItemNode{ID: id, Next: *head}
    *head = newNode
}

func main() {
    var head *ItemNode
    badPrepend(head, 101)
    fmt.Printf("After badPrepend, head is still nil: %t\n", head == nil)

    goodPrepend(&head, 101)
    fmt.Printf("After goodPrepend, head ID: %d\n", head.ID)
}

Run:

go run bad_prepend.go

Output:

After badPrepend, head is still nil: true
After goodPrepend, head ID: 101

The boring rule

  1. Use slices ([]T) by default. Slices beat linked lists in 95% of workloads because CPUs fetch contiguous cache lines in parallel.
  2. If you need a linked list in Go, inspect the standard library’s container/list before rolling your own.
  3. When writing custom pointer-linked structures, encapsulate mutations inside methods on the list struct (func (l *List) Push()) rather than passing raw node pointers across API boundaries.
  4. When unlinking a node, clear its Next and Prev references to assist garbage collection.

Try this

  1. Implement Find(predicate func(T) bool) *Node[T] on SinglyList to locate tickets matching specific criteria.
  2. Combine a map[string]*DNode[Order] with DoublyList to build a 3-item Least-Recently-Used (LRU) cache for desk orders.