Nodes and Pointers

Recall from lesson 2-3 why inserting at the front of an array is O(n): every existing item must shift one slot right to make room.

Contiguous storage has no gaps, so opening a space at index 0 slides all n items over, and the cost is unavoidable given the layout.

Linked lists exist to fix exactly this. They trade the contiguous block for a chain, which makes front insertion O(1), and this unit is largely about what that trade costs elsewhere.

Chains instead of blocks

A linked list stores items in separate nodes scattered anywhere in memory. Each node holds two things.

• A value.
• A pointer called next, referring to the following node, or None at the end of the chain.

A pointer is just an address, like the ones computed in lesson 2-1, except now stored inside the data rather than derived from a formula. The list itself keeps only one thing, a pointer to the first node, called the head.

Because nodes do not need to sit side by side, inserting one never shifts anything. You create the node and rewire one or two pointers, and every other node stays exactly where it was.

The price is that the index formula is gone. Reaching item i means traversing, following next pointers one hop at a time from the head, so reading by position becomes O(n).

That is a genuine trade rather than an upgrade. The array's contiguity bought O(1) indexing and cost O(n) front insertion, and the linked list reverses both sides of that deal.

Building and walking a chain by hand

A node class is tiny, just a value and a pointer. Three nodes wired together make a list.

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

a = Node("to")
b = Node("do")
c = Node("list")
a.next = b
b.next = c

current = a
while current is not None:
    print(current.value)
    current = current.next

Output

to
do
list

Each node starts with next as None, and the two assignments a.next = b and b.next = c are what create the chain. Nothing else connects them, and c.next stays None, which is how the traversal knows where to stop.

The traversal itself is the pattern to memorize, because every linked list operation is a variation on it. Start current at the head, do something with current.value, then move on with current = current.next, until current is None.

Notice that the loop never mentions a length or an index. It cannot, because neither exists here, and the only thing the code can ask a node is what comes next.

Two traversal utilities

length hops through the whole chain counting nodes, and value_at takes exactly i hops and stops.

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

head = Node(10)
current = head
for v in [20, 30, 40, 50]:
    current.next = Node(v)
    current = current.next

def length(head):
    count = 0
    current = head
    while current is not None:
        count += 1
        current = current.next
    return count

def value_at(head, i):
    current = head
    for _ in range(i):
        current = current.next
    return current.value

print("length:", length(head))
print("value at 0:", value_at(head, 0))
print("value at 3:", value_at(head, 3))

Output

length: 5
value at 0: 10
value at 3: 40

The build loop at the top is the standard way to grow a chain: keep a current pointer at the last node, attach a new node to its next, then move current onto it.

Both functions share the same skeleton and differ only in the work done per hop. In length that work is count += 1, and the loop runs to the end. In value_at a while is not needed at all, since for _ in range(i) takes exactly i hops, and value_at(head, 0) takes zero hops and returns the head's own value.

The cost of value_at(head, 3) is three pointer follows, and the cost of value_at(head, 4999) would be 4,999. That linear relationship is the thing the next block puts a name to.

Reading the 700th value from a 1,000-node linked list costs O(n), because you must follow next pointers 700 times from the head.

Nodes are scattered across memory, so no formula can compute where node 700 lives. The address of each node is known only to the node before it, which means the only route to node 700 runs through nodes 0 through 699.

This has a consequence beyond slow indexing. It kills binary search from lesson 1-3, which depends on jumping to the middle of a range in O(1). A sorted linked list is still sorted, but the halving trick has no way to reach the midpoint cheaply, so searching it stays O(n) even with the data in order.

That is why sorted-data structures in later units are built on trees rather than chains: a tree keeps the cheap-middle property that halving requires.