Linked Lists & Recursion

Nodes joined by pointers

A linked list is a chain of nodes. Each node holds a value and a pointer to the next node. The list itself is just a pointer to the first node (the head); the last node's Next is nil.

In Go you model a node with a struct that points to itself: type Node struct { Val int; Next Node }. That Node is a pointer — a node doesn't contain the next node (that would be infinitely large), it points to it. Nodes can live anywhere in memory, stitched together by their Next pointers.