Linked Lists

What a linked list is

A linked list is a way to store a sequence of values, one after another, where each value lives in its own little box, and each box also holds a pointer to the next box. A pointer here just means “a reference that tells you where to find another object” — in Python, it is simply a variable that holds another object.

Each box is called a node. A node holds two things:

1. a value (the data you care about, like a number or a name), and
2. a next reference that points to the following node.

The last node’s next points to nothing. In Python “nothing” is written None, a built-in value that means “no object here.”

This is different from a Python list (the thing you write with square brackets, like [1, 2, 3]). A Python list stores its items packed together in one continuous block of memory. A linked list scatters its items anywhere in memory and threads them together with the next pointers. That difference is the whole point, and it decides which operations are fast and which are slow.

The node

We build a node with a class. A class is a template that describes what data an object holds. Here is a node that stores one value and one next pointer:

class Node:
    def __init__(self, value):
        self.value = value   # the data
        self.next = None     # points to the next node, or None if there is none

__init__ is the setup method that runs when you create a node. self refers to the node being built. So self.value = value records the data, and self.next = None starts with no next node.

Let us make three nodes and link them by hand:

a = Node(10)
b = Node(20)
c = Node(30)

a.next = b   # a now points to b
b.next = c   # b now points to c
# c.next is still None, so c is the last node

print(a.value)         # -> 10
print(a.next.value)    # -> 20
print(a.next.next.value)  # -> 30

Reading a.next.next.value means: start at a, hop to its next (b), hop to that node’s next (c), then read the value (30).

The head

To use a linked list you only need to hold on to the first node. That reference is called the head. From the head you can reach every other node by following next pointers. If you lose the head, you lose the whole list, because nothing else points to the first node.

Picture the list 10 -> 20 -> 30. head sits outside the chain and points at the first node; each node’s next threads to the following one, until the last node points at None.

graph LR
    head([head]) --> A
    A["value: 10 | next"] --> B["value: 20 | next"]
    B --> C["value: 30 | next"]
    C --> NULL([None])

Singly vs doubly linked

The list above is singly linked: each node knows only about the node after it. You can walk forward, but not backward.

A doubly linked list gives each node a second pointer, usually called prev, that points to the node before it. Now you can walk in both directions. The cost is one extra pointer per node (more memory) and more bookkeeping on every insert and delete, because you must fix up both next and prev.

class DNode:
    def __init__(self, value):
        self.value = value
        self.next = None
        self.prev = None

Use singly linked when you only ever move forward. Use doubly linked when you need to move backward too, or delete a node quickly when you are standing on it (because you can reach the previous node directly).

Traversal

Traversal means visiting each node in order, from the head to the end. You keep a variable (call it current) that starts at the head and moves forward by current = current.next until it falls off the end at None.

def print_list(head):
    current = head
    while current is not None:
        print(current.value)
        current = current.next

print_list(a)
# -> 10
# -> 20
# -> 30

Traversal touches every node once, so it is O(n) time (where n is the number of nodes) and O(1) extra space (we only keep the single current variable). O(n) means the work grows in step with the number of nodes; O(1) means the extra memory does not grow with the list at all.

Why linked lists exist: insert and delete

The reason to use a linked list is speed of insertion and deletion when you already have a node in hand.

Suppose you are holding a node and want to insert a new node right after it. You only rewire two pointers, no matter how big the list is:

def insert_after(node, value):
    new_node = Node(value)
    new_node.next = node.next   # new node points to what came after
    node.next = new_node        # old node now points to the new node

insert_after(a, 15)   # list is now 10 -> 15 -> 20 -> 30

The order here matters. Set new_node.next first. If you overwrote node.next first, you would lose the reference to the rest of the list.

Trace insert_after(a, 15): only two arrows change. a’s next now points at the new node 15, and 15’s next points at 20. Every other node is untouched.

Before:

graph LR
    head([head]) --> A["10"]
    A --> B["20"]
    B --> C["30"]
    C --> NULL([None])

After:

graph LR
    head([head]) --> A["10"]
    A --> N["15 (new)"]
    N --> B["20"]
    B --> C["30"]
    C --> NULL([None])

That work is constant, O(1) time, because it never depends on the list’s length. Deleting the node after a known node is also O(1): you just skip over it.

def delete_after(node):
    if node.next is not None:
        node.next = node.next.next   # unlink the following node

delete_after(a)   # if list was 10 -> 15 -> 20 -> 30, it is now 10 -> 20 -> 30

Now run delete_after(a) on the list 10 -> 15 -> 20 -> 30. The only change is a’s next: it used to point at 15, and now it points past 15 straight to 20. The 15 node still exists in memory for a moment, but nothing points to it anymore.

