The Project | About Us | Contribute | Donations | License
HOME My courses Completed
◄ Previous
◄

Linked Lists

Next ►
►

In the previous lesson we chained nodes by hand and ended up with expressions as awkward as head.next.next.next. Today we encapsulate all that mechanics in a LinkedList class that fulfills the list ADT's contract: insert (at the front, at the back, and at a position), remove, find, traverse, plus the magic methods __len__ and __str__ so it behaves like a full-fledged Python structure. Besides building it, we will subject it to the same scrutiny as everything else in this course: a Big O analysis operation by operation and empirical verification with timeit, pitting it against Python's list exactly where the latter fell short — inserting at the front. By the end, the TaskFlow board will move onto our new structure.

Contents

  1. The pieces: Node and the skeleton of LinkedList
  2. Inserting at the front and at the back (and the tail trick)
  3. Traversing, __len__, and __str__
  4. Finding and inserting at a position
  5. Removing: the previous-node pattern
  6. Big O analysis of all the operations
  7. The rematch: timeit against list inserting at the front
  8. TaskFlow v0.2: the board as a linked list

The pieces: Node and the skeleton of LinkedList

We start from the Node class of the previous lesson, unchanged, and add the container class that will hold the strategic references:

class Node:
    """A data item and the reference to the next node."""
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    """Singly linked list: an implementation of the list ADT with nodes."""
    def __init__(self):
        self.head = None    # reference to the first node (None = empty list)
        self.tail = None    # reference to the last node (the announced "trick")
        self.size = 0       # element counter, kept up to date

Three design decisions worth understanding before moving on:

  • head: the one indispensable entry point. If it is None, the list is empty.
  • tail: a direct reference to the last node. It is not mandatory in a linked list, but without it inserting at the back would require walking the whole list (O(n)); with it, it will be O(1). It is the trick we announced in the table in 02-01. The price: every operation must keep it up to date, as we will see.
  • size: keeping count on insert and remove costs one addition or one subtraction (O(1)), and in exchange len(my_list) will be instantaneous instead of recounting the nodes every time. It is the same spirit of spread-out cost we saw with amortization: pay a tiny bit on every operation so you never pay a lot at once.

A note on naming: although Python allows non-ASCII characters in identifiers (a tamaño with the Spanish ñ, or an accented café, are perfectly legal), avoiding non-ASCII characters in code names is a widespread professional convention (and consistent with the URL-safe naming hygiene this campus practices).

Inserting at the front and at the back (and the tail trick)

Inserting at the front: the strong suit

    def insert_front(self, data):
        """Adds an element ahead of everything. Cost: O(1)."""
        new_node = Node(data)
        new_node.next = self.head       # 1: the new node points to the old first
        self.head = new_node            # 2: the head becomes the new node
        if self.tail is None:           # 3: if the list was empty...
            self.tail = new_node        #    ...the new node is also the last
        self.size += 1

Step by step, with the rewiring diagram:

graph LR
    H[head] -- "2: reassigned" --> N["new node"]
    N -- "1: new_node.next" --> A["old first"]
    A --> B["..."]
  • Line 1 (new_node.next = self.head): the freshly created node grabs hold of the one that used to be first. If the list was empty, self.head is None and the new node correctly ends up as the last one (its next is None).
  • Line 2 (self.head = new_node): the list now starts at the new node. The order of these two lines is sacred: if we reassigned the head first, we would lose the only reference to the rest of the list.
  • Line 3: the empty-list special case — the new node is first and last at the same time.

Count the operations: two assignments, one comparison, one addition. None of them depends on how many elements there are. True O(1), not amortized: there are no occasional resizes here like in the array's append.

Inserting at the back: the tail in action

    def insert_back(self, data):
        """Adds an element behind everything. Cost: O(1) thanks to the tail."""
        new_node = Node(data)
        if self.tail is None:           # empty list: the new node is everything
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node   # the old last points to the new node
            self.tail = new_node        # the tail becomes the new node
        self.size += 1

Without the tail reference, this method would have to walk from the head to the last node (O(n)) just to hook the new one on. With it, two assignments and done. It is a perfect example of how one extra, well-maintained reference changes an operation's cost class.

Traversing, __len__, and __str__

