Python LinkedList linked structures node insert delete traverse guide FP2

Linked structures in Python — LinkedList from scratch without the mystery

BySergio Alejandro Medina Ospina

Linked structures are the last FP2 block and the one that carries most weight in the second exam. Most people arrive here with the node concept not quite clicking — they understand the words separately but can’t visualise how the whole chain works.

This article starts from absolute zero: what a node actually is, how nodes connect in memory, and how every operation works with step-by-step diagrams.

What problem do linked structures solve?

When you use a Python list [1, 2, 3, 4, 5], Python stores all elements in consecutive memory positions — like a row of numbered boxes:

Position:  [0]  [1]  [2]  [3]  [4]
Value:      1    2    3    4    5

That has one enormous advantage: accessing element 3 is instant because Python calculates its memory position directly. But it has a hidden cost: inserting or deleting in the middle is expensive — Python has to shift every element that comes after.

Insert 99 at position 2:
Before:  [1]  [2]  [3]  [4]  [5]
         ← shift everything →
After:   [1]  [2]  [99] [3]  [4]  [5]

With a million elements, inserting at the front means moving a million values in memory.

Linked structures solve exactly this — inserting and deleting anywhere is always equally fast, without moving anything. The trade-off they pay for that: accessing a specific element requires traversing from the beginning.

Python list: fast index access   O(1), slow middle insert/delete O(n)
LinkedList:  slow index access   O(n), fast insert/delete anywhere O(1)*
(*if you already have the adjacent node)

In FP2 we don’t use LinkedList because it’s always better — we use it to understand how references work in memory, which is the foundation of the more complex data structures you’ll see in later courses.

What is a node — the basic unit

A node is the smallest piece of a linked structure. Each node contains exactly two things:

  • The value it stores (a number, a string, any object)
  • A reference to the next node — or None if it’s the last one

Nothing else. A node doesn’t know how many elements are in the list. It doesn’t know what position it’s at. It only knows its value and who comes after it.

┌──────────┬──────────┐
│  value   │   next   │
│    10    │  ──────► │ → (points to next node)
└──────────┴──────────┘

┌──────────┬──────────┐
│  value   │   next   │
│    10    │   None   │   (last node — no next)
└──────────┴──────────┘

Why it needs its own class: because it’s an object with two independent attributes that must exist separately in memory. It’s not a number, not a tuple — it’s an object that stores a value and knows who it points to:

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

Just that. The Node class has two attributes: value and next_node. The next_node parameter defaults to None because when you create a new node you usually don’t yet know who comes after it.

You can create and chain nodes manually to see how it works:

# Create three separate nodes
n1 = Node(10)
n2 = Node(20)
n3 = Node(30)

# Chain them manually
n1.next_node = n2
n2.next_node = n3
# n3.next_node remains None — it's the last

print(n1.value)                          # → 10
print(n1.next_node.value)               # → 20
print(n1.next_node.next_node.value)     # → 30
print(n1.next_node.next_node.next_node) # → None
n1                 n2                 n3
┌────┬────────┐   ┌────┬────────┐   ┌────┬──────┐
│ 10 │   ──────►  │ 20 │   ──────►  │ 30 │ None │
└────┴────────┘   └────┴────────┘   └────┴──────┘

That’s already a linked list — three nodes connected in a chain. All that’s missing is wrapping them in a class that manages the collection.

What you see as an arrow ──► in the diagram is actually a reference — the memory address where the next node lives. When you do n1.next_node = n2 you’re not copying n2 inside n1 — you’re storing n2’s memory address in n1.next_node.

This has an important consequence: nodes can live anywhere in memory, they don’t need to be in consecutive positions like a Python list. That’s why insertion is so cheap — you just change what two references point to, without moving any data:

RAM (example):
  address 0x1000: node value=10, next → 0x2500
  address 0x2500: node value=20, next → 0x0800
  address 0x0800: node value=30, next → None

Nodes scattered in memory — the chain links them with references

The Python LinkedList class

The LinkedList class doesn’t store elements directly — it stores a reference to the first node in the chain. That first node is called the head (or first). With just that one reference you can reach any element by following the next_node chain.

LinkedList
┌──────────┐
│  first  ──────► ┌────┬───┐   ┌────┬───┐   ┌────┬──────┐
└──────────┘      │ 10 │ ──────► 20 │ ──────► 30 │ None │
                  └────┴───┘   └────┴───┘   └────┴──────┘

Empty list:
┌──────────┐
│  first   │ → None
└──────────┘

In FP2 the Node class is defined inside LinkedList as a nested class — that’s how it appears in the course PDF. It’s an internal class because nodes are an implementation detail that shouldn’t be used from outside the list:

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

    def __init__(self):
        self.__first = None
        self.__length = 0

Insert at front — O(1)

