What a linked list is
A singly linked list is a chain of nodes. Each node stores a value and a reference to the next node. The last node's reference is null, which marks the end. The list as a whole is represented by a reference to its first node, the head. An empty list is just a null head.
The problems in this chapter all use the same node class, which looks like this:
class ListNode {
public int val;
public ListNode next;
public ListNode() {}
public ListNode(int val) { this.val = val; }
public ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
ListNode is a class, so it is a reference type. A variable of type ListNode holds a reference to a node, or null, and never a copy of the node. Assigning one variable to another makes both refer to the same node. The three constructors let you build a node empty, with a value, or with a value and its successor, so a three-node list can be built in one expression:
ListNode head = new ListNode(1, new ListNode(2, new ListNode(3)));
// 1 -> 2 -> 3 -> null
Traversal
To visit every node, start at the head and follow next until you reach null:
ListNode node = head;
while (node != null) {
Console.Write(node.val + " -> ");
node = node.next;
}
Console.WriteLine("null");
// prints: 1 -> 2 -> 3 -> null
Walking with a separate variable like node keeps head pointing at the start of the list. If you moved head itself, you would lose the beginning. The same pattern counts the nodes: add a counter and increment it inside the loop. Reaching the node at position k costs k steps, because there is no index to jump to.
Inserting and removing nodes
Changing a linked list means changing references, and no other elements move.
- Insert at the front. Create a node whose
nextis the old head, and treat it as the new head:head = new ListNode(0, head);. This takes constant time. - Insert after a node. Given a node
second, set the new node'snexttosecond.nextfirst, then setsecond.nextto the new node. The order matters. Reversing it would lose the rest of the list. - Remove the node after a given node. Skip over it:
node.next = node.next.next;. The skipped node is no longer reachable, so the garbage collector frees it.
Both an insertion and a removal take constant time once you hold the node before the position. Finding that node is what costs O(n).
Starting from 0 -> 1 -> 2 -> 3, inserting 9 after the node holding 1 gives 0 -> 1 -> 9 -> 2 -> 3, and removing the node after 1 brings back 0 -> 1 -> 2 -> 3.
Removing the head is a special case
The head has no node before it, so node.next = node.next.next can't remove it. You have to return or assign head.next instead. A common trick avoids this case: create a dummy node in front of the head, work with dummy.next as if it were any other link, and return dummy.next at the end. The problems in this chapter use that idea, and several others, such as walking two pointers at different speeds or reversing the links as you go.
Linked list or List<T>?
C# already has List<T>, which is backed by an array, and also a built-in LinkedList<T>, which is a doubly linked list. This chapter uses a hand-written ListNode because interview problems are stated that way and because working with the references is the point of the exercise. The trade-offs are:
| Operation | Linked list | List<T> (array-backed) |
|---|---|---|
Read the item at index k | O(k), walk from the head | O(1) |
| Insert or remove at the front | O(1) | O(n), items shift |
| Insert or remove next to a node you hold | O(1) | O(n), items shift |
| Search for a value | O(n) | O(n) |
In everyday C# code, List<T> is usually the better default, because contiguous memory is fast and indexing is constant time. Linked lists pay off when you do many insertions and removals at positions you already hold, and they are worth knowing because the same pointer-following skills apply to trees and graphs.
Mistakes to watch for
- Dereferencing
null. Readingnode.nextornode.valwhennodeisnullthrowsNullReferenceException. Checknode != nullbefore you follow a link, and checknode.next != nullbefore usingnode.next.val. - Losing the rest of the list. When you overwrite a
nextlink, first save the old target in a variable if you still need it. - Comparing the wrong thing.
a == bon two nodes checks whether they are the very same node, not whether their values are equal. Two separately created nodes holding 1 are not==. Comparea.val == b.valfor values. - Forgetting the empty list. A
nullhead is a valid input. Code that readshead.nextat the start fails on it. - Moving the head. Use a separate walking variable if you still need the start of the list afterwards.
How the chapter uses this
The problems that follow all take the head of a list and return a head. You will reverse a list by flipping its links, remove nodes by value and by position from the end, and find where two lists meet. In each one the work is the same: choose pointer variables, move them along the chain, and rewrite next links in an order that never loses a node.