Traversal is the move you already know: current = current.next until None. We will offer it in the most Pythonic way possible, as a generator, so we can write for task in my_list:

    def __iter__(self):
        """Enables: for data in my_list. Traverses in order. Cost: O(n)."""
        current = self.head
        while current is not None:
            yield current.data          # hand over the data and pause here
            current = current.next      # when the next one is requested, advance

    def __len__(self):
        """Enables: len(my_list). Cost: O(1) thanks to the counter."""
        return self.size

    def __str__(self):
        """Enables: print(my_list). Draws the chain of nodes."""
        parts = []
        for data in self:               # we reuse __iter__
            if isinstance(data, dict) and "title" in data:
                parts.append(f'[{data["id"]}:{data["title"]}]')
            else:
                parts.append(f"[{data}]")
        return (" -> ".join(parts) + " -> None") if parts else "(empty)"
  • yield turns __iter__ into a generator: it hands over a data item, stays "frozen", and continues when the for asks for the next one. To the user of the class, the linked list is traversed just like a list.
  • __str__ reuses __iter__ itself (no duplicating the loop) and has a TaskFlow-friendly detail: if the data item is a task-dict, it shows id:title instead of the whole dictionary.
  • The final -> None arrow is not decorative: it is a visual reminder that the last node points to None.

Finding and inserting at a position

Finding

Finding by value has no shortcuts: you have to look node by node. We implement a predicate-based search, designed for tasks ("give me the first one that meets this condition"):

    def find(self, condition):
        """Returns the first data item meeting the condition, or None. Cost: O(n)."""
        current = self.head
        while current is not None:
            if condition(current.data):
                return current.data
            current = current.next
        return None

Usage: my_list.find(lambda t: t["id"] == 42). It is the same O(n) as searching a list; lesson 01-02 already taught us that "look at everything" does not scale, and module 5 will bring the index by id that fixes it. The linked list does not compete on this terrain.

Inserting at a position

    def insert_at(self, index, data):
        """Inserts the data at position index (0 = at the front).
        Cost: O(n) for the walk to the spot; the rewiring is O(1)."""
        if index <= 0:
            self.insert_front(data)
            return
        if index >= self.size:
            self.insert_back(data)
            return
        prev = self.head
        for _ in range(index - 1):      # walk to the node before the spot
            prev = prev.next
        new_node = Node(data)
        new_node.next = prev.next       # 1: the new node grabs the displaced one
        prev.next = new_node            # 2: the previous one grabs the new node
        self.size += 1

Here appears the fine print we announced in 02-01, and it deserves a straight look:

  • Getting to the insertion point costs O(n): you have to walk index - 1 hops.
  • Rewiring costs O(1): the usual two assignments, in the usual order.

So where is the advantage over the array, if both are O(n) when inserting in the middle? In two places. First, at the ends: at the front the linked list is O(1) where the array is O(n) — we will measure that difference shortly. Second, in the "if we are already positioned" nuance: when an algorithm traverses the list and decides to insert or remove right where it stands (as you will do when merging sorted lists in 02-05), the O(1) rewiring truly pays off, whereas the array would pay the shifting anyway. The array, by contrast, pays the memory shifts always, no matter where it stands.

Removing: the previous-node pattern

To remove a node you must rewire the one that stands before it... and in a singly linked list the nodes don't know who precedes them (a shortcoming the doubly linked list will fix in 02-03). The standard technique is to advance with two references in parallel: prev and current.

    def remove(self, condition):
        """Removes the first node whose data meets the condition.
        Returns the removed data, or None if nothing meets it. Cost: O(n)."""
        prev = None
        current = self.head
        while current is not None:
            if condition(current.data):
                if prev is None:                    # it was the first
                    self.head = current.next
                else:
                    prev.next = current.next        # bypass the node
                if current is self.tail:            # it was the last
                    self.tail = prev
                self.size -= 1
                return current.data
            prev = current
            current = current.next
        return None
graph LR
    A["prev"] -- "new bridge" --> C["current.next"]
    A -. "old arrow" .-> B["current (removed)"]
    B -.-> C

The delicate points, one by one:

  • Bypassing: prev.next = current.next makes the chain "jump over" the doomed node. Nothing points to it anymore, so Python's garbage collector frees it. There is no del and no manual deallocation: dropping every reference is enough.
  • Removing the first: if prev is still None, the node to remove is the head; the bridge consists of moving self.head.
  • Removing the last: if the doomed node was the tail, self.tail must be pulled back to the previous one. Forgetting this case leaves a ghost tail pointing at a node outside the list — a classic.
  • We use is (identity) and not == to compare against self.tail: we want to know whether it is the same node, not a similar-looking one.

Big O analysis of all the operations

The table promised in 02-01, now proven method by method:

