Linked Lists

Overview

A linked list stores each element in a node that also holds a reference to the next node. Because nodes are linked by pointers rather than stored contiguously, inserting or removing at a known position is O(1), but reaching the nth element requires walking from the head in O(n). Unlike arrays, there is no O(1) random access by index.

Syntax / Usage

Python has no built-in linked list, so you define a Node and connect them.

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

head = Node(1)
head.next = Node(2)
head.next.next = Node(3)

# Traverse the list -> O(n)
node = head
while node is not None:
    print(node.value)
    node = node.next

Examples

Prepend a value in O(1) by pointing the new node at the old head:

def push_front(head, value):
    new_node = Node(value)
    new_node.next = head   # O(1)
    return new_node        # new head

head = push_front(head, 0)  # list is now 0 -> 1 -> 2 -> 3

Search for a value, returning whether it exists:

def contains(head, target):
    node = head
    while node:            # O(n)
        if node.value == target:
            return True
        node = node.next
    return False

Common Mistakes

• Losing the rest of the list by reassigning next before saving it
• Forgetting to update the head when inserting or removing at the front
• Dereferencing node.next when node is already None
• Expecting O(1) index access — traversal is always O(n)
• Creating a cycle by accidentally linking a node back to an earlier one

See Also

data-structures-arrays data-structures-stacks data-structures-queues