A linked list stores a sequence in nodes rather than in contiguous memory. Each node holds a value and a pointer to the next node. Insertion or removal can relink nodes without shifting other elements, though reaching an indexed position requires following links. Go slices remain the simpler choice for most production uses. section 6.1 section 6.3
Listing 6.1 A generic node implementation
type node[T any] struct { #1
value T #2
next *node[T] #3
}
A type parameter keeps the stored value and the next node the same type: node[T any] holds value T and next *node[T]. section 6.1
The list keeps a head pointer and a size. Its concrete type uses T comparable so operations such as Remove and Contains can test values for equality. This is narrower than a generic List[T any] interface: a LinkedList can implement that interface for types permitted by its comparable constraint. section 6.1 section 6.3
Listing 6.12 Defining a generic List interface
type List[T any] interface {
Collection[T]
Get(index int) (T, error)
Set(index int, item T) error
Insert(index int, item T) error
RemoveAt(index int) (T, error)
}
The List interface combines collection operations with indexed Get, Set, Insert, and RemoveAt methods. It defines what callers can do without requiring them to use a linked-list implementation. section 6.3
Adding an item walks to the tail and links a new node, or sets the head if the list is empty. Removing a matching item links the preceding node to the following one; removing the head changes the head pointer instead. Both changes update the stored size. section 6.3
Listing 6.16 Finishing the interface implementation
func (l *LinkedList[T]) Set(index int, item T) error {
if index < 0 || index >= l.size { #1
return errors.New("index out of bounds")
}
curr := l.head
for i := 0; i < index; i++ { #2
curr = curr.next
}
curr.value = item #3
return nil
}
func (l *LinkedList[T]) Insert(index int, item T) error {
if index < 0 || index > l.size { #4
return errors.New("index out of bounds")
}
n := &node[T]{value: item} #5
if index == 0 { #6
n.next = l.head
l.head = n
} else {
curr := l.head
for i := 0; i < index-1; i++ { #7
curr = curr.next
}
n.next = curr.next #8
curr.next = n
}
l.size++ #9
return nil
}
func (l *LinkedList[T]) RemoveAt(index int) (T, error) {
var zero T
if index < 0 || index >= l.size { #10
return zero, errors.New("index out of bounds")
}
var prev *node[T]
curr := l.head
for i := 0; i < index; i++ { #11
prev = curr
curr = curr.next
}
if prev == nil { #12
l.head = curr.next
} else {
prev.next = curr.next #13
}
l.size-- #14
return curr.value, nil
}
Insert checks the index, handles insertion at the head, or walks to the preceding node before changing links. Set also walks from the head and reports an out-of-bounds index. section 6.3
Using a typed list
A LinkedList[int] can hold 10, 20, and 30; Insert(1, 15) places a value between the first two items. The same list can then be read with Get, changed with Set, and shortened with RemoveAt. section 6.3