Operation LinkedList Why? Python's list
insert_front O(1) Rewire the head: 2 assignments O(n) — shifts everything
insert_back O(1) Thanks to the tail reference O(1) amortized
insert_at(i, x) O(n) Walk to i (rewiring is O(1)) O(n) — shifts the rest
remove (at the front) O(1) Move the head O(n) — the pop(0) trap
remove (in general) O(n) Walk to the node O(n)
find O(n) Look node by node O(n)
Traverse (__iter__) O(n) Visits each node once O(n)
len() O(1) Maintained counter O(1)
Access by index O(n) No formula: walk i hops O(1)

The last row is the price of scattering and there is no point hiding it: if your code lives off doing board[i], the linked list is a poor choice. That is why we haven't implemented __getitem__: giving bracket syntax to an O(n) operation invites using it in loops and manufacturing O(n²) without noticing.

The rematch: timeit against list inserting at the front

In 01-05 we saw that filling a list with insert(0, x) was quadratic. Let's repeat that experiment with our structure in the contest:

import timeit

def fill_list_front(n):
    items = []
    for i in range(n):
        items.insert(0, i)          # shifts i elements each time
    return items

def fill_linked_front(n):
    linked = LinkedList()
    for i in range(n):
        linked.insert_front(i)      # rewires 2 references each time
    return linked

for n in (10_000, 50_000, 100_000):
    t_list = timeit.timeit(lambda: fill_list_front(n), number=3)
    t_link = timeit.timeit(lambda: fill_linked_front(n), number=3)
    print(f"n={n:>7}: list.insert(0) {t_list:8.3f} s | linked {t_link:8.3f} s")

Typical result (the exact numbers vary by machine; the shape does not):

n=  10000: list.insert(0)    0.050 s | linked    0.012 s
n=  50000: list.insert(0)    1.3   s | linked    0.06  s
n= 100000: list.insert(0)    5.2   s | linked    0.12  s

The reading matters more than the figures:

  • When n doubles, the list quadruples (each insert(0) is O(n), the total O(n²)); the linked list doubles (each insertion O(1), the total O(n)). These are the curves from 01-04 in the flesh.
  • With small n the difference is anecdotal; with large n it is abysmal. Scalability, as in the 01-02 experiment, is what separates a correct choice from one that "worked on my laptop".
  • Experimental honesty: on operations where the list is strong (traversing, append, access by index), it would win, often by a wide margin, because the contiguous array exploits the cache and its internals are written in C. Choosing a structure means choosing by the dominant operation, not by the winner of the last benchmark.

TaskFlow v0.2: the board as a linked list

We close by putting the piece in its place. The TaskFlow board, where urgencies enter at the front and tasks are dispatched from the front, finally finds its structure:

board = LinkedList()

# Normal tasks enter at the back (arrival order)
board.insert_back({"id": 1, "title": "Design logo",
                   "priority": 2, "status": "pending"})
board.insert_back({"id": 2, "title": "Configure server",
                   "priority": 2, "status": "pending"})

# Urgent! It enters at the front, in O(1)
board.insert_front({"id": 3, "title": "Production hotfix",
                    "priority": 1, "status": "pending"})

print(board)
# [3:Production hotfix] -> [1:Design logo] -> [2:Configure server] -> None

# A task gets completed: locate it and pull it out
done_task = board.remove(lambda t: t["id"] == 3)
print("Completed:", done_task["title"])   # Completed: Production hotfix
print(len(board))                         # 2

# Board report: natural traversal with for
for t in board:
    print(f'- ({t["priority"]}) {t["title"]} [{t["status"]}]')

Notice that the client code never mentions nodes or references: it talks about tasks, exactly as the ADT-implementation separation of 01-01 demands. And a preview: this pattern of "enter at one end and leave at one end" has proper names — stack and queue — and dedicated structures we will build in modules 3 and 4, often mounted on exactly what you just wrote.

Common Mistakes and Tips

  • Rewiring in the wrong order. Assigning self.head = new_node before new_node.next = self.head leaves the new node pointing at itself and loses the rest of the list. Mnemonic rule: first the new node grabs, then it gets grabbed.
  • Forgetting to update tail (or size). Every method that touches the structure must leave the three references consistent. A remove that doesn't pull back the tail when it deletes the last node will make the next insert_back hook the node onto a ghost. Write a _check_invariants() method for debugging if this happens to you often.
  • The edge cases: empty list and a single element. They are the source of 80% of the failures: removing the only node must leave head and tail at None; inserting into an empty list must set both. Always test your methods with lists of 0, 1, and 2 elements before lists of 100.
  • Iterating with indexes out of habit. for i in range(len(my_list)): do_something(element_at(my_list, i)) would be O(n²) on a linked list. Always traverse with for data in my_list (our __iter__), which visits each node exactly once.
  • Tip: whenever a rewiring gives you doubts, draw the before and after with boxes and arrows, number the assignments, and only then write the code. Five minutes of paper save an hour of debugger.

