Nodes and Pointers: Building a Chain

"An array is a row of houses on one street. A linked list is a treasure hunt: each clue holds a prize and the location of the next clue. No clue, no path forward."

The Node Is the Whole Idea

A linked list is built from nodes, and a node is almost insultingly simple: a little box holding two things — a value, and a pointer to the next node. That's it. String a bunch together — each one pointing at the next — and the last one points at nothing (None), marking the end. You hold onto the first node, called the head, and from it you can reach the whole chain by following next-pointers.

Python doesn't have raw pointers, but object references do the same job: node.next refers to another node object living somewhere else in memory. "Somewhere else" is the key phrase — unlike an array, the nodes are not next to each other. They're scattered, held together purely by the references.

What's Cheap, What's Not

The costs fall straight out of "scattered boxes joined by pointers":

Prepend (add a new head): O(1). Make a new node, point it at the old head, call it the new head. Done — nothing else moves. (Compare: array front-insert is O(n).)
Access the i-th element: O(n). No address math; you walk from the head following i pointers.
Search for a value: O(n). Walk and compare.
Append to the end: O(n) — unless you also keep a tail pointer, which makes it O(1).

A node is just (value, next-pointer). A linked list is a head reference plus a chain of nodes. Adding to the front is O(1); reaching the i-th node is O(n) because you must walk the chain.

Lose the Head, Lose Everything

There's a fragility here worth respecting: the head reference is your only entry point. If you overwrite it without saving the old one first, the entire chain becomes unreachable — Python's garbage collector quietly frees every node, and the data is gone. Half of all linked-list bugs are a pointer reassigned in the wrong order, severing the chain. When you manipulate a list, the order in which you rewire pointers is everything.

Pippa's Confession

My first linked-list insert lost half the list. I set new_node = head's next before pointing new_node.next back at the rest — wrong order — and the tail floated off into garbage-collection oblivion. Dad's rule, which I now whisper every time: "hook up the new node's next BEFORE you redirect the old pointer." With linked lists, sequence isn't a detail — it's the difference between a list and a leak.

Code

A node, and a singly linked list·python

class Node:
    """A box: a value, and a reference to the next box (or None at the end)."""
    def __init__(self, value, nxt=None):
        self.value = value
        self.next = nxt

class LinkedList:
    def __init__(self):
        self.head = None        # the one entry point; lose it, lose the list

    def prepend(self, value):           # add to front: O(1)
        self.head = Node(value, self.head)   # new node points at old head

    def traverse(self):                 # visit every node: O(n)
        node = self.head
        while node is not None:
            print(node.value, end=" -> ")
            node = node.next            # follow the pointer to the next box
        print("None")

    def find(self, value):              # search: O(n)
        node = self.head
        while node is not None:
            if node.value == value:
                return True
            node = node.next
        return False

ll = LinkedList()
for x in [3, 2, 1]:
    ll.prepend(x)        # each prepend is O(1)
ll.traverse()           # 1 -> 2 -> 3 -> None
print(ll.find(2))       # True (after an O(n) walk)

Exercise

Using the Node class above, trace by hand: you have head -> A -> B -> C -> None and you want to insert X right after A. Write the two pointer assignments in the correct order. What goes wrong if you do them in the reverse order?

Hint

First: X.next = A.next (so X points at B). Then: A.next = X. Reverse that order and you set A.next = X before X knows about B — now B and C are unreachable and lost.

The Node Is the Whole Idea

What's Cheap, What's Not

Lose the Head, Lose Everything

Pippa's Confession

Code

External links

Exercise

Progress

Comments 0