Inserting at the front is the simplest and fastest operation. The process always has two steps: create the new node pointing to the current first, then make the new node become first.

Before inserting 5:
first ──► [10] ──► [20] ──► [30] ──► None

Step 1 — create node with next_node = current first:
new ──► [5] ──► [10] ──► [20] ──► [30] ──► None

Step 2 — first now points to new node:
first ──► [5] ──► [10] ──► [20] ──► [30] ──► None

The order of steps matters. If you update first before connecting the new node to the rest, you lose the reference to the existing list. Connect first, then update.

def insert_front(self, value):
    self.__first = self.Node(value, self.__first)
    self.__length += 1

This one-liner works because self.Node(value, self.__first) creates the new node already pointing to the current first — then self.__first = new_node makes it the new head. Both steps happen in the right order.

Insert at back — O(n)

Inserting at the back requires traversing the entire list to reach the last node — the one with next_node = None — and connecting the new node there.

Before inserting 40 at the back:
first ──► [10] ──► [20] ──► [30] ──► None

Traverse to last node (next_node is None):
                              current
first ──► [10] ──► [20] ──► [30] ──► None

Connect new node:
first ──► [10] ──► [20] ──► [30] ──► [40] ──► None

There’s a special case: if the list is empty, the new node becomes first directly:

def insert_back(self, value):
    new = self.Node(value)

    if self.__first is None:          # empty list — special case
        self.__first = new
    else:
        current = self.__first
        while current.next_node is not None:   # advance to last node
            current = current.next_node
        current.next_node = new        # connect new node at end
    self.__length += 1

while current.next_node is not None is the most important traversal pattern in LinkedList — memorise it because it appears in almost every operation.

Traverse — O(n)

Traversing the list node by node always follows the same pattern: start at first and advance with current = current.next_node until current is None.

first ──► [10] ──► [20] ──► [30] ──► None
current=10 → current=20 → current=30 → current=None → STOP
def __str__(self):
    """Display the list as: 10 → 20 → 30 → None"""
    return ' → '.join(str(v) for v in self) + ' → None'

def __len__(self):
    return self.__length

def __iter__(self):
    """Allows using the list in a for loop."""
    current = self.__first
    while current is not None:
        value = current.value
        current = current.next_node    # advance BEFORE yield — safe iteration
        yield value

Notice that __iter__ saves current.next_node before the yield. The generator pauses at yield, and if someone modifies the list while iterating, advancing after resumption could cause problems. Advancing before the yield is the safe pattern.

Search — O(n)

Search traverses the list comparing each value until it finds the element or reaches the end:

Search for 20 in: [10] ──► [20] ──► [30] ──► None

current=[10] → 10 != 20 → advance
current=[20] → 20 == 20 → found → return True
def contains(self, value):
    """Returns True if value is in the list."""
    current = self.__first
    while current is not None:
        if current.value == value:
            return True
        current = current.next_node
    return False    # reached end without finding it

Delete — O(n)

Deletion is the operation hardest to visualise. The key insight: to delete a node you don’t need to erase it — you just need the previous node to stop pointing to it and point directly to the next one instead.

Delete 20 from: [10] ──► [20] ──► [30] ──► None

Before:
[10].next_node ──► [20]
[20].next_node ──► [30]

After deleting [20]:
[10].next_node ──► [30]   ← we jump over node 20

Node [20] still exists in memory but nothing points to it
Python will remove it automatically (garbage collector)

Three cases to handle:

Case 1 — delete first:
first ──► [10] ──► [20] ──► [30] ──► None
first = first.next_node
first ──► [20] ──► [30] ──► None

Case 2 — delete middle:
[10] ──► [20] ──► [30] ──► None
previous.next_node = current.next_node
[10] ──► [30] ──► None

Case 3 — delete last:
[10] ──► [20] ──► [30] ──► None
previous.next_node = None
[10] ──► [20] ──► None
def delete(self, value):
    """Deletes first occurrence. Raises ValueError if not found."""

    if self.__first is None:
        raise ValueError(f"{value} not in list")

    # Case 1 — value is at the first node
    if self.__first.value == value:
        self.__first = self.__first.next_node    # first points to second
        self.__length -= 1
        return

    # Cases 2 and 3 — find the node BEFORE the one to delete
    previous = self.__first
    current = self.__first.next_node

    while current is not None:
        if current.value == value:
            previous.next_node = current.next_node    # jump over current
            self.__length -= 1
            return
        previous = current
        current = current.next_node

    raise ValueError(f"{value} not in list")

The previous / current pair advancing together is the key pattern for deletion:

previous ──► current ──► next
  [10]   ──►   [20]  ──►  [30]

To delete current (20):
previous.next_node = current.next_node
  [10].next_node   =      [30]

Result: [10] ──► [30]  (the [20] is now isolated)

Complete class

