Classes for nodes

Linked lists, trees and graphs are built from small objects that refer to each other. This lesson shows how to make such objects in Python with a class.

A class is a new kind of value

Python has built-in kinds of value: numbers, strings, lists. A class lets you define a new kind. Each value made from a class is called an object, and each object has its own named parts, called attributes.

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

p = Point(2, 5)
p.x          # 2
p.y = 7      # attributes can be changed

Point(2, 5) makes a new object and then runs __init__ on it. Inside the class, self is the object being set up. So self.x = x stores the value of x in the new object.

A node class

A node is an object that holds a value and a reference to another node. Joining nodes this way makes a chain, called a linked list. The last node refers to None, which marks the end.

Step through the figure. It builds three nodes, then visits them in order. Each box is a node: the value on the left, and on the right a dot with an arrow for next. The tags under the nodes show which node each name refers to.

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

head = Node(3)
head.next = Node(8)
head.next.next = Node(5)

cur = head
while cur is not None:
    print(cur.value)
    cur = cur.next

Names refer to objects

Just as with lists, a name refers to an object; it does not contain it. cur = head makes cur refer to the same node as head. Moving cur later does not move head. But changing an attribute through either name changes the one shared object:

cur = head
cur.value = 99
print(head.value)     # 99: same node

cur = cur.next        # cur moves on
print(head.value)     # still 99: head did not move

Use is to ask whether two names refer to the same object, and is None to test for the end of a chain. == asks a different question: whether two values are equal.

Walking along the nodes

Every linked structure in the course uses this loop. Learn how it is written:

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

Printing your objects

By default, print(node) shows something like <Node object at 0x7f…>, which does not help. Define __repr__ to choose what is shown:

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

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

print(Node(3))      # Node(3)

The f"…" is an f-string. Python replaces anything in curly brackets with its value. Here __init__ also has a default for next, so Node(3, other) makes a node that points to other in one step.