Python LinkedList — nodes, links, inserting and deleting without losing the queue (and why the order of two lines changes everything)

While preparing for the second FP2 exam I wrote insert_front in two lines. Both lines were correct. The problem was that I wrote them the other way round. I ran the program and the terminal started spitting out Ana → Ana → Ana → Ana… non-stop, until I pressed Ctrl+C. No error, no traceback: just a node pointing to itself and the rest of the list gone. That day I understood that with a LinkedList it is not enough to know what to do: the order matters.

Linked lists (in FP2 we call them LinkedList or linked structures) are the topic where you can really tell whether you understand Python references. In this article we build one from scratch with an example you will recognise: the reservation queue for a book in the faculty library. Laura reserves it, then Pablo, then Marta… and a member of staff can jump the queue (the rule is made up, just for the example). Every operation comes with its code, its real output and a drawing of which arrows change.

You come from Python testing with unittest, so you already know how to write classes, special methods and generators. All of that shows up here.

Before you start: what problem do linked structures solve?

A Python list stores its elements in consecutive boxes. That is why list[3] is instant: Python works out where box 3 is and jumps straight to it. But those consecutive boxes have a price: if you do list.insert(0, "Ana"), Python has to shift every element one place to the right to make room. With five reservations you don’t notice. With a million, you do.

A LinkedList does exactly the opposite. Each element lives in its own object, a node, which can be anywhere in memory. The only thing joining them is that each node knows who comes after it. The list only stores one reference: the first node, the head.

Look at the drawing: at the top, boxes [0] to [4] sit side by side; at the bottom, the nodes are scattered and only the arrows say which order they go in. That gives the two faces of the structure:

Operation	Python list	LinkedList
Access by position ([3])	Fast: O(1), direct jump	Slow: O(n), you traverse from the head
Insert at the front	Slow: O(n), shifts everything	Fast: O(1), two references change
Insert or delete in the middle (if you are already at the node before)	Slow: O(n)	Fast: O(1)
Insert at the back	Fast (almost always O(1))	O(n) if you only store the head
Search for a value	O(n)	O(n)
Memory per element	Less	More: each node also stores a reference

So is a LinkedList better? No. It is different. In FP2 we study it because it forces you to handle references by hand, which is the basis of trees, graphs and almost every serious data structure. And because it comes up in the exam.

What is a node: the basic unit

A node stores exactly two things:

• The value: the data (here, the name of whoever made the reservation).
• The reference to the next node, or None if it is the last one.

Nothing else. A node doesn’t know its position or how many there are in total. It only knows its data and who comes next. As it needs two attributes of its own, it is a class. Let’s create three loose nodes and chain them by hand:

class Node:
    def __init__(self, value, next_node=None):
        self.value = value          # the data: who made the reservation
        self.next_node = next_node  # reference to the next node (None if it is the last one)


# Three loose nodes: the reservation queue for a library book
laura = Node("Laura")
pablo = Node("Pablo")
marta = Node("Marta")

# We chain them by hand: each node stores a REFERENCE to the next one
laura.next_node = pablo
pablo.next_node = marta
# marta.next_node is still None: she is last in the queue

print(laura.value)                          # the data of the first node
print(laura.next_node.value)                # one hop: Pablo's node
print(laura.next_node.next_node.value)      # two hops: Marta's node
print(laura.next_node.next_node.next_node)  # three hops: there is no node any more
print(laura.next_node is pablo)             # is it the SAME object or a copy?
print(laura.next_node.next_node.next_node.value)  # one hop too many

Output:

Laura
Pablo
Marta
None
True
Traceback (most recent call last):
  File "nodes.py", line 22, in <module>
    print(laura.next_node.next_node.next_node.value)  # one hop too many
          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
AttributeError: 'NoneType' object has no attribute 'value'

Let’s go line by line, because the whole topic is here in miniature:

