Python Linked Lists

A linked list is a data structure made of individual nodes, where each node holds a piece of data and a reference (a ‘link’) to the next node in the sequence. Unlike a Python list, which stores its elements in one contiguous block of memory, a linked list’s nodes can live anywhere in memory and are connected only through these references. Learning to build one from scratch teaches you how references and memory actually work in Python, and linked lists show up constantly in technical interviews and inside the implementation of other structures like stacks, queues, and graphs.

Overview: How Linked Lists Work

Python’s standard library does not give you a general-purpose linked list type the way it gives you list or dict. Instead, you build one yourself out of small, self-referential objects. Each node is an object with two parts: the data it stores, and a reference to the next node. A separate variable, usually called head, points to the first node. To find any element, you start at head and follow the chain of .next references one node at a time until you either find what you want or reach a node whose .next is None, which marks the end of the list.

This matters because Python lists (which are really dynamic arrays) store their elements in one contiguous block of memory, so the interpreter can jump straight to index i by computing an address. A linked list has no such shortcut: there is no ‘slot 5’ to jump to, only a chain you must walk link by link. In exchange for slower access, linked lists give you cheap insertion and removal anywhere you already have a reference to, because changing a link is just reassigning a .next attribute; nothing needs to shift over as it would in an array-backed list.

There are several flavors. A singly linked list (the focus of this lesson) has nodes that only know about the next node. A doubly linked list adds a .previous reference on each node so you can walk backward too; Python’s own collections.deque is implemented internally as a doubly linked list, which is why appending or popping from either end of a deque is O(1). A circular linked list has its last node point back to the first instead of to None.

Linked list vs. Python list: time complexity

Operation	Python list (array)	Singly linked list
Access by index	O(1)	O(n)
Insert/delete at front	O(n)	O(1)
Insert/delete at end	O(1) amortized	O(1) with a tail pointer, else O(n)
Search by value	O(n)	O(n)

Syntax

A linked list is normally built from two classes: Node, which holds one value and a reference to the next node, and a wrapper class (often called LinkedList) that tracks the head and exposes operations like append, prepend, and delete.

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

first = Node("A")
second = Node("B")
first.next = second

print(first.data, first.next.data)

Output:

A B

• Node.data — the value stored in this node; can be any Python object.
• Node.next — a reference to the next Node, or None if this is the last node.
• head — a reference to the first node of the whole list; None means the list is empty.
• tail (optional) — a reference to the last node, kept so append() does not have to walk the whole list every time.

Examples

Example 1: Building and Traversing a Singly Linked List

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


class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        current = self.head
        while current.next is not None:
            current = current.next
        current.next = new_node

    def display(self):
        values = []
        current = self.head
        while current is not None:
            values.append(str(current.data))
            current = current.next
        print(" -> ".join(values))


numbers = LinkedList()
numbers.append(10)
numbers.append(20)
numbers.append(30)
numbers.display()

Output:

10 -> 20 -> 30

Each call to append creates a new Node and walks from head to the last existing node (the one whose .next is None), then attaches the new node there. display does the same kind of walk, collecting each node’s data into a list of strings before printing them joined by arrows. Notice that current is a separate variable used only for walking — self.head itself is never changed by traversal, so the list stays intact after display() runs.

Example 2: Prepending, Deleting, and Making the List Iterable

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


