Python for Data Structures: the Tools This Module Uses

self is the object being worked on, and it is the first parameter of every method. It is not optional and it is not passed at the call: Node(10) calls __init__(new_object, 10).

nxt=None is a default. Node(10) and Node(10, None) mean the same thing, so a node made without a successor has one anyway: None.

The field is called nxt and not next on purpose. next is a built-in function in Python, and a field called next shadows nothing dangerous inside a class, but a local variable called next in a traversal does. Using nxt everywhere avoids having to remember which is safe. Some books write next and some write link; all three mean the same thing and an examiner will accept any of them.

None, and what it means in a structure

None is Python's single "there is nothing here" value. In this module it means three different things, and telling them apart is the whole of getting a linked structure right.

class Node:
    def __init__(self, data, nxt=None):
        self.data = data
        self.nxt = nxt


head = None
print("empty?", head is None)

head = Node(1, Node(2, Node(3)))

count = 0
here = head
while here is not None:
    count += 1
    here = here.nxt

print("nodes:", count)
print("last node holds:", 3, "and its nxt is", head.nxt.nxt.nxt)

empty? True
nodes: 3
last node holds: 3 and its nxt is None

while here is not None is the traversal, and it appears in nine of the ten exercises. Read it as "while I am still standing on a node". The three lines of that loop are worth learning by heart:

here = head
while here is not None:
    ...
    here = here.nxt

Forgetting here = here.nxt gives an infinite loop, and it is the single commonest mistake in this module. If a program in the examination hall never finishes, that line is where to look.

Use is None, not == None. is asks whether it is the same object, which is what is meant; == calls a comparison method, which a class of your own may define and get wrong. Python itself warns about == None in some tools, and it is the house style everywhere.

The reference, which is why a node can be shared

This is the idea that makes every structure in this module work, and it is worth one program of its own.

class Node:
    def __init__(self, data, nxt=None):
        self.data = data
        self.nxt = nxt


a = Node("first")
b = a                      # NOT a copy: another name for the same node

b.data = "changed"
print("a.data is now", a.data)
print("are they the same object?", a is b)

c = Node("first")
print("c looks like a, but is it a?", a is c, "and equal?", a.data == c.data)

a.data is now changed
are they the same object? True
c looks like a, but is it a? False and equal? False

A variable holds a reference, not an object. b = a makes a second name for one node, so a change through either name is seen through both. That is why head = node.nxt moves a pointer and copies nothing, and why a linked list of a million nodes can be traversed without copying anything.

The last line is worth a second look. a.data was changed to "changed" before c was made, so a.data == c.data is False. If the change had not happened they would be equal in content and still not the same object, and is and == would disagree. is asks about identity and == asks about content, and every chapter in this module needs both: is None for the end of a list, == for searching.

A readable __repr__, which saves hours of debugging

Print a node without help and this is what you get:

class Bare:
    def __init__(self, data):
        self.data = data


class Node:
    def __init__(self, data, nxt=None):
        self.data = data
        self.nxt = nxt

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


print(str(Bare(5)).split(" at ")[0] + " at 0x...>")
print(Node(5))
print([Node(1), Node(2), Node(3)])

<__main__.Bare object at 0x...>
Node(5)
[Node(1), Node(2), Node(3)]

The first line is what a class without __repr__ prints: its name and its address, which tells you nothing and is different on every run. Every class in this module defines __repr__, and the last line is why: printing a list of nodes then shows the nodes.

If a class defines only __repr__, print falls back on it, which is why one method is enough for this module. !r inside an f-string means "use repr on this", which is what puts the quotation marks round a string and leaves a number bare.

Raising an exception rather than returning a sentinel

Every structure in this module has operations that can fail: popping an empty stack, dequeueing an empty queue, deleting a key that is not there. There are two ways to report it and only one is right.

class Stack:
    def __init__(self):
        self.items = []

    def push(self, x):
        self.items.append(x)

    def pop(self):
        if not self.items:
            raise IndexError("pop from an empty stack")
        return self.items.pop()


s = Stack()
s.push(7)
print("popped", s.pop())

try:
    s.pop()
except IndexError as e:
    print("the second pop said:", e)

popped 7
the second pop said: pop from an empty stack

Returning None or -1 for an empty stack is the wrong answer, and the reason is short: None is a value somebody may legitimately have pushed. A stack holding None and an empty stack would then be indistinguishable, and the caller has no way to tell a failure from a success.

