The Node Class: Build and Traverse
25 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)A linked list stores items in a chain, not in a block. Each item knows only where the next one is. This lesson builds that chain and walks it, and says honestly when Python has something better.
A node holds a value and a link
Node is one object in a linked list. It holds a value and a reference to the next node, or None when it is the last one.
A linked list keeps its items in small separate objects called nodes. Each node holds a value and a reference to the next node, so the items form a chain.
class Node: def __init__(self, value, next=None): self.value = value self.next = next
head = Node(10, Node(20, Node(30)))print(head.value)print(head.next.value)print(head.next.next.next)Example 1 · Follow the links by hand
class Node: def __init__(self, value, next=None): self.value = value self.next = next
first = Node("T-101")second = Node("T-102")third = Node("T-103")first.next = secondsecond.next = thirdprint(first.next.value, third.next)T-102 None
What this code does
- Three tickets are made as separate nodes, then joined by setting
next. first.nextis the second node, so.valuereads T-102. The third node has nothing after it, so itsnextis None.
head is the only name we keep. The last node has next set to None, which marks the end. next is also a built-in function, but as an attribute name it is harmless, and it is the name interviews use.
Build a list from values
Linked list is a chain of nodes in which each node points to the next one. The list is known by its head, the first node, and an empty list is just None.
You rarely type nodes by hand. Walk the values backwards, and give each new node the list built so far as its next. The last node made becomes the head.
def build(values): head = None for value in reversed(values): head = Node(value, head) return head
head = build([4, 8, 15])Example 2 · Build from a list and print arrows
class Node: def __init__(self, value, next=None): self.value = value self.next = next
def build(values): head = None for value in reversed(values): head = Node(value, head) return head
def to_list(head): out = [] node = head while node: out.append(node.value) node = node.next return out
head = build([4, 8, 15, 16])print(" -> ".join(str(v) for v in to_list(head)))4 -> 8 -> 15 -> 16
What this code does
buildturns a normal list into nodes, andto_listwalks them back out.- The arrows are only printing. In memory each node holds just one link.
head = None is the empty list. Each round makes a node whose next is the old head, then makes that node the new head. This takes O(n) time.
Traverse with a loop
Traversal is visiting every node of a list once, from the head to the end. It follows the next links one by one and takes O(n) time.
Traversing means visiting every node once. Start a variable at the head and move it with node = node.next until it becomes None.
def to_list(head): out = [] node = head while node: out.append(node.value) node = node.next return outExample 3 · Length, sum and largest in one pass
class Node: def __init__(self, value, next=None): self.value = value self.next = next
def build(values): head = None for value in reversed(values): head = Node(value, head) return head
head = build([30, 50, 10, 25, 15])count = total = 0biggest = head.valuenode = headwhile node: count += 1 total += node.value biggest = max(biggest, node.value) node = node.nextprint(count, total, biggest)5 130 50
What this code does
- One walk answers three questions, so the cost is O(n) time and O(1) space.
- There is no
len(head): a chain has to be walked to be counted.
Example 4 · Find a value by position
class Node: def __init__(self, value, next=None): self.value = value self.next = next
def build(values): head = None for value in reversed(values): head = Node(value, head) return head
def get(head, index): node = head while node and index > 0: node = node.next index -= 1 return node.value if node else None
head = build([7, 14, 21, 28])print(get(head, 2), get(head, 9))21 None
What this code does
- A list reaches
items[2]in one step. A linked list must follow two links first, sogetcosts O(n). - A position past the end walks off the chain and returns None instead of crashing.
while node: works because a node is truthy and None is falsy. Use a separate variable such as node, so head still names the start. Time is O(n).
Why Python rarely uses one
A Python list is already a fast dynamic array: items[i] is O(1) and append is cheap. A linked list has no index and needs one object per value, so real programs seldom use it. Interviews do, to test how well you handle references.
from collections import deque
queue = deque([10, 20, 30])queue.appendleft(5)queue.pop()print(queue)Example 5 · Wrap the nodes in a class and get for-loops free
class Node: def __init__(self, value, next=None): self.value = value self.next = next
class LinkedList: def __init__(self): self.head = None self.tail = None self.size = 0
def append(self, value): node = Node(value) if self.tail: self.tail.next = node else: self.head = node self.tail = node self.size += 1
def __iter__(self): node = self.head while node: yield node.value node = node.next
def __len__(self): return self.size
marks = LinkedList()for mark in [72, 85, 90]: marks.append(mark)print(list(marks), sum(marks), len(marks))[72, 85, 90] 247 3
What this code does
__iter__is a generator, sofor,listandsumall work on the list.- Keeping a
tailmakesappendO(1). Interviews usually give only the head and the bare Node class.
When you need fast changes at both ends, Python gives you collections.deque. Learn linked lists to think clearly about references, which is what interviewers check.
Next step
Check your understanding
10 quick questions