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 practiced here is the exact skill every linked structure runs on: the deque in unit 5, the tree nodes of unit 7, LRU caches, and the memory allocators inside the systems you use daily.

It is also a favorite interview probe, because rewiring pointers in the wrong order destroys data silently rather than raising an error.

The list object stores just self.head. The star operation is push_front, which adds 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 and is not interchangeable. Overwrite self.head first and you have lost your only reference to the old chain, so every remaining node becomes unreachable in one line. Pointer code is largely the practice of not dropping the chain.

push_front in a class

Pushing 3, then 2, then 1 to the front produces a chain reading 1, 2, 3, since each new node lands ahead of the previous one.

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def push_front(self, value):
        node = Node(value)
        node.next = self.head
        self.head = node

    def to_list(self):
        out = []
        current = self.head
        while current is not None:
            out.append(current.value)
            current = current.next
        return out

lst = LinkedList()
for v in [3, 2, 1]:
    lst.push_front(v)
print(lst.to_list())

Output

[1, 2, 3]

The two lines inside push_front are the whole operation. node.next = self.head links the new node to the old chain, and only then does self.head = node make it the front.

to_list is the traversal loop from lesson 4-1, collecting values so they can be printed. It exists purely for inspection, and it is worth noting that it costs O(n) while every push_front cost O(1).

The empty-list case needs no special handling. When self.head is None, the first push sets node.next = None, which is exactly right for a single-node chain.

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, making it O(n), the same linear search as lesson 1-1.

delete(value) is where pointers earn their keep. Unlinking a node means rewiring the pointer of the node before it.

current.next = current.next.next

The skipped node simply becomes unreachable, and Python's garbage collector reclaims it. Nothing shifts, and the cost of the rewiring itself is O(1) once you have found the right place.

Two cases have to be handled separately.

  • The head itself matches, in which case self.head moves forward, since no node sits before the head to rewire.
  • Otherwise, walk with current looking one node ahead by testing current.next.value, so you still hold the node before the match when you find it.

That asymmetry, where the first element needs its own branch, shows up in nearly every singly linked structure. Some implementations avoid it with a permanent dummy node at the front, which trades one wasted node for one fewer special case.

delete("b"): walk with current on the node BEFORE the matchabccurrentcurrent.nextnext = Nonecurrent.next = current.next.nextabcone pointer rewired, nothing shiftedunreachable
Deletion rewires one pointer on the previous node. The skipped node becomes unreachable, and no other node moves.

find and delete in full

Both operations traverse, and delete handles the head as its own case.

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def push_front(self, value):
        node = Node(value)
        node.next = self.head
        self.head = node

    def find(self, value):
        current = self.head
        i = 0
        while current is not None:
            if current.value == value:
                return i
            current = current.next
            i += 1
        return -1

    def delete(self, value):
        if self.head is None:
            return False
        if self.head.value == value:
            self.head = self.head.next
            return True
        current = self.head
        while current.next is not None:
            if current.next.value == value:
                current.next = current.next.next
                return True
            current = current.next
        return False

    def to_list(self):
        out = []
        current = self.head
        while current is not None:
            out.append(current.value)
            current = current.next
        return out

lst = LinkedList()
for v in ["c", "b", "a"]:
    lst.push_front(v)
print(lst.to_list())
print("find b:", lst.find("b"))
print("find z:", lst.find("z"))
print("delete b:", lst.delete("b"))
print(lst.to_list())
print("delete z:", lst.delete("z"))
print(lst.to_list())

Output

['a', 'b', 'c']
find b: 1
find z: -1
delete b: True
['a', 'c']
delete z: False
['a', 'c']

find is the traversal loop with a counter, returning i on a match and −1 after the loop ends without one.

delete opens with the two guards, an empty list and a matching head, before entering the general loop. That loop walks while current.next is not None and compares current.next.value, so current is always positioned on the node before the candidate.

The two delete results are worth comparing. Deleting b returned True and left ['a', 'c'], while deleting the absent z returned False and changed nothing, which is the behavior a caller needs in order to distinguish a removal from a no-op.

The loop compares current.next.value because unlinking a node requires rewiring the pointer of the node before it, so the walk has to stop one node early.

The unlink is current.next = current.next.next, an assignment made on the previous node. Standing on the matching node itself gives you nothing to assign to.

In a singly linked list there is no way to walk backward, since a node holds no reference to its predecessor. So if the traversal moved onto the match, the node that needs updating would already be unreachable, and recovering it would mean starting over from the head.

Looking one node ahead keeps the predecessor in hand at the exact moment it is needed. This is the structural reason the doubly linked list in the next lesson exists: a prev pointer removes the need for this whole maneuver.

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 is the already-reversed part, starting as None.
  • current is the node being rewired.
  • nxt is a saved copy of current.next.

At each node, save nxt = current.next first, then point current.next at prev, then advance both names.

The order of those first two steps is the whole exercise. The moment current.next is flipped backward, the old forward link is gone, so the only way to reach the rest of the chain is a copy made beforehand. It is the same save-before-overwrite rule that governed push_front.

When current falls off the end, prev holds the new head. One pass, O(n) time, and O(1) extra memory, since there is no second list anywhere, only three variables.

Reversing in place

The three-name walk, with build and to_list supplied for inspection.

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

def build(values):
    head = None
    for v in reversed(values):
        node = Node(v)
        node.next = head
        head = node
    return head

def to_list(head):
    out, current = [], head
    while current:
        out.append(current.value)
        current = current.next
    return out

def reverse(head):
    prev = None
    current = head
    while current is not None:
        nxt = current.next
        current.next = prev
        prev = current
        current = nxt
    return prev

head = build([1, 2, 3, 4, 5])
print("before:", to_list(head))
head = reverse(head)
print("after:", to_list(head))

Output

before: [1, 2, 3, 4, 5]
after: [5, 4, 3, 2, 1]

Inside the loop the order is everything. nxt = current.next must come before current.next = prev, or the rest of the chain is lost the instant the pointer flips. Then the two advances, prev = current and current = nxt, move the boundary one node along.

The loop runs until current is None, and at that moment prev holds the last real node visited, which is the reversed list's head. That is why the function returns prev rather than current, and forgetting it is the most common way this exercise goes wrong.

Also worth noting is what the caller must do. Since the old head becomes the new tail, the returned value has to be assigned back, which is why the example writes head = reverse(head).