What a linked list is
A linked list stores a sequence of values in separate nodes. Each node holds one value and a pointer to the next node. The list itself is just a pointer to the first node, called the head. The last node's pointer is nil, which marks the end.
A slice is the usual way to hold a sequence in Go, and it keeps its elements side by side in one block of memory. A linked list does the opposite: its nodes can live anywhere, and the pointers join them. That difference decides what each structure is good at.
A node in Go
Go has no classes, so a node is a struct that refers to its own type through a pointer:
type ListNode struct {
Val int
Next *ListNode
}
Next is a *ListNode: either the address of another node or nil. A struct can't contain itself by value, since it would have infinite size, but it can contain a pointer to one. The zero value of a pointer is nil, so var head *ListNode is already a valid empty list.
The expression &ListNode{Val: 5} creates a node and returns its address. Go's garbage collector frees nodes that nothing points to, so there is nothing to release by hand.
Traversal
To visit every node, start at the head and follow Next until it is nil. Go has no while, so this is a for loop with a condition:
func printList(head *ListNode) {
for cur := head; cur != nil; cur = cur.Next {
fmt.Print(cur.Val, " -> ")
}
fmt.Println("nil")
}
The loop variable cur is a copy of the pointer, so moving it never changes the list. Reaching the n-th node means following n pointers; there is no way to jump straight to it as with nums[n].
Inserting and deleting
Inserting at the front takes constant time: make a node whose Next is the old head and return it as the new head. Inserting at the back means walking to the last node first:
func pushFront(head *ListNode, val int) *ListNode {
return &ListNode{Val: val, Next: head}
}
func pushBack(head *ListNode, val int) *ListNode {
node := &ListNode{Val: val}
if head == nil {
return node
}
cur := head
for cur.Next != nil {
cur = cur.Next
}
cur.Next = node
return head
}
Both functions return the head, because an insertion can change which node comes first. The caller must store the result: head = pushFront(head, 1). Deleting a node means making the previous node skip it:
func deleteValue(head *ListNode, val int) *ListNode {
if head == nil {
return nil
}
if head.Val == val {
return head.Next
}
for cur := head; cur.Next != nil; cur = cur.Next {
if cur.Next.Val == val {
cur.Next = cur.Next.Next
break
}
}
return head
}
The loop stops at the node before the one to delete, because only that node's Next can be changed. Deleting the head is a special case and returns the second node.
Reversing a list rewires every pointer to face backward. Three variables are enough: the previous node, the current one and the saved next one:
func reverse(head *ListNode) *ListNode {
var prev *ListNode
for head != nil {
next := head.Next
head.Next = prev
prev = head
head = next
}
return prev
}
Building a list with pushBack(nil, 2), pushBack of 3, then pushFront of 1 and printing it gives:
1 -> 2 -> 3 -> nil
After adding 4 at the back, deleting 3 and reversing, the list prints as 1 -> 2 -> 3 -> 4 -> nil, then 1 -> 2 -> 4 -> nil, then:
4 -> 2 -> 1 -> nil
Linked list versus slice
| Operation | Linked list | Slice |
|---|---|---|
| Read the i-th element | O(i) | O(1) |
| Insert at the front | O(1) | O(n), elements shift |
| Insert at the back | O(n) walking, O(1) with a tail pointer | O(1) amortized with append |
| Insert or delete after a known node | O(1) | O(n), elements shift |
| Search for a value | O(n) | O(n) |
A linked list wins when you keep adding or removing near nodes you already hold. A slice wins whenever you need to jump to an index. In practice slices are the default in Go, because their contiguous layout is also friendlier to the CPU cache. Linked lists appear in problems because pointer manipulation is the skill being tested. The standard library also offers a doubly linked list in the container/list package.
Common mistakes in Go
- Dereferencing nil. Reading
head.Valorhead.Nexton anilpointer panics withinvalid memory address or nil pointer dereference. Check fornilbefore using a node, especiallycur.Next.Next, which needs bothcur.Nextandcurto be non-nil. - Losing the rest of the list. In
reverse, overwritinghead.Nextbefore saving it innextcuts off every node after it. - Ignoring the returned head. Calling
pushFront(head, 1)without assigning the result leaves the caller'sheadunchanged, because Go passes the pointer by value. - Forgetting the empty list. Every operation should work when
headisnil. - Cycles. If a node's
Nextpoints back to an earlier node, a traversal loop never ends.
Key takeaways
- A node holds a value and a
*ListNode; the list is its head pointer, andnilends it. - Traversal follows
Nextin afor cur != nilloop. - Insertion and deletion at a known position change a few pointers; finding the position takes
O(n). - Indexing is
O(n), unlike a slice. - Most linked list bugs are
nildereferences and lost pointers, so draw the nodes and arrows before coding.