Unit 4 · Introduction to Computer Science

Linked Lists

The first structure you build from nothing. No Python list underneath — just objects holding references to other objects. It trades away instant indexing and buys constant-time insertion anywhere you already are.

By the end you can

Build a linked list from node objects.
Insert and delete without losing the rest of the list.
Say precisely what linked lists are better and worse at.
Handle the empty list and the head as separate cases.

Why it matters & where it comes from

Why it exists

A Python list stores items contiguously, so inserting in the middle shifts everything after it. A linked list stores each item wherever, connected by references, so inserting is three assignments regardless of size.

In the real world

File systems chain disk blocks this way. Undo histories, music playlists and the free-memory lists inside an allocator are linked structures, chosen because insertion and removal dominate.

Story & open questions

Linked lists were invented in 1955 for an early artificial-intelligence program at RAND. The idea — data scattered in memory but logically ordered by references — is the ancestor of every tree and graph in this course.

Nodes

Example The building block

python

class _Node:
    """A node in a linked list.

    Attributes:
        item: the value stored here
        next: the following node, or None at the end of the list
    """
    item: object
    next: object

    def __init__(self, item) -> None:
        """Initialize a node holding item with no successor."""
        self.item = item
        self.next = None

The leading underscore says clients never see nodes. They are an implementation detail of the list.

next being None is what marks the end. Every traversal stops on it.

Example The list itself

python

class LinkedList:
    """A sequence of items stored in linked nodes.

    Attributes:
        _first: the first node, or None if the list is empty
    """
    _first: object

    def __init__(self) -> None:
        """Initialize an empty linked list."""
        self._first = None

    def is_empty(self) -> bool:
        """Return whether this list is empty."""
        return self._first is None

    def __len__(self) -> int:
        """Return the number of items in this list.

        >>> lst = LinkedList()
        >>> len(lst)
        0
        """
        count = 0
        node = self._first
        while node is not None:
            count = count + 1
            node = node.next
        return count

Note __len__ is $O(n)$: there is no stored count, so it walks the whole list. A Python list answers in $O(1)$. That is the first of the trade-offs.

Rule The traversal pattern

Almost every linked-list method is this loop:

python

node = self._first
while node is not None:
    # do something with node.item
    node = node.next

Forgetting the last line gives an infinite loop, and it is the single most common mistake in the unit.

Insertion

Example At the front — the cheap case

python

def prepend(self, item) -> None:
    """Add item to the front of this list.

    >>> lst = LinkedList()
    >>> lst.prepend(2)
    >>> lst.prepend(1)
    >>> len(lst)
    2
    """
    new_node = _Node(item)
    new_node.next = self._first
    self._first = new_node

Two assignments, $O(1)$, whatever the length. A Python list's insert(0, x) is $O(n)$.

The order matters. Setting self._first first would lose the reference to the old head and orphan the entire list.

Order of assignment is the whole game

python

# wrong - the rest of the list is now unreachable
self._first = new_node
new_node.next = self._first   # points at itself!

Always attach the new node to the existing structure before redirecting anything that pointed into it. Drawing the arrows makes this obvious; reading the code does not.

Example In the middle

python

def insert_after(self, target, item) -> bool:
    """Insert item immediately after the first occurrence of target.

    Return whether target was found.

    >>> lst = LinkedList()
    >>> lst.prepend(1)
    >>> lst.insert_after(1, 2)
    True
    """
    node = self._first
    while node is not None:
        if node.item == target:
            new_node = _Node(item)
            new_node.next = node.next
            node.next = new_node
            return True
        node = node.next
    return False

The insertion itself is $O(1)$ — two assignments. Finding the position is $O(n)$.

That split is the honest description of linked lists: cheap to modify once you are there, expensive to get there.

Deletion

Example Removing a node

python

def remove(self, item) -> bool:
    """Remove the first occurrence of item and return whether it was found.

    >>> lst = LinkedList()
    >>> lst.prepend(1)
    >>> lst.remove(1)
    True
    >>> lst.is_empty()
    True
    """
    if self._first is None:
        return False

    if self._first.item == item:          # removing the head
        self._first = self._first.next
        return True

    node = self._first                    # removing anything else
    while node.next is not None:
        if node.next.item == item:
            node.next = node.next.next
            return True
        node = node.next
    return False

Three cases, and they genuinely differ: empty list, head, and everything else. Collapsing them into one loop is where most bugs come from.

Removing the head is special because there is no previous node to redirect — self._first plays that role.

The loop looks at node.next, not node, because you must hold the node before the one you are deleting.

Rule Deletion is just skipping

Nothing is erased. Setting node.next = node.next.next routes around the unwanted node, and Python's garbage collector reclaims it once nothing refers to it.

