Each node points forward to the next one. Walking the list only goes one direction, and finding a node's predecessor means starting over from the head.
The shape
Singly-linked nodes
Each node holds a value and a pointer to the next one, and the list holds the ends.
- PushFront: point the new node at the old head.
- PushBack: point the old tail at the new node.
- Remove: walk to the node in front and skip past the one going.
Push a value at either end, or remove one, and watch the pointers rewire.
Purpose
Hold a sequence where adding and removing at the ends costs nothing.
Input
Values pushed at the front or the back.
Output
The values in order, walked from Head.
Constraints
- Reaching the nth value means walking n nodes. There is no indexing.
- Head, Tail and Len are kept on the list, so none of them has to be recomputed.
- Removing a node means finding the one in front of it, since a node cannot see backwards.
A generic Node[T] and List[T] work for any value type. Tail makes appends O(1); without it, PushBack would need to walk the whole list first.
type Node[T any] struct {
Value T
Next *Node[T]
}
type List[T any] struct {
Head *Node[T]
Tail *Node[T]
Len int
}PushFront links the new node ahead of the old head, an O(1) operation. PushBack is also O(1) because Tail is already tracked.
func (l *List[T]) PushFront(v T) {
n := &Node[T]{Value: v, Next: l.Head}
l.Head = n
if l.Tail == nil {
l.Tail = n
}
l.Len++
}
func (l *List[T]) PushBack(v T) {
n := &Node[T]{Value: v}
if l.Tail == nil {
l.Head, l.Tail = n, n
} else {
l.Tail.Next = n
l.Tail = n
}
l.Len++
}Remove needs the node before the target, since there's no Prev pointer to read it directly. The loop walks from Head until it finds the node whose Next is the target, an O(n) operation, then relinks around it.
func (l *List[T]) Remove(target *Node[T]) {
if l.Head == target {
l.Head = target.Next
if l.Tail == target {
l.Tail = nil
}
l.Len--
return
}
for n := l.Head; n.Next != nil; n = n.Next {
if n.Next == target {
n.Next = target.Next
if l.Tail == target {
l.Tail = n
}
l.Len--
return
}
}
}The whole program main.go Show
package main
import "fmt"
type Node[T any] struct {
Value 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, Next: l.Head}
l.Head = n
if l.Tail == nil {
l.Tail = n
}
l.Len++
}
func (l *List[T]) PushBack(v T) {
n := &Node[T]{Value: v}
if l.Tail == nil {
l.Head, l.Tail = n, n
} else {
l.Tail.Next = n
l.Tail = n
}
l.Len++
}
func (l *List[T]) Remove(target *Node[T]) {
if l.Head == target {
l.Head = target.Next
if l.Tail == target {
l.Tail = nil
}
l.Len--
return
}
for n := l.Head; n.Next != nil; n = n.Next {
if n.Next == target {
n.Next = target.Next
if l.Tail == target {
l.Tail = n
}
l.Len--
return
}
}
}
// Print walks from the head, which is the only direction a singly linked
// list can go.
func (l *List[T]) Print() {
var vals []any
for n := l.Head; n != nil; n = n.Next {
vals = append(vals, n.Value)
}
fmt.Println(vals...)
}
func main() {
l := &List[int]{}
l.PushBack(10)
l.PushBack(20)
l.PushBack(30)
l.Print()
// Walking is the only way through a list: start at the head and follow
// Next. There is no index and no way back.
n := l.Head
fmt.Println("head:", n.Value)
fmt.Println("next:", n.Next.Value)
l.Remove(l.Head)
l.Print()
}Traversal only runs forward from Head to nil. Removing the middle node here means walking past it once to find its predecessor.
$ go run main.go
10 20 30
head: 10
next: 20
20 30