An exception cannot be mistaken for a value. It also cannot be ignored: a caller who forgets to check a returned -1 carries on with a wrong number, while a caller who forgets to catch an exception gets a stack trace that names the line.

The exceptions this module uses, and what each is for:

Those are the same ones Python's own containers raise, which is the point: a structure of yours should fail the way a list or a dictionary fails, so that nobody has to learn your conventions.

try:
    [].pop()
except IndexError as e:
    print("list.pop on empty:", e)

try:
    {}["missing"]
except KeyError as e:
    print("dict['missing']:", e)

try:
    (1, 2)[5]
except IndexError as e:
    print("tuple[5]:", e)

list.pop on empty: pop from empty list
dict['missing']: 'missing'
tuple[5]: tuple index out of range

Those three messages are identical on Python 3.12, 3.13 and 3.14, which is how this page can print them. Some of Python's messages have changed between versions, and where a chapter in this module prints one, it has been run on all three.

The list against the node chain

Python's list is not an array and not a linked list. It is a dynamic array: a block of references that is reallocated larger when it fills up. Knowing that decides which operations are cheap.

items = [10, 20, 30]

items.append(40)          # cheap: put it at the end
items.insert(0, 5)        # dear: everything moves up one
print(items)

print("item 2 is", items[2])   # cheap: arithmetic on the address
items.pop(0)                   # dear: everything moves down one
print(items)

[5, 10, 20, 30, 40]
item 2 is 20
[10, 20, 30, 40]

That table is the answer to MU's bullet about static against dynamic, and it is measured rather than asserted in [Practical 12: Singly Linked Lists].

The cost of "walk n nodes" and "everything moves" is written O(n) and read "order n": the work grows in proportion to the number of items. "One step" is O(1), constant time, meaning the work does not depend on how many items there are. Those two symbols and O(log n) for a balanced tree are all the notation this module needs.

Measuring how long something takes

Several exercises ask for two approaches to be compared, so the measurement has to be trustworthy.

from time import perf_counter

n = 20000

start = perf_counter()
front = []
for i in range(n):
    front.insert(0, i)          # at the front: everything moves
at_front = perf_counter() - start

start = perf_counter()
back = []
for i in range(n):
    back.append(i)              # at the end
at_back = perf_counter() - start

print(f"{n} inserts at the front: {at_front:.4f} seconds")
print(f"{n} appends at the end  : {at_back:.4f} seconds")
print(f"the front was {at_front / at_back:.0f} times slower")
print("and both built the same list:", front == list(reversed(back)))

20000 inserts at the front: 0.1795 seconds
20000 appends at the end  : 0.0018 seconds
the front was 99 times slower
and both built the same list: True

Two rules about measuring, both learned the hard way in Module 1 of this book.

Print the answer, or the compiler and the interpreter may skip the work. The last line of that program compares the two lists, so neither loop can be optimised away and the reader can see that both really did build the same thing.

One measurement is not a result. The figures above are from one run on one machine and the ratio changes from run to run; what is stable is that inserting at the front of a list is far slower than appending, and that the gap grows with n. Where a chapter in this module prints a time, the timing digits are marked as varying and it is the shape that is proved, never the exact number.

perf_counter is the right clock for this: it is monotonic, it has the finest resolution the machine offers, and it measures elapsed time rather than processor time. time.time is a wall clock that can go backwards when the machine syncs its clock, and should not be used for measuring.

For a small operation that takes microseconds, the standard library has a better tool:

import timeit

setup = "items = list(range(1000))"

front = timeit.timeit("items.insert(0, 99)", setup=setup, number=1000)
back = timeit.timeit("items.append(99)", setup=setup, number=1000)

print(f"1000 inserts at the front: {front:.5f} seconds")
print(f"1000 appends at the end  : {back:.5f} seconds")

1000 inserts at the front: 0.00253 seconds
1000 appends at the end  : 0.00005 seconds

timeit runs the statement many times, uses the best clock available and turns the garbage collector off, so it is the tool to reach for when the thing being measured is fast.

The shape of every chapter in Module 2

Each of MU's ten exercises is one journal entry and one chapter, laid out the same way:

1. Aim, in MU's own words.
2. What you need to know: the structure explained before any code, with a picture in text.
3. The class, built up operation by operation, with the reasoning for each.
4. The run, which is what the program actually printed on all three interpreters.
5. The cost of each operation, as a table, because the examination asks for it.
6. Where it is used, which is MU's own third bullet in most of the exercises.
7. Procedure, Result, Where marks are lost, For the journal, Quick revision

