Linked Lists Part 1 — Node Class & Traversal

By the end of this lesson you can:

• Define a Node class with value and next.
• Wire nodes into a singly-linked list.
• Traverse the list to print, count, find, or sum its contents.
• Explain why list[i] on a linked list is O(n) and on a Python list is O(1).

Each node is a small box:

   ┌───┬───┐    ┌───┬───┐    ┌───┬───┐    ┌───┬───┐
   │ 1 │ ●─┼──→ │ 2 │ ●─┼──→ │ 3 │ ●─┼──→ │ 4 │ Nil│
   └───┴───┘    └───┴───┘    └───┴───┘    └───┴───┘

The list is a reference to the FIRST node (the head).
Each node knows only its value and the next node.
The last node's "next" is None — the end marker.

Compare to a Python list: contiguous memory, index access in O(1), but resizing is expensive. Linked list: scattered nodes, index access is O(n) (walk every node), but insertion/deletion in the middle is O(1) if you have the surrounding node.

The Node — two attributes

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

    def __repr__(self):
        return f"Node({self.value!r})"

That's it. A Node holds a value and a reference to the next node (or None if it's the last). The whole linked list is just nodes pointing at each other.

Building a list manually

# Build 1 → 2 → 3
n3 = Node(3)
n2 = Node(2, next=n3)
n1 = Node(1, next=n2)

# The "head" of the list is n1
head = n1

# Walk it
current = head
while current is not None:
    print(current.value)
    current = current.next
# 1
# 2
# 3

Traversal is a while current is not None: current = current.next loop. The body does whatever you need; the loop walks the chain.

A LinkedList wrapper

To make this usable, wrap it. The wrapper holds the head; the user calls methods.

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

    def push_front(self, value):
        """O(1) — new head."""
        self.head = Node(value, next=self.head)

    def __iter__(self):
        current = self.head
        while current is not None:
            yield current.value
            current = current.next

    def __len__(self):
        n = 0
        for _ in self:
            n += 1
        return n

    def __repr__(self):
        return "LinkedList[" + " → ".join(str(v) for v in self) + "]"

__iter__ as a generator makes the list usable in for, sum, list(), comprehensions — all the iterable goodies from PY-L3-26-28.

Three common traversals

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


def find(head, target):
    cur = head
    while cur is not None:
        if cur.value == target:
            return cur
        cur = cur.next
    return None


def sum_of(head):
    total = 0
    cur = head
    while cur is not None:
        total += cur.value
        cur = cur.next
    return total

Same walking shape, different operation. All O(n) — every node visited.

Why list[i] on a linked list is O(n)

There's no random access. To reach index 5, you walk 5 nodes. Python's list is a contiguous array — index access is constant time. That's why we can't cheaply slice a linked list either; we'd have to walk the start, then walk to the end of the slice.

Why bother, then?

Insertion / deletion in the middle is O(1) if you have a reference to the node — no shifting needed. Python lists need O(n) for that. For workloads with lots of middle-edits and few index accesses, linked lists win. For everything else (most code), Python's built-in list is better.

Save as linked_list.py:

# linked_list.py — singly-linked list, read-only operations

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

    def __repr__(self):
        return f"Node({self.value!r})"


class LinkedList:
    def __init__(self, iterable=None):
        self.head = None
        if iterable is not None:
            for item in reversed(list(iterable)):
                self.push_front(item)

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

    def append(self, value):
        """O(n) — find the tail and add."""
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
            return
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = new_node

    def __iter__(self):
        cur = self.head
        while cur is not None:
            yield cur.value
            cur = cur.next

    def __len__(self):
        return sum(1 for _ in self)

    def __contains__(self, value):
        return any(v == value for v in self)

    def __getitem__(self, i):
        """O(n) — walk to index i."""
        if i < 0:
            raise IndexError("Negative indices not supported")
        for n, v in enumerate(self):
            if n == i:
                return v
        raise IndexError("LinkedList index out of range")

    def __repr__(self):
        return "[" + " → ".join(str(v) for v in self) + "]"


# Build and explore
ll = LinkedList([10, 20, 30, 40, 50])
print(ll)                  # [10 → 20 → 30 → 40 → 50]
print(len(ll))             # 5
print(20 in ll)            # True
print(ll[2])               # 30  (O(n) lookup)
print(sum(ll))             # 150
print(list(ll))            # [10, 20, 30, 40, 50]
ll.push_front(0)
print(ll)                  # [0 → 10 → 20 → 30 → 40 → 50]
ll.append(60)
print(ll)                  # [0 → 10 → 20 → 30 → 40 → 50 → 60]

Read the diff

One Node class, one LinkedList class with eight methods. __iter__ as a generator gives all the iterable conveniences. __contains__ and __getitem__ use the iterator. push_front is O(1) (just reassign head); append is O(n) (walk to tail). Tomorrow we'll add insert and delete.

A linked list is a chain of nodes. Each node holds a value and a pointer to the next. The whole list is a reference to the head node; the end is marked by None. Traversal is a while current is not None: current = current.next loop. Indexing is O(n). Push-front is O(1). Linked lists shine for middle insertions (tomorrow) and as a teaching device for understanding what Python's list hides.