Before:

graph LR
    head([head]) --> A["10"]
    A --> N["15"]
    N --> B["20"]
    B --> C["30"]
    C --> NULL([None])

After:

graph LR
    head([head]) --> A["10"]
    A --> B["20"]
    B --> C["30"]
    C --> NULL([None])
    N["15 (unlinked)"]

The unlinked node is no longer reachable from the head, so Python’s garbage collector frees its memory automatically.

Search is the slow part. To find a value you must start at the head and check nodes one by one until you find it or reach the end. That is O(n) time. A linked list gives you no way to jump straight to the fifth item; there is no indexing by position.

def find(head, target):
    current = head
    while current is not None:
        if current.value == target:
            return True
        current = current.next
    return False

print(find(a, 20))   # -> True
print(find(a, 99))   # -> False

A small singly linked list class

So far we have passed the head around as a loose variable. It is cleaner to wrap the head inside a class that offers a couple of methods. Here push adds a value to the front, and print_all walks the list.

class LinkedList:
    def __init__(self):
        self.head = None   # an empty list has no head

    def push(self, value):
        # add a new node at the front
        new_node = Node(value)
        new_node.next = self.head   # new node points to the old first node
        self.head = new_node        # the new node becomes the head

    def print_all(self):
        current = self.head
        while current is not None:
            print(current.value)
            current = current.next

Adding to the front is O(1): we rewire two pointers and never walk the list.

lst = LinkedList()
lst.push(30)
lst.push(20)
lst.push(10)   # each push goes to the front, so order reverses

lst.print_all()
# -> 10
# -> 20
# -> 30

Because push inserts at the front, the values come out in the reverse of the order you pushed them.

push also rewires exactly two pointers. Follow the single call lst.push(10) when the list already holds 20 -> 30: the new node points at the old head, then head moves to point at the new node.

Before:

graph LR
    head([head]) --> B["20"]
    B --> C["30"]
    C --> NULL([None])

After:

graph LR
    head([head]) --> A["10 (new)"]
    A --> B["20"]
    B --> C["30"]
    C --> NULL([None])

Tracing the three pushes step by step

Let us follow the exact three calls from the example, starting from an empty list. Each row shows the full state of the list right after that step runs. Read -> as a next pointer and None as the end.

At each step the brand-new node becomes the head and its next is whatever the head used to be. Nothing after the front ever moves, which is why every push is the same small amount of work regardless of how long the list already is.

Big-O of the operations

Here is every operation on a singly linked list gathered in one place. n is the number of nodes. “Time” is how the work grows with n; “space” is the extra memory the operation needs beyond the list itself.

The pattern to remember: anything you can do while already standing on the right node is O(1), and anything that first requires finding a node is O(n).

Array vs linked list trade-offs

An array (Python’s built-in list) and a linked list solve the same problem — hold a sequence — but with opposite strengths. Here is the honest comparison.

An array stores items in one packed block, so it can jump to position i instantly by arithmetic — that is the O(1) read. But inserting at the front means shifting every other item over by one, which is O(n).

A linked list cannot jump to a position; it has to walk, so reads and searches are O(n). What it buys you is O(1) insertion and deletion once you are holding the relevant node, and it never needs to move existing items.

In everyday Python you will reach for the built-in list almost always, because fast indexing and good memory locality matter more in practice. Linked lists are worth understanding because their pointer-rewiring idea is the foundation for stacks, queues, and more complex structures like trees and graphs.

Common pitfalls

• Losing the head. The head is your only handle on the list. If you reassign it during traversal (for example, writing head = head.next in a loop) you throw away the front of the list. Walk with a separate current variable instead.
• Wrong pointer order on insert. When inserting, point the new node at the rest of the list before you rewire the previous node’s next. Do it backward and the tail of the list becomes unreachable.
• Forgetting the None at the end. Traversal loops stop at None. If a node’s next is left uninitialized or points somewhere by accident, your loop can run forever or crash. A fresh node should always start with next = None.
• Comparing with == instead of is. To test for the end of the list, use current is None. is checks whether it is literally the None object, which is what you mean here.
• Assuming index access. There is no list[3] on a linked list. Reaching the fourth node means four hops from the head.

Practice

1. Write a function length(head) that returns the number of nodes in a singly linked list by traversing it. State its Big-O time.
2. Add an append(value) method to the LinkedList class that adds a node at the end. Think about what its Big-O time is for a plain singly linked list, and why it differs from push.
3. Write a function reverse(head) that reverses a singly linked list in place and returns the new head. Hint: walk the list with three variables — the previous node, the current node, and the next node — and flip each next pointer as you go.