The placeholder head trick

Linked lists Junior Python 3.13+ Reviewed By Best Latest Apps

Spot the bug

Which line misses the case where the first link has the value to remove?

  1. from typing import Any
  2. ​
  3. ​
  4. def drop_value(head: Any, x: int) -> Any:
  5. here = head
  6. while here and here.next:
  7. if here.next.val == x:
  8. here.next = here.next.next
  9. else:
  10. here = here.next
  11. return head

Choose an answer, then open Show answer below to check it.

Show answer
  • Answer: line 5 here = head

Starting at head means only links after the head are ever checked, so a matching head survives. Starting from a placeholder in front of the head fixes it.

30-second answer

It is an extra link placed in front of the real head. Every real link then has a predecessor, so removing or inserting at the head uses the same code as anywhere else. At the end you return placeholder.next. It costs one object and removes a whole class of edge-case bugs.

Practise saying it · 30 s. No recording, just a timer

Explain the placeholder head.

Say your answer out loud, then check which of these points you covered:

  • Extra link before the head
  • Head is no longer special
  • Return placeholder.next

Deep dive

Use it whenever the head might change: removals, merges, partitions, building a new chain.

A tail pointer next to it makes appending O(1).

Doubly linked caches often use a placeholder at both ends.

Common mistakes

  • Returning the placeholder itself instead of placeholder.next.
  • Giving the placeholder a value that can be confused with real data in comparisons.

Senior take & follow-ups

Say 'the placeholder means the head is not a special case'.

Follow-up questions

Think of your answer first, then open the hint.

  1. When is a placeholder unnecessary?

    Show hint

    When the head can never change, such as counting or searching.

  2. How do least-recently-used caches use this?

    Show hint

    A dict maps keys to links in a doubly linked chain with placeholders at both ends, so moves and evictions are O(1).

What each operation costs: Linked List · Singly Linked List · Doubly Linked List

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.