Linked list introduction

Linked lists

An array stores its elements in one contiguous block, so you can jump to index i instantly. A linked list stores each element in its own box — a node — and each node points to the next one. The nodes can live anywhere in memory; the chain of pointers is what keeps them in order, like a scavenger hunt where each clue tells you where to find the next one.

The node

In Go a singly linked list node looks like:

ListNode:
    value
    next   // reference to the next node, or nothing if this is the last one

Val is the data; Next points to the following node, or is nil at the end of the list. You hold a list by holding its head (the first node). The list 1 → 2 → 3 is a head node with Val: 1 whose Next is a node with Val: 2, and so on, ending in Next: nil.

What's it good for?

Cheap insert/remove at a known position — just rewire a couple of pointers, no shifting elements around like an array needs.
No fixed capacity — grow one node at a time.

The trade-off: no random access. To reach the 5th element you have to follow Next five times — O(n) — whereas an array jumps there in O(1). Linked lists also spend extra memory on all those pointers.

The two moves you'll use constantly

Almost every linked-list algorithm is built from:

Traverse — walk node by node following Next until you hit nil.
Rewire — change a node's Next to splice nodes in or out.

The next lesson drills both. Throughout this section, lists are written as space-separated values, e.g. 1 2 3 for 1 → 2 → 3, and an empty line is the empty list.