What a linked list is
A linked list is a sequence of values stored in separate objects called nodes. Each node holds one value and a reference to the next node. The list itself is just a reference to the first node, called the head. The last node's reference to the next node is null, which marks the end.
head
|
v
[1 | *]-->[2 | *]-->[3 | null]
A list has no indexes. To reach the third value you start at the head and follow the links twice. That is the main difference from an array, and it explains most of what makes linked lists fast at some things and slow at others.
Nodes in TypeScript
A node is a small class with a value and a link. The linked-list lessons use a ListNode with the fields val and next:
class ListNode {
val: number;
next: ListNode | null;
constructor(val?: number, next?: ListNode | null) {
this.val = val === undefined ? 0 : val;
this.next = next === undefined ? null : next;
}
}
The type of next is ListNode | null: either another node or nothing. Both constructor parameters are optional, so new ListNode() makes a node with value 0 and no next node, and new ListNode(2, c) makes a node with value 2 that points at c.
Building the list 1, 2, 3 from the back:
const c = new ListNode(3);
const b = new ListNode(2, c);
const head = new ListNode(1, b);
Traversal
To visit every node, keep a variable that points at the current node and move it forward until it becomes null:
let node: ListNode | null = head;
const seen: number[] = [];
while (node !== null) {
seen.push(node.val);
node = node.next;
}
console.log(seen.join(" -> "));
This prints 1 -> 2 -> 3. Inside the loop, node is a real node, because the loop condition has ruled out null. The same loop shape counts nodes, searches for a value or sums them up. It always takes O(n) time, because each node is visited once.
Moving forward is the only free direction. A node has no reference to the one before it, so you can't step back. Algorithms that need the previous node keep a second variable for it, as the reversal lesson does with prev.
Insertion and deletion
Changing a list means changing links. Nothing else moves.
- Insert at the front:
const newHead = new ListNode(0, head);. The new node points at the old head, and it becomes the new head. This isO(1), however long the list is. - Insert after a given node: point the new node at
b.nextfirst, then pointb.nextat the new node:const x = new ListNode(9, b.next); b.next = x;. The order matters. If you changedb.nextfirst, you'd lose the rest of the list. - Delete the node after
b:b.next = b.next.next;. The skipped node is no longer reachable, and the garbage collector reclaims it. This isO(1)once you holdb.
Starting from 0 -> 1 -> 2 -> 3, inserting 9 after the node holding 2 gives 0 -> 1 -> 2 -> 9 -> 3, and deleting the node after it brings back 0 -> 1 -> 2 -> 3.
The constant-time cost applies only to the change itself. Finding b in the first place takes a walk from the head, which is O(n).
Linked list or array
| Operation | Linked list | Array |
|---|---|---|
| Read the k-th element | O(k), by walking | O(1) |
| Insert or delete at the front | O(1) | O(n), the rest shifts |
| Insert or delete after a node you hold | O(1) | O(n) in the middle |
| Find a value | O(n) | O(n) unsorted |
In everyday TypeScript, the built-in Array is the right default, and the engines make it fast. Linked lists matter for learning to think in references, and in interview problems where you are handed nodes and asked to rearrange them in O(1) extra space. Note that a TypeScript Array is not a linked list, whatever its name suggests for other languages.
Gotchas
- Reading through
null. Writingnode.next.valwhennode.nextisnullthrows "Cannot read properties of null (reading 'val')". Check before you step, or use optional chaining:last.next?.valgivesundefinedinstead of throwing. The lessons compile withstrictoff, so the compiler doesn't always warn you about such reads. The error appears at run time. - Losing the rest of the list. Overwriting a
nextlink before you have saved where it pointed makes the following nodes unreachable. Save the old value in a variable first. - Accidental cycles. If some node's link points back to an earlier node, a traversal loop never reaches
nulland never finishes. A reversal that forgets to cut the old head's link produces exactly this. - Losing the head. If you move the
headvariable itself while walking, you lose the start of the list. Walk with a separate variable. - The empty list. It is just
null. A function that takeshead: ListNode | nullhas to handle that case, or its first access ofhead.nextthrows. - Types are erased. The
ListNode | nullannotations help your editor and the compiler, but at run time there are only objects andnull.
The dummy node trick
Removing the head is awkward, because the head has no node before it whose link you could change. A common fix is a dummy node: create const dummy = new ListNode(), set dummy.next = head, and work with the node before the one you examine. Now every node, including the old head, has a predecessor. At the end, return dummy.next, which is the new head. The next lessons use this pattern.
Key takeaways
- A list is a head reference plus nodes that each point to the next one;
nullends the list. - You reach elements by walking, so reading position
kcostsO(k). - Insertion and deletion at a known node are
O(1), because only links change. - Always save a link before overwriting it, and guard against
null. - A dummy node removes the special case for the head.