Exercises

Exercise 1 — count_if. Add to LinkedList a method count_if(condition) that returns how many data items meet the condition, and use it to count how many tasks on the board have priority == 1. What is its Big O cost and why can't it be better?

Exercise 2 — insert_sorted by priority. Add a method insert_sorted(task) that inserts the task keeping the board sorted by ascending priority (priority 1 at the front). Hint: it is a variant of insert_at, but instead of counting hops, you walk until you find the first node with a higher priority. Mind the three cases: inserting at the front, in the middle, and at the back. State the Big O.

Exercise 3 — The price of the index. Implement an external function element_at(linked, i) that returns the data item at position i of a LinkedList (or None if it doesn't exist). Then write print_badly(linked), which prints all the elements using element_at in a loop over range(len(linked)), and print_well(linked), using for data in linked. Time both with timeit for n = 2,000 and 4,000 elements and explain the result with Big O.

Solutions

Solution 1:

    def count_if(self, condition):
        """Counts the data items meeting the condition. Cost: O(n)."""
        count = 0
        current = self.head
        while current is not None:
            if condition(current.data):
                count += 1
            current = current.next
        return count

# Usage:
urgent = board.count_if(lambda t: t["priority"] == 1)

It is O(n) and cannot be better: to count how many meet something, you must examine them all; no rewiring or extra reference avoids looking at each data item at least once.

Solution 2:

    def insert_sorted(self, task):
        """Inserts keeping ascending priority order. Cost: O(n)."""
        # Case 1: empty, or the new one goes first (priority lower than or equal to the first's)
        if self.head is None or task["priority"] <= self.head.data["priority"]:
            self.insert_front(task)
            return
        # Cases 2 and 3: walk to the last node with priority <= the new one's
        new_node = Node(task)
        prev = self.head
        while (prev.next is not None
               and prev.next.data["priority"] <= task["priority"]):
            prev = prev.next
        new_node.next = prev.next       # the usual rewiring
        prev.next = new_node
        if new_node.next is None:       # it ended up last: update the tail
            self.tail = new_node
        self.size += 1

Comments: the while condition looks at prev.next (not prev) because we need to stop at the node before the insertion point — the previous-node pattern again. The "goes at the back" case resolves itself: the while ends with prev.next at None and the rewiring hooks on at the end (without forgetting the tail). Cost O(n): in the worst case the whole list is walked. This method will reappear in module 4 when we talk about priority queues.

Solution 3:

import timeit

def element_at(linked, i):
    """Returns the data item at position i, or None. Cost: O(n)."""
    if i < 0:
        return None
    current = linked.head
    for _ in range(i):
        if current is None:
            return None
        current = current.next
    return current.data if current is not None else None

def print_badly(linked):
    for i in range(len(linked)):
        _ = element_at(linked, i)    # each call walks from the head

def print_well(linked):
    for data in linked:              # a single traversal
        _ = data

for n in (2_000, 4_000):
    linked = LinkedList()
    for i in range(n):
        linked.insert_back(i)
    t_bad = timeit.timeit(lambda: print_badly(linked), number=5)
    t_good = timeit.timeit(lambda: print_well(linked), number=5)
    print(f"n={n}: with indexes {t_bad:.3f} s | with the iterator {t_good:.4f} s")

Typical result: when n doubles, print_well doubles (O(n): one traversal) but print_badly quadruples (O(n²): the i-th call walks i hops, totaling 0+1+...+(n−1) ≈ n²/2). It is exactly the same sum that condemned insert(0) on the array, now on the linked list's side: each structure has its own way of manufacturing O(n²) when used against its nature.

Conclusion

You now have your first structure built from scratch and complete: LinkedList, with O(1) insertions at both ends (head rewired, tail maintained), removal via the previous-node pattern, predicate-based search, traversal as a generator, and first-class len/print. The Big O analysis was proven and timeit confirmed the rematch: where insert(0) condemned the list to quadratic behavior, our structure scales linearly — at the price of giving up O(1) access by index, as the last exercise exposed. The TaskFlow board now lives on it. But it still has a structural shortcoming: each node knows the next one and is completely unaware of the previous one, which forced us into the two-reference dance for removal and makes traversing backward impossible. In the next lesson we will add the missing arrow — prev — and obtain the doubly linked list: O(1) removals when you hold the node, traversals in both directions, and for TaskFlow a task history you can navigate forward and backward.

◄ Previous
◄
Next ►
►
The Project | About Us | Contribute | Donations | License
© Copyright 2026. All rights reserved