The trade-off

Rule Which structure when

Indexing. Python list $O(1)$; linked list $O(n)$ — you must walk from the start.

Insert or delete at the front. Python list $O(n)$; linked list $O(1)$.

Insert or delete at a known node. Python list $O(n)$; linked list $O(1)$.

Memory. Linked lists use more — each item carries a reference alongside it.

Neither is better. Choose by which operation dominates, which is exactly the analysis Unit 9 formalises.

Example Fixing the queue

Unit 3's queue had an $O(n)$ dequeue. Keeping a reference to the last node as well as the first fixes it.

Enqueue at the back: attach to _last, then update _last. $O(1)$.

Dequeue from the front: advance _first. $O(1)$.

Both ends are now constant time, which no single Python list can manage. This is the concrete payoff of the whole unit.

Common pitfalls

• Forgetting node = node.next and looping forever.
• Reassigning references in the wrong order and orphaning the list.
• Not handling the empty list or the head as separate cases.
• Comparing with == None rather than is None.
• Expecting len() to be free. It walks the whole list.

Practice

Write out each answer before opening it. Original exercises written for this guide in the style of the course's weekly work.

Practice 1 · End of list

How does a traversal know it has finished?

Answer

The current node's next is None.

Practice 2 · Assignment order

What breaks if you set self._first = new_node before new_node.next = self._first?

Answer

The new node points at itself and the rest of the list becomes unreachable — a self-referential loop and a lost list.

Practice 3 · Cost of indexing

What is the cost of getting item $k$?

Answer

$O(k)$, so $O(n)$ in the worst case. There is no arithmetic shortcut to a position.

Practice 4 · Why three cases

Why does remove treat the head separately?

Answer

Because there is no preceding node to redirect. The list's own _first reference has to be updated instead.

Practice 5 · Append

Write a method adding an item at the end.

Solution

python

def append(self, item) -> None:
    """Add item to the end of this list."""
    new_node = _Node(item)
    if self._first is None:
        self._first = new_node
        return
    node = self._first
    while node.next is not None:
        node = node.next
    node.next = new_node

$O(n)$ without a tail reference — which is exactly why the queue keeps one.

Practice 6 · Count occurrences

Count how many times an item appears.

Solution

python

def count(self, item) -> int:
    """Return how many times item appears in this list."""
    total = 0
    node = self._first
    while node is not None:
        if node.item == item:
            total = total + 1
        node = node.next
    return total

Practice 7 · Reverse

Reverse a linked list in place.

Solution

python

def reverse(self) -> None:
    """Reverse the order of the items in this list."""
    previous = None
    node = self._first
    while node is not None:
        following = node.next    # save before overwriting
        node.next = previous
        previous = node
        node = following
    self._first = previous

Saving following first is essential — overwriting node.next destroys the only route to the rest.

Practice 8 · When to choose it

Give a case where a linked list clearly beats a Python list.

Answer

Repeatedly inserting at the front, or maintaining a queue where both ends are used. Both are $O(1)$ per operation on a linked list and $O(n)$ on a Python list.

Expanded topic checklist

Course coverage. This unit is part of the complete CSC148H1 topic map. It should cover the following items before you move on:

Nodes. Item plus reference, with None marking the end.
Traversal. The standard loop and why the advance line matters.
Insertion and deletion. Assignment order, and the head and empty cases.
Trade-offs. What linked lists win and lose against a Python list.

Textbook/source alignment

The calendar names "linked data structures" explicitly. Check Quercus for the assigned exercises; linked-list manipulation is a standard term test question and is usually assessed by writing code by hand.

Core idea map

Objects holding references to objects. Change the structure by redirecting references, in the right order. Units 7 and 8 use the same idea with two references per node instead of one.

Study routine. Draw the boxes and arrows before and after every operation, and number the assignments in the order you will make them. Reference bugs are invisible in code and obvious in a diagram.

Deep practice extensions

Use these after the main practice set. They push on definitions and edge cases rather than routine calculation.

Extension 1 · Marking the end

What signals the end of a linked list?

Guide

A next of None. Every traversal loop tests for it.

Extension 2 · Insertion cost

Why is inserting at a known node $O(1)$?

Guide

It is two assignments and nothing shifts. The $O(n)$ part is finding the node, not the insertion itself.

Extension 3 · Head case

Why is removing the first item special?

Guide

There is no previous node whose next can be redirected, so the list's own _first must change.

Extension 4 · Choosing

When does a Python list win?

Guide

When indexing dominates. $O(1)$ access by position versus $O(n)$, and lower memory per item.

← Unit 03Stacks & queues Unit 05 →Recursion