class LinkedList:
    def __init__(self):
        self.head = None
        self.size = 0

    def prepend(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
        self.size += 1

    def append(self, data):
        new_node = Node(data)
        self.size += 1
        if self.head is None:
            self.head = new_node
            return
        current = self.head
        while current.next is not None:
            current = current.next
        current.next = new_node

    def delete(self, data):
        current = self.head
        previous = None
        while current is not None:
            if current.data == data:
                if previous is None:
                    self.head = current.next
                else:
                    previous.next = current.next
                self.size -= 1
                return True
            previous = current
            current = current.next
        return False

    def __iter__(self):
        current = self.head
        while current is not None:
            yield current.data
            current = current.next

    def __len__(self):
        return self.size


tasks = LinkedList()
tasks.append("wash dishes")
tasks.append("write report")
tasks.prepend("wake up")
tasks.delete("write report")

print(list(tasks))
print(f"Remaining tasks: {len(tasks)}")

Output:

['wake up', 'wash dishes']
Remaining tasks: 2

prepend is O(1): the new node’s .next is pointed at the old head, then self.head is reassigned to the new node — no walking required. delete keeps two ‘hands’ as it walks: previous and current. When it finds a match, it splices the node out by pointing previous.next (or self.head, if the match is the first node) directly at current.next, skipping over the deleted node entirely. Implementing __iter__ as a generator lets the class work with list(), for loops, and any function that expects an iterable, and __len__ lets len(tasks) work without a separate walk.

Example 3: Reversing a Linked List In Place

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


def build_list(values):
    head = None
    tail = None
    for value in values:
        node = Node(value)
        if head is None:
            head = node
            tail = node
        else:
            tail.next = node
            tail = node
    return head


def print_list(head):
    values = []
    current = head
    while current is not None:
        values.append(str(current.data))
        current = current.next
    print(" -> ".join(values))


def reverse_list(head):
    previous = None
    current = head
    while current is not None:
        next_node = current.next
        current.next = previous
        previous = current
        current = next_node
    return previous


head = build_list([1, 2, 3, 4, 5])
print_list(head)
head = reverse_list(head)
print_list(head)

Output:

1 -> 2 -> 3 -> 4 -> 5
5 -> 4 -> 3 -> 2 -> 1

This is the classic linked-list interview problem, and it is entirely non-destructive of data — only the .next links change direction. reverse_list keeps three pointers as it walks forward exactly once: previous (the node behind, initially None), current (the node being rewired), and next_node (a saved reference to what used to come next, taken before the link is overwritten). Without saving next_node first, reassigning current.next = previous would sever the only path forward and the rest of the list would be lost.

Under the Hood: What’s Really Happening

Every Node you create is a separate object living on the heap, just like any other Python object. The attribute node.next does not contain another node’s data by value — it holds a reference to that node object, the same mechanism Python uses whenever one variable is assigned to another. This is why current = self.head does not copy the list: current and self.head now both point at the exact same first Node object. Walking the list with current = current.next simply moves which object current refers to; it never touches self.head, which is precisely why traversal is safe.

Tracing reverse_list([1, 2, 3]) makes the mechanics concrete. Start: previous=None, current points at node 1. Iteration 1: next_node is saved as node 2; node 1‘s .next is rewritten to None (pointing at previous); then previous and current both advance one slot. Iteration 2: node 2‘s .next is rewritten to point at node 1. Iteration 3: node 3‘s .next is rewritten to point at node 2, and current becomes None, ending the loop. previous now points at node 3, the new head, and the chain reads 3 -> 2 -> 1.

Common Mistakes

Mistake 1: Traversing by overwriting head itself

It is tempting to reuse self.head as the walking variable instead of introducing a new one:

class LinkedList:
    def display(self):
        while self.head is not None:
            print(self.head.data)
            self.head = self.head.next

This prints the values correctly the first time, but it also permanently destroys the list: by the end of the loop, self.head has been walked all the way to None. Call display() a second time and it prints nothing, because the entry point to the list is gone. Always traverse with a separate local variable:

class LinkedList:
    def display(self):
        current = self.head
        while current is not None:
            print(current.data)
            current = current.next

Mistake 2: Forgetting to advance the loop pointer

Another common slip is writing the traversal condition and body correctly but forgetting the step that moves to the next node:

current = self.head
while current is not None:
    print(current.data)

Because current never changes, this prints the first node’s data forever — an infinite loop that will hang the program (or, inside a generator using yield, silently produce infinite values to whatever consumes it). The fix is to always include the advance step as the last line of the loop body:

current = self.head
while current is not None:
    print(current.data)
    current = current.next

Best Practices

• Keep a tail reference alongside head if you append often; otherwise every append() costs an O(n) walk to find the last node.
• Prefer prepend() over append() when order doesn’t matter and you’re building a list from many items, since inserting at the front is always O(1).
• Implement __iter__ as a generator so your list works naturally with for loops, list(), and comprehensions instead of exposing raw Node objects.
• Implement __len__ and track size incrementally rather than walking the list to count nodes every time.
• When deleting or inserting mid-list, always track both the current node and the previous node so you can relink around the target in a single pass.
• For real production code, reach for collections.deque instead of hand-rolling a linked list — it’s a battle-tested, doubly linked structure with O(1) appends and pops from both ends.
• Use type hints (e.g. next: "Node | None" = None) on your Node class to make the structure self-documenting for readers and IDEs.

Practice Exercises

• Exercise 1: Write a function find_middle(head) that returns the middle node of a singly linked list in a single pass, using a ‘slow’ pointer that advances one node at a time and a ‘fast’ pointer that advances two nodes at a time.
• Exercise 2: Write a function has_cycle(head) that returns True if a linked list loops back on itself (Floyd’s cycle detection, using the same slow/fast pointer idea) and False otherwise.
• Exercise 3: Write two conversion functions, from_list(values) that builds a linked list from a Python list, and to_list(head) that converts a linked list back into a Python list. Confirm that to_list(from_list([1, 2, 3])) == [1, 2, 3].

Summary

• A linked list is built from Node objects, each holding data and a reference to the next node; head marks the entry point.
• Unlike a Python list, a linked list has no contiguous memory, so indexed access is O(n), but inserting or deleting at a known position can be O(1).
• Always traverse with a separate local variable (e.g. current) so you never lose or destroy head.
• Always advance the walking pointer inside the loop body, or you’ll create an infinite loop.
• Reversing a list in place needs three tracked references — previous, current, and a saved next_node — because overwriting .next destroys the forward path if you don’t save it first.
• For production use, Python’s collections.deque already gives you a doubly linked list with fast operations at both ends.