Doubly Linked Lists

Every node points both forward and backward, so the list can be walked either direction and a known node removed in O(1).

The shape

Doubly-linked nodes

Each node points forward and backward, so the list can be walked either way.

PushFront: link the new node in ahead of the old head.
PushBack: link it in behind the old tail.
Remove: join the node's two neighbors to each other.

Push a value at either end, or remove one, and watch both sets of pointers rewire.

Purpose

Hold a sequence you can walk in both directions and remove from anywhere in one step.

Input

Values pushed at the front or the back.

Output

The values in order from Head, or in reverse from Tail.

Constraints

Every node carries two pointers, so it costs more memory than a singly-linked list.
Removing a node needs only the node itself, since it can see both neighbors.
The standard library ships this as container/list.

A generic Node[T] works for any value type. Len tracks size so it doesn't need to be computed by walking the list.

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

type List[T any] struct {
    Head *Node[T]
    Tail *Node[T]
    Len  int
}

PushFront allocates a node, relinks the old head's Prev, and updates Head. Insertion is O(1) regardless of list size.

func (l *List[T]) PushFront(v T) {
    n := &Node[T]{Value: v}
    if l.Head == nil {
        l.Head, l.Tail = n, n
    } else {
        n.Next = l.Head
        l.Head.Prev = n
        l.Head = n
    }
    l.Len++
}

Remove takes a node pointer directly, no search required, which is the main advantage over a singly linked list. Both branches guard against removing an end node.

func (l *List[T]) Remove(n *Node[T]) {
    if n.Prev != nil {
        n.Prev.Next = n.Next
    } else {
        l.Head = n.Next // n was head
    }
    if n.Next != nil {
        n.Next.Prev = n.Prev
    } else {
        l.Tail = n.Prev // n was tail
    }
    l.Len--
}

The whole program main.go Show

package main

import "fmt"

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

type List[T any] struct {
    Head *Node[T]
    Tail *Node[T]
    Len  int
}

func (l *List[T]) PushFront(v T) {
    n := &Node[T]{Value: v}
    if l.Head == nil {
        l.Head, l.Tail = n, n
    } else {
        n.Next = l.Head
        l.Head.Prev = n
        l.Head = n
    }
    l.Len++
}

func (l *List[T]) Remove(n *Node[T]) {
    if n.Prev != nil {
        n.Prev.Next = n.Next
    } else {
        l.Head = n.Next // n was head
    }
    if n.Next != nil {
        n.Next.Prev = n.Prev
    } else {
        l.Tail = n.Prev // n was tail
    }
    l.Len--
}

func (l *List[T]) Forward() {
    var vals []any
    for n := l.Head; n != nil; n = n.Next {
        vals = append(vals, n.Value)
    }
    fmt.Println(vals...)
}

// Backward is the whole point of the second pointer: the same list read from
// the other end, without walking it from the head first.
func (l *List[T]) Backward() {
    var vals []any
    for n := l.Tail; n != nil; n = n.Prev {
        vals = append(vals, n.Value)
    }
    fmt.Println(vals...)
}

func main() {
    l := &List[int]{}
    l.PushFront(30)
    l.PushFront(20)
    l.PushFront(10)

    l.Forward()
    l.Backward()

    // The second pointer means any node can look both ways without walking
    // from an end first.
    mid := l.Head.Next
    fmt.Println(mid.Value, "sits between", mid.Prev.Value, "and", mid.Next.Value)
}

Forward traversal follows Next from Head; backward traversal follows Prev from Tail.

Terminal

$ go run main.go
10 20 30
30 20 10
20 sits between 10 and 30

Previous Linked List Next Topic Quick Sort