and Questions you should be able to answer.

Procedure

1. Check your Python version with python3 --version. Anything from 3.8 onwards runs everything

in this module.

1. Type the Node program into a file and run it. Add a fourth node and count again.
2. Delete the line here = here.nxt and run it. Stop the program with Ctrl+C and note the

message, because you will see it again.

1. Add __repr__ to a class of your own and print a list of three of them.
2. Write a Stack whose pop returns None when empty, push None on to it, and satisfy

yourself that the caller cannot tell the two cases apart.

1. Run the timing program with n of 10000, 20000 and 40000, and note that the ratio grows.

Result

The tools Module 2 uses were set up and tried: a class with __init__ and self, None as the end of a structure, the reference that lets two names share one node, __repr__ for a readable printout, an exception rather than a sentinel for a failed operation, and perf_counter and timeit for measuring. Inserting at the front of a Python list was measured to be many times slower than appending, which is the fact the linked list exercise rests on.

Where marks are lost

• Using Python's own list, dictionary or deque for an exercise that asks for the structure to be built.

No marks, however correct the answer.

• Forgetting here = here.nxt, so the traversal never ends.
• == None instead of is None.
• No __repr__, so the output is a list of memory addresses and the examiner cannot see what

the program built.

• Returning None or -1 from a failed operation instead of raising an exception.
• Forgetting self in a method's parameter list, which gives a TypeError naming the wrong

number of arguments.

• Claiming a speed difference from one run without saying it was one run.

For the journal

This chapter is groundwork rather than one of the twenty, so it needs no journal entry of its own unless your teacher asks for one. If they do: the Node program, the traversal, the __repr__ before and after, and the timing figures with your own machine's numbers.

Quick revision

• A structure is a node class and a container class. __init__ is the constructor and

self is the object.

• None means empty list, last node, or missing child, depending on where it is. Test it with

is None.

• The traversal is here = head, while here is not None, and here = here.nxt at the bottom.

Leaving the last line out is an infinite loop.

• A variable holds a reference. b = a is a second name for one object, not a copy. is asks

about identity, == about content.

• Every class defines __repr__, or printing a list of nodes prints addresses.
• A failed operation raises: IndexError for a position, KeyError for a key, ValueError

for a bad value. Returning None is wrong because None may be a real item.

• Python's list is a dynamic array: cheap at the end, dear at the front. A linked list is the

opposite.

• O(1) means the work does not grow with the number of items; O(n) means it grows in proportion.
• Measure with perf_counter for anything slow and timeit for anything fast, never time.time,

and print the answer so the work cannot be skipped.

• Every listing in this module was run on Python 3.14, 3.13 and 3.12 and printed the same thing on

all three.

Questions you should be able to answer

1. What is self, and why is it the first parameter of every method? It is the object the method was called on. Python passes it automatically, so s.push(7) calls push(s, 7), and a method written without it fails with a TypeError about the number of arguments.

2. What does None mean in a linked list? Three things depending on where it is: an empty list when the head is None, the last node when a node's nxt is None, and a missing child when a tree node's left or right is None.

3. Why is None rather than == None? Because is compares identity, which is what is meant, while == calls a comparison method that a class of your own may define and get wrong.

4. b = a where a is a node. How many nodes are there? One. b is a second name for the same object, so a change through either name is visible through both.

5. Why does every class in this module define __repr__? Because without it, printing an object gives its class name and its address, which is different on every run and says nothing. With it, printing a list of nodes shows what the nodes hold.

6. Why should pop on an empty stack raise rather than return None? Because None is a value somebody may have pushed, so the caller could not tell an empty stack from a stack holding None. An exception cannot be mistaken for a value and cannot be silently ignored.

7. Which is cheaper in a Python list, append or insert(0, x), and why? append. A Python list is a dynamic array, so inserting at the front moves every other item up one, while appending usually writes into spare room at the end. Measured here, 20000 inserts at the front took about eighty times as long as 20000 appends.

8. What does O(1) mean, and what does O(n) mean? O(1) means the work does not depend on how many items there are. O(n) means it grows in proportion to the number of items.

9. Which clock should be used for timing, and which should not? time.perf_counter for anything slow and timeit for anything fast. Not time.time, which is a wall clock and can move backwards when the machine adjusts it.