class LinkedList:
    """Singly linked list."""

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

    def __init__(self):
        self.__first = None
        self.__length = 0

    def insert_front(self, value):
        """Insert at front — O(1)."""
        self.__first = self.Node(value, self.__first)
        self.__length += 1

    def insert_back(self, value):
        """Insert at back — O(n)."""
        new = self.Node(value)
        if self.__first is None:
            self.__first = new
        else:
            current = self.__first
            while current.next_node is not None:
                current = current.next_node
            current.next_node = new
        self.__length += 1

    def delete(self, value):
        """Delete first occurrence. Raises ValueError if not found."""
        if self.__first is None:
            raise ValueError(f"{value} not in list")

        if self.__first.value == value:
            self.__first = self.__first.next_node
            self.__length -= 1
            return

        previous = self.__first
        current = self.__first.next_node
        while current is not None:
            if current.value == value:
                previous.next_node = current.next_node
                self.__length -= 1
                return
            previous = current
            current = current.next_node

        raise ValueError(f"{value} not in list")

    def contains(self, value):
        """Returns True if value is in the list."""
        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 __iter__(self):
        current = self.__first
        while current is not None:
            value = current.value
            current = current.next_node
            yield value

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

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

    def __contains__(self, value):
        return self.contains(value)

LinkedList vs Python list — when to use each

 <code>                   Python list    LinkedList
──────────────────────────────────────────────
Index access:          O(1) ✓        O(n) ✗
Insert at front:       O(n) ✗        O(1) ✓
Insert at back:        O(1) ✓        O(n) ✗
Insert in middle:      O(n) ✗        O(1) ✓ (if you have the previous node)
Search:                O(n)          O(n)
Memory:            more efficient  less efficient (each node carries pointer)</code>

In FP2 the LinkedList isn’t used because it’s better at everything — it’s used to learn how to manage references and pointers, which is the foundation of trees, graphs and other structures you’ll see in later courses.

Visualise with Python Tutor

LinkedList is where pythontutor.com is most valuable in the entire course — you can see exactly how each node points to the next and how references change when you insert or delete. Paste this:

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

# Build a 3-node list manually
n1 = Node(10)
n2 = Node(20)
n3 = Node(30)

n1.next_node = n2
n2.next_node = n3

# Traverse
current = n1
while current is not None:
    print(current.value)
    current = current.next_node

Step through and watch current jump from node to node following the arrows. Python Tutor draws the reference arrows visually — you’ll see n1 pointing to n2 pointing to n3 pointing to None. Then modify the code: insert a new node between n1 and n2:

new_node = Node(15)
new_node.next_node = n2    # connect new to n2 first
n1.next_node = new_node    # then connect n1 to new

Watch exactly which arrows change — n1‘s arrow now points to new_node, and new_node‘s arrow points to n2. The n2 and n3 nodes are completely unchanged. That’s the key insight of linked structures: insertion only modifies two references, regardless of list size.

Quick summary

# NODE — basic unit
class Node:
    def __init__(self, value, next_node=None):
        self.value = value           # the data
        self.next_node = next_node   # reference to next node or None

# LINKED LIST STRUCTURE
# first ──► [v1] ──► [v2] ──► [v3] ──► None
# Only stores reference to first node
# To reach any element: traverse from first

# INSERT AT FRONT — O(1)
new = Node(value, first)    # 1. connect to current first
first = new                  # 2. new is now first

# INSERT AT BACK — O(n)
current = first
while current.next_node is not None:   # advance to last node
    current = current.next_node
current.next_node = Node(value)        # connect at end

# TRAVERSE — O(n)
current = first
while current is not None:
    print(current.value)
    current = current.next_node    # advance to next

# DELETE — O(n)
# Special case: delete first
first = first.next_node

# General case: previous/current pair
previous = first
current = first.next_node
while current is not None:
    if current.value == target:
        previous.next_node = current.next_node   # jump over node
        break
    previous = current
    current = current.next_node

# COMPLEXITY COMPARISON
# Python list: index O(1), insert front O(n), insert back O(1)
# LinkedList:  index O(n), insert front O(1), insert back O(n)

# COMMON MISTAKES
# 1. Updating first BEFORE connecting new node → lose the list
# 2. Forgetting empty list special case in insert_back
# 3. Forgetting first node special case in delete
# 4. Comparing current.value after current becomes None → AttributeError
# 5. Not saving next reference before modifying previous.next_node

In the next article we practice the LinkedList with real programs — reversing a linked list, sorting its elements and detecting cycles.

Similar Posts

2 Comments

  1. Pingback: Python LinkedList Practice — Reverse, Sort and Search Linked Structures
  2. Pingback: Python LinkedList Exercises — 3 Essential with Solutions and Cheat Sheet

Leave a Reply

Your email address will not be published. Required fields are marked *