Nodes, Pointers & the Dummy Head

Linked Lists, lesson 1 of 3

Nodes, Pointers & the Dummy Head

Build, walk and edit a singly linked list, and use a dummy head to kill edge cases.

12 min, 0 of 3 activities solved

View cheatsheet

Getting Python ready… examples can run in a moment.

A singly linked list is a chain of small objects. Each node holds a value and a reference to the next node; the last one points to None:

head
 |
 v
[1] -> [2] -> [3] -> None

All you ever hold is head. To reach the third node you must walk: head.next.next. That's the big trade compared with a Python list:

  • Index access is O(n) (no lst[i] jump).
  • Insert / delete next to a node you hold is O(1): you rewire one or two next pointers, nothing shifts.

Interview problems use linked lists to test one thing: can you move pointers around without losing part of the chain?

Example

A tiny ListNode and two helpers

while node: is the standard walk: it stops after the last node because node becomes None. Lesson examples define ListNode themselves; in the practice problems it already exists and tests are written as plain lists like [1, 2, 3].

Quiz

What does this print?

Deleting is "skip the next node". To remove a node you need its predecessor: prev.next = prev.next.next.

That's awkward when the node to delete is the head: it has no predecessor, so you need a special case, and the function must return a new head.

The fix is a dummy (sentinel) head: a fake node placed before the real head. Now every real node has a predecessor, and the answer is always dummy.next:

dummy -> [6] -> [1] -> [6] -> [2] -> None
  ^
 prev starts here
Example

Delete every 6, with a dummy head

No if head is None or "is it the head?" branches. Notice prev only moves when we keep a node: after a skip, the new prev.next still needs checking (think [6, 6]).

Quiz

You build a result list by appending nodes after dummy = ListNode(). What should the function return?

Exercise

Remove duplicates from a sorted list

The list is sorted, so equal values sit next to each other. Write dedupe(head) that keeps only the first node of each run of equal values and returns the head:

1 -> 1 -> 2 -> 3 -> 3 becomes 1 -> 2 -> 3.

Do it by rewiring next pointers (no new lists).