Linked list explained: how it works, code and complexity

What problem a linked list solves

An array (a Python list) keeps its elements in one contiguous block of memory. Reading a[i] is instant, but inserting at the front shifts every other element one slot to the right, which costs O(n). A linked list avoids that shift: each element lives in its own node, and nodes are connected by references. To insert, you only change a couple of references.

Linked lists are the building block behind many other structures: stacks, queues, hash table buckets (separate chaining), LRU caches and adjacency lists in graphs.

The idea in plain words

Think of a treasure hunt: each clue tells you where the next clue is. You cannot jump to clue number 7; you must follow clues 1 to 6 first. The list itself only remembers the first node, called the head. The last node points to nothing (None).

Worked example: inserting and deleting

Start with the list 3 -> 7 -> 9. We insert 5 after 3, then delete 7.

1. Create a new node with value 5.
2. Set new.next to the node after 3 (the node 7).
3. Set node3.next to the new node. The list is now 3 -> 5 -> 7 -> 9.
4. To delete 7, find the node before it (5) by walking from the head.
5. Set node5.next = node5.next.next, which skips 7. The list is now 3 -> 5 -> 9. Python's garbage collector frees the unreachable node.

Python implementation of a singly linked list

This class keeps a reference to the head and a size counter. It supports adding at the front and back, deleting the first matching value, and iteration.

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next
class LinkedList:
    def __init__(self):
        self.head = None
        self.size = 0
    def push_front(self, value):
        self.head = Node(value, self.head)
        self.size += 1
    def push_back(self, value):
        node = Node(value)
        if self.head is None:
            self.head = node
        else:
            cur = self.head
            while cur.next:
                cur = cur.next
            cur.next = node
        self.size += 1
    def remove(self, value):
        prev, cur = None, self.head
        while cur and cur.value != value:
            prev, cur = cur, cur.next
        if cur is None:
            return False          # not found
        if prev is None:
            self.head = cur.next  # removing the head
        else:
            prev.next = cur.next
        self.size -= 1
        return True
    def __iter__(self):
        cur = self.head
        while cur:
            yield cur.value
            cur = cur.next

items = LinkedList()
for x in [3, 7, 9]:
    items.push_back(x)
items.push_front(1)
items.remove(7)
print(list(items), items.size)  # [1, 3, 9] 3

push_back here walks the whole list, so it is O(n). Keeping an extra tail reference makes it O(1); that is what real queue implementations do.

Classic operations: reverse and cycle detection

Reversing a list in place is the most common linked list interview question. Walk the list once and turn each next pointer around.

def reverse(head):
    prev = None
    cur = head
    while cur:
        nxt = cur.next     # remember the rest
        cur.next = prev    # turn the pointer around
        prev, cur = cur, nxt
    return prev            # new head
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False
head = Node(1, Node(2, Node(3)))
head = reverse(head)
print(head.value, head.next.value, head.next.next.value)  # 3 2 1
print(has_cycle(head))  # False

has_cycle is Floyd's tortoise and hare algorithm: a slow pointer moves one step and a fast pointer moves two steps. If there is a loop, the fast pointer eventually meets the slow one; if not, it reaches None. It uses O(1) extra memory.

Time and space complexity

In practice, arrays are often faster even for operations where the linked list has a better Big O, because array elements sit next to each other in memory and use the CPU cache well. Linked list nodes are scattered.

Variants and common mistakes

• Forgetting the empty list: always check head is None before reading head.next.
• Losing the rest of the list by overwriting next before saving it (see nxt in reverse).
• Not updating head when the first node is removed, or tail when the last node is removed.
• Using recursion on very long lists: Python's default recursion limit is about 1000 frames, so iterative code is safer.
• A dummy (sentinel) head node removes most special cases: every real node then has a previous node.
• In a doubly linked list, every insert and delete must update four references; missing one corrupts the list silently.

When to use a linked list, and what to use in Python

Use a linked list when you insert and remove at the ends or in the middle at positions you already hold a reference to, and you rarely need random access. Examples: an LRU cache (doubly linked list plus hash map), the free list of a memory allocator, undo history, or the buckets of a hash table.

In everyday Python code you rarely write your own. For a queue or deque, use collections.deque, which gives O(1) appends and pops at both ends. For general sequences, use list. Write your own linked list for learning, for interviews, and when you need to splice nodes in O(1), as in an LRU cache.

from collections import deque
q = deque([1, 2, 3])
q.appendleft(0)
q.append(4)
print(q.popleft(), q.pop(), list(q))  # 0 4 [1, 2, 3]