Hack University
Course outline · 0% complete

0/29 lessons0%

Course overview →

Build One: Push, Find, Delete

lesson 4-2 · ~15 min · 11/29

A real LinkedList class

Time to wrap the chain in a class — and the point is bigger than linked lists. The pointer-rewiring discipline you practice here is the exact skill every linked structure runs on: the deque in unit 5, the tree nodes of unit 7, LRU caches, and memory allocators inside the systems you use daily. It is also a favorite interview probe, because rewiring pointers in the wrong order silently destroys data. The list object stores just self.head. The star operation is push_front, adding at the front in O(1), the exact operation arrays are worst at:

  1. Create a node.
  2. Point its next at the current head.
  3. Make it the new head.

Two pointer assignments, regardless of length. No shifting, ever.

The order of steps 2 and 3 matters. If you overwrite self.head first, you lose your only reference to the old chain, and the rest of the list is gone. Pointer code is all about not dropping the chain.

Code exercise · python

Run this. We push 3, then 2, then 1 to the front, so the chain reads 1 → 2 → 3. `to_list` is the traversal loop from lesson 4-1, collecting values into a Python list so we can print them.

Find and delete

find(value) traverses from the head, counting positions, and returns the index of the first match or −1. There is no index formula and no way to jump ahead, so a front-to-back scan is the only option: O(n), the same linear search you ran in lesson 1-1.

delete(value) is where pointers earn their keep. To unlink a node you rewire the pointer of the node before it:

current.next = current.next.next

The skipped node is simply no longer reachable (Python's garbage collector reclaims it). No shifting. But there are two cases:

  • the head itself matches: move self.head forward instead, since no node sits before the head
  • otherwise: walk with current looking one node ahead (current.next.value), so you still hold the node before the match

Code exercise · python

Your turn: implement `find` and `delete`. `find` returns the index of the first match or -1. `delete` unlinks the first matching node and returns True, or False if the value is absent. Handle the head case separately in `delete`.

Quiz

In `delete`, why does the loop compare `current.next.value` instead of `current.value`?

Reversal: the pointer-discipline test

Reversing a linked list in place is the canonical exercise for one reason: it forces you to rewire every pointer in the chain without ever losing your grip on the rest of it. It is also probably the single most-asked linked list interview question.

The in-place method walks the chain once with three names:

  • prev: the already-reversed part (starts as None)
  • current: the node being rewired
  • nxt: a saved copy of current.next

At each node: save nxt = current.next FIRST (the moment you flip current.next backward, the old forward link is gone — this is the save-before-overwrite rule from push_front again), then point current.next at prev, then advance both names. When current falls off the end, prev is the new head. One pass, O(n) time, O(1) extra memory: no second list, just three variables.

Code exercise · python

Your turn: implement `reverse(head)` in place with the prev/current/nxt walk and return the new head. `build` and `to_list` are done for you.