• laura.next_node.value gives Pablo: from Laura you follow one arrow and reach Pablo’s node.
• laura.next_node.next_node.value gives Marta: two arrows.
• laura.next_node.next_node.next_node gives None: Marta is the last one, her next_node was never changed.
• laura.next_node is pablo gives True. This is the key point: laura.next_node is not a copy of Pablo, it is the same object. If you change pablo.value, you will see it from Laura too.
• The last line asks for the .value of None and Python answers with an AttributeError. It is the most typical error of the whole topic: reaching None and carrying on.

This table tells you what you are holding at each step of the chain:

Expression	What it is	Type
laura	The first node	Node
laura.next_node	Pablo’s node	Node
laura.next_node.next_node	Marta’s node	Node
laura.next_node.next_node.next_node	Nothing: the end	NoneType
laura.next_node.next_node.next_node.value	Error	AttributeError

How nodes link in memory

What the drawings show as an arrow is, in Python, a reference: the memory address where the next node lives. When you write laura.next_node = pablo you don’t put Pablo inside Laura; you store in laura.next_node where Pablo is.

This has two consequences you will use all the time:

1. Nodes never move. Inserting or deleting means changing what one or two references point to. That is why it is so cheap.
2. A node that nothing points to disappears. Python removes it on its own (the garbage collector). If by mistake you stop pointing to the head, you lose the whole list, even though the nodes are still properly linked to each other.

Why is and not ==? Because == compares values and is asks “is it the same object?”. Two members can have the same name and be different nodes. In linked lists you almost always want to know whether you are at the same node, and that is is (you’ll see it in the exercises challenge).

The LinkedList class: what it needs

Handling loose nodes is awkward and dangerous. The normal thing is to wrap them in a class that stores the head and offers safe operations. This is how the class starts, just as it appears in the FP2 PDF:

class LinkedList:
    """Singly linked list, like the one in the FP2 PDF."""

    class Node:
        """Inner class: nodes are an implementation detail of the list."""
        def __init__(self, value, next_node=None):
            self.value = value
            self.next_node = next_node

    def __init__(self):
        self.__first = None    # head: reference to the first node (None if empty)
        self.__length = 0      # we keep it up to date so that len() does not have to traverse

Three design decisions:

• Node goes inside LinkedList (a nested class). Whoever uses the list doesn’t need to know nodes exist: they add and remove values. From the inside it is created with self.Node(...).
• __first and __length have two underscores: they are private. Nobody outside should be able to do list.__first = None and wipe out the queue. Further down you’ll see this has a catch when you inherit.
• We store the length instead of counting it. That way len() is O(1); in exchange, every operation that adds or removes has to update it. If you forget in one place, len() will lie (the exercises show a real case).

An empty list is simply __first = None. There is no “empty” node.

Operation 1: insert at the front

Inserting at the front takes two steps, and the order is not negotiable:

1. Create the new node pointing to the current head.
2. Move the head to the new node.

def insert_front(self, value):
    """Inserts at the front in O(1): link first, move the head afterwards."""
    self.__first = self.Node(value, self.__first)
    self.__length += 1

self.Node(value, self.__first) does step 1 when it creates the node, and the assignment to self.__first does step 2. As Python evaluates the right-hand side first, the order comes out right on its own. But when you write it in two lines, the order is up to you. This program does it both ways with the same queue:

class Node:
    def __init__(self, value, next_node=None):
        self.value = value          # the data: who made the reservation
        self.next_node = next_node  # reference to the next node (None if it is the last one)


def show(first, limit=6):
    """Walks the chain from first. Past limit nodes it stops (emergency brake)."""
    parts = []
    current = first
    while current is not None:
        if len(parts) == limit:      # a chain that never ends: we cut it here
            return " → ".join(parts) + " → … (doesn't end)"
        parts.append(current.value)
        current = current.next_node
    return " → ".join(parts + ["None"])


# Reservation queue: Laura → Pablo → Marta. Ana has to go in front.
first = Node("Laura", Node("Pablo", Node("Marta")))
print("Before:", show(first))

# WRONG: we move the head BEFORE linking the new node
original_head = first            # we keep it only to repeat the test
new_node = Node("Ana")
first = new_node                 # step 2 first: the head is already Ana...
new_node.next_node = first       # ...and "first" is NOT Laura any more: Ana points to herself
print("Wrong: ", show(first))

# RIGHT: first we link the new node to the current head and then we move the head
first = original_head
new_node = Node("Ana", first)    # step 1: Ana points to Laura
first = new_node                 # step 2: the head is Ana
print("Right: ", show(first))

Output:

Before: Laura → Pablo → Marta → None
Wrong:  Ana → Ana → Ana → Ana → Ana → Ana → … (doesn't end)
Right:  Ana → Laura → Pablo → Marta → None

The Wrong line is my story from the beginning, with a brake: show stops after 6 nodes, because otherwise the loop would never end. What happened?

• first = new_node moves the head to Ana before linking her.
• new_node.next_node = first meant “Ana points to the old head”, but first is already Ana. Result: Ana points to herself.
• Laura, Pablo and Marta are still linked to each other, but nothing points to Laura: the queue is lost.

Operation 2: insert at the back

As we only store the head, to insert at the back we have to reach the last node (the one with next_node = None) and hook the new one onto it:

def insert_back(self, value):
    """Inserts at the back in O(n): you have to reach the last node."""
    new_node = self.Node(value)
    if self.__first is None:                    # empty list: the new node is the head
        self.__first = new_node
    else:
        current = self.__first
        while current.next_node is not None:    # we stop AT the last one, not after it
            current = current.next_node
        current.next_node = new_node
    self.__length += 1

Two things worth looking at closely:

• The special case of the empty list. If __first is None, there is no last node to hook onto: the new one becomes the head. Forget this if and the while would ask for None.next_node and raise the AttributeError.
• The while condition is current.next_node is not None, not current is not None. We want to stop at the last one, not after it.

This is the trace when Iván is inserted at the back of Ana → Laura → Pablo → Marta:

Lap	current	current.next_node	Does the loop go on?
Before	Ana	Laura	Yes
1	Laura	Pablo	Yes
2	Pablo	Marta	Yes
3	Marta	None	No: Marta is the last one
After	Marta	Iván	(the new one is hooked on)

And if you use the other condition? This happens:

class Node:
    def __init__(self, value, next_node=None):
        self.value = value          # the data: who made the reservation
        self.next_node = next_node  # reference to the next node (None if it is the last one)


first = Node("Laura", Node("Pablo"))

# WRONG: the while condition leaves current at None, not at the last node
current = first
while current is not None:
    current = current.next_node
current.next_node = Node("Marta")

Output:

Traceback (most recent call last):
  File "back_wrong.py", line 13, in <module>
    current.next_node = Node("Marta")
    ^^^^^^^^^^^^^^^^^
AttributeError: 'NoneType' object has no attribute 'next_node' and no __dict__ for setting new attributes

With while current is not None, the loop ends when current already is None, and you can’t give None a next_node. The message is long (since Python 3.13 it adds “and no __dict__ for setting new attributes”), but it says the usual thing: you’ve gone one too far.

Operation 3: traverse the list

Traversing always follows the same pattern: start at the head and move on with current = current.next_node until current is None. In the class we put it in __iter__, which is a generator (you saw it in iterators and generators):

def __iter__(self):               # lets you traverse it with for
    current = self.__first
    while current is not None:
        value = current.value
        current = current.next_node    # we move on BEFORE the yield pauses
        yield value

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

Thanks to __iter__, the list works in a for, in list(queue), in enumerate and in the " → ".join(...) of __str__. Notice that we move current on before the yield: the generator pauses at the yield, and if someone deletes the node it is on in the meantime, we already have the next one saved.

__len__ traverses nothing: it returns __length. That’s why len(queue) is instant even if the queue has a thousand reservations.

Operation 4: search for an element

Searching is traversing while comparing, and leaving as soon as you find it:

def contains(self, value):
    """True if value is in the list (traversal from start to end)."""
    current = self.__first
    while current is not None:
        if current.value == value:
            return True
        current = current.next_node
    return False

With __contains__ (which just calls contains) the in operator works too: "Pablo" in queue. It is O(n) in the worst case, just like a Python list: you have to look one by one.

Operation 5: delete an element

This is the hardest one to picture. The key idea: to delete a node you don’t touch it. You make the previous node skip it and point straight to the next one. The deleted node is left with nothing pointing to it and Python collects it.

The problem is that in a singly linked list you can’t go backwards: from the node you want to delete you don’t know which one is before it. That’s why we traverse with a pair: previous and current, which move together.

Case 1: delete the first one

The head has no previous node. It’s enough to move __first to the second node: self.__first = self.__first.next_node. If the list had a single node, the second one is None and the list ends up empty, which is exactly what we want.

Case 2: delete a node in the middle

previous is on Laura and current on Pablo. previous.next_node = current.next_node makes Laura point to Marta. Pablo still points to Marta, but it doesn’t matter: he is no longer in the chain.

Case 3: delete the last one

It is the same code as case 2: current.next_node is None, so previous.next_node becomes None and the previous node becomes the last one. No separate if needed.

The full method:

def remove(self, value):
    """Removes the first occurrence of value. Raises ValueError if it is not there."""
    if self.__first is None:
        raise ValueError(f"{value} is not in the list")
    if self.__first.value == value:          # case 1: it is the head
        self.__first = self.__first.next_node
        self.__length -= 1
        return
    previous = self.__first                  # cases 2 and 3: we look for its PREVIOUS node
    current = self.__first.next_node
    while current is not None:
        if current.value == value:
            previous.next_node = current.next_node   # previous skips over current
            self.__length -= 1
            return
        previous = current                   # both move on, always as a pair
        current = current.next_node
    raise ValueError(f"{value} is not in the list")

This is the trace of remove("Pablo") on Laura → Pablo → Marta → Iván:

Moment	previous	current	current.value == "Pablo"?
Before the loop	Laura	Pablo	Yes: Laura now points to Marta and return

A single lap. If we were looking for Iván, the pair would move twice (Pablo/Marta, Marta/Iván) before finding him. And if the value isn’t there, current reaches None, the loop ends and the ValueError is raised, just like list.remove does on a normal list.

The complete class

Everything together, with a test that goes through the three deletion cases and a value that doesn’t exist:

class LinkedList:
    """Singly linked list, like the one in the FP2 PDF."""

    class Node:
        """Inner class: nodes are an implementation detail of the list."""
        def __init__(self, value, next_node=None):
            self.value = value
            self.next_node = next_node

    def __init__(self):
        self.__first = None    # head: reference to the first node (None if empty)
        self.__length = 0      # we keep it up to date so that len() does not have to traverse

    def insert_front(self, value):
        """Inserts at the front in O(1): link first, move the head afterwards."""
        self.__first = self.Node(value, self.__first)
        self.__length += 1

    def insert_back(self, value):
        """Inserts at the back in O(n): you have to reach the last node."""
        new_node = self.Node(value)
        if self.__first is None:                    # empty list: the new node is the head
            self.__first = new_node
        else:
            current = self.__first
            while current.next_node is not None:    # we stop AT the last one, not after it
                current = current.next_node
            current.next_node = new_node
        self.__length += 1

    def remove(self, value):
        """Removes the first occurrence of value. Raises ValueError if it is not there."""
        if self.__first is None:
            raise ValueError(f"{value} is not in the list")
        if self.__first.value == value:             # case 1: it is the head
            self.__first = self.__first.next_node
            self.__length -= 1
            return
        previous = self.__first                     # cases 2 and 3: we look for its PREVIOUS node
        current = self.__first.next_node
        while current is not None:
            if current.value == value:
                previous.next_node = current.next_node   # previous skips over current
                self.__length -= 1
                return
            previous = current                      # both move on, always as a pair
            current = current.next_node
        raise ValueError(f"{value} is not in the list")

    def contains(self, value):
        """True if value is in the list (traversal from start to end)."""
        current = self.__first
        while current is not None:
            if current.value == value:
                return True
            current = current.next_node
        return False

    def is_empty(self):
        return self.__first is None

    def __len__(self):
        return self.__length

    def __contains__(self, value):    # lets you write: value in list
        return self.contains(value)

    def __iter__(self):               # lets you traverse it with for
        current = self.__first
        while current is not None:
            value = current.value
            current = current.next_node    # we move on BEFORE the yield pauses
            yield value

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

    def __repr__(self):
        return f"LinkedList({list(self)})"


queue = LinkedList()
print("Empty:", queue, "| len =", len(queue), "| is_empty =", queue.is_empty())
for member in ["Laura", "Pablo", "Marta"]:
    queue.insert_back(member)         # normal reservations: at the back of the queue
print("Reservations:", queue)
queue.insert_front("Ana")             # Ana is staff: her reservation jumps ahead
print("Ana in front:", queue)
queue.insert_back("Iván")
print("Iván at the back:", queue, "| len =", len(queue))
print("Does Pablo have a reservation?", "Pablo" in queue)
print("Does Nora have a reservation?", queue.contains("Nora"))
queue.remove("Ana")                   # case 1: the head
print("Without Ana:", queue)
queue.remove("Pablo")                 # case 2: one in the middle
print("Without Pablo:", queue)
queue.remove("Iván")                  # case 3: the last one
print("Without Iván:", queue)
print(repr(queue), "| len =", len(queue))
try:
    queue.remove("Nora")
except ValueError as error:
    print("ValueError:", error)
for turn, member in enumerate(queue, start=1):
    print(f"Turn {turn}: {member}")

Output:

Empty: None | len = 0 | is_empty = True
Reservations: Laura → Pablo → Marta → None
Ana in front: Ana → Laura → Pablo → Marta → None
Iván at the back: Ana → Laura → Pablo → Marta → Iván → None | len = 5
Does Pablo have a reservation? True
Does Nora have a reservation? False
Without Ana: Laura → Pablo → Marta → Iván → None
Without Pablo: Laura → Marta → Iván → None
Without Iván: Laura → Marta → None
LinkedList(['Laura', 'Marta']) | len = 2
ValueError: Nora is not in the list
Turn 1: Laura
Turn 2: Marta

Check the output against the drawings: Ana goes in at the front (O(1)), Iván at the back (traverses four nodes), and then Ana (case 1), Pablo (case 2) and Iván (case 3) leave. Two reservations remain and len knows it without traversing: 5 − 3 = 2. When we try to remove Nora, who never reserved, the ValueError is raised with the same message we built in the raise.

Inheriting from LinkedList: the private attributes problem

In practice and in exams it is common to extend the LinkedList with a subclass (class ReservationQueue(LinkedList)). And here a trap appears that has nothing to do with nodes, but with how Python hides attributes with two underscores:

from linked_list import LinkedList


class ReservationQueue(LinkedList):
    def next_turn(self):
        """Who is first in the queue, without taking them out."""
        if self.__first is None:      # looks the same as inside LinkedList...
            return None
        return self.__first.value


queue = ReservationQueue()
queue.insert_back("Laura")
queue.insert_back("Pablo")
print(queue)
print(queue.next_turn())

Output:

Laura → Pablo → None
Traceback (most recent call last):
  File "subclass.py", line 16, in <module>
    print(queue.next_turn())
          ~~~~~~~~~~~~~~~^^
  File "subclass.py", line 7, in next_turn
    if self.__first is None:      # looks the same as inside LinkedList...
       ^^^^^^^^^^^^
AttributeError: 'ReservationQueue' object has no attribute '_ReservationQueue__first'

Why does it fail if __first exists? Because Python renames attributes starting with two underscores (it’s called name mangling): inside LinkedList, self.__first is stored as self._LinkedList__first. Inside ReservationQueue, self.__first becomes self._ReservationQueue__first, which doesn’t exist. Look at the message: it looks for exactly that name.

There are two sensible ways out:

from linked_list import LinkedList


class ReservationQueue(LinkedList):
    def next_turn(self):
        """Option A: the real name of the parent's private attribute."""
        first = self._LinkedList__first
        return None if first is None else first.value

    def next_turn_public(self):
        """Option B: only the public interface (the for of __iter__)."""
        for member in self:
            return member          # the first one the traversal gives
        return None                # the queue was empty


queue = ReservationQueue()
print(queue.next_turn(), queue.next_turn_public())
queue.insert_back("Laura")
queue.insert_back("Pablo")
print(queue.next_turn(), queue.next_turn_public())
print([name for name in vars(queue)])     # this is what the attributes are really called

Output:

None None
Laura Laura
['_LinkedList__first', '_LinkedList__length']

• Option A: write the real name, self._LinkedList__first. It works and it is what you will do when you need to touch the nodes (reversing, sorting…). It is ugly on purpose: it reminds you that you are reaching into the parent.
• Option B: use only the public interface (for, len, in, insert_…). If reading the values is enough, it is the cleanest.

vars(queue) confirms it: the attributes are called _LinkedList__first and _LinkedList__length. In the practice we use both options.

LinkedList versus Python list: when to use each

I want to…	Python list?	LinkedList?
Access by position many times	Yes	No
Insert and remove a lot at the front (a queue)	No	Yes
Insert in the middle when I’m already at the node before	No	Yes
Sort, filter, slicing, all done for me	Yes	No: you program it
Learn to handle references	No	Yes

In everyday Python you will use lists (and collections.deque if you need a queue that is fast at both ends). You program the LinkedList to understand what is underneath, and because the exam will ask you for new methods on it.

Common mistakes with LinkedList

Watch it step by step in Python Tutor

Python Tutor runs the code line by line and draws every object with its arrows. For linked lists it is the best there is: you literally see the references. Go there, choose Python 3 and paste this program, which puts Ana between Laura and Pablo:

class Node:
    def __init__(self, value, next_node=None):
        self.value = value          # the data: who made the reservation
        self.next_node = next_node  # reference to the next node (None if it is the last one)

laura = Node("Laura")
pablo = Node("Pablo")
marta = Node("Marta")
laura.next_node = pablo
pablo.next_node = marta
first = laura

# Ana squeezes in between Laura and Pablo: link first, move afterwards
ana = Node("Ana", laura.next_node)   # Ana points to Pablo
laura.next_node = ana                # Laura points to Ana

current = first
while current is not None:
    print(current.value)
    current = current.next_node

Output:

Laura
Ana
Pablo
Marta

What to watch step by step:

1. After the three nodes are created you’ll see three loose boxes with next_node: None. They are not a list yet.
2. With laura.next_node = pablo and pablo.next_node = marta the arrows appear. No node has moved.
3. At ana = Node("Ana", laura.next_node), Ana’s arrow already goes to Pablo, and Laura still points to Pablo: two arrows to the same node, and nothing goes wrong.
4. At laura.next_node = ana, only one arrow changes. Pablo and Marta don’t notice: that is the beauty of linked structures.
5. Now break it on purpose: create ana = Node("Ana"), do laura.next_node = ana and then ana.next_node = laura.next_node. As laura.next_node is already Ana, Ana points to herself and Pablo and Marta are left with nothing pointing to them.

Quick summary

Operation	How	Cost
Insert at the front	self.__first = self.Node(value, self.__first)	O(1)
Insert at the back	Empty case; otherwise while current.next_node is not None and hook on	O(n)
Traverse	current = current.next_node until None (in __iter__)	O(n)
Search	Traverse and return True when found	O(n)
Delete	Head apart; the rest with the previous/current pair	O(n)
Length	__length attribute kept up to date	O(1)

Three ideas to keep:

1. A node only knows its value and who comes next. The list only knows where the head is.
2. Link first, move afterwards. Changing a reference in the wrong order leaves nodes with nothing pointing to them.
3. To delete you need the previous node. That’s why you traverse as a pair, and why the head is a separate case.

In the LinkedList practice we extend this class with three library programs: loan statistics, reversing the reservation queue in place and sorting the catalogue by insertion.

Next step: practicePython LinkedList practice — loans, the reservation queue backwards and the sorted catalogue (three library programs)

Did this article help you? Here is how you can support SergioLearns →