Linked Lists — Items That Point to the Next

What is it? #

A linked list stores each item in its own small box called a node. Every node holds a value and a reference to the next node. The list itself is just a reference to the first node.

Nothing is stored next to anything else in memory, so there is no way to calculate where item 500 lives. You have to start at the front and follow the chain.

In exchange, inserting or removing is cheap once you are at the right place. You change two references and nothing else moves.

That trade-off is the whole story: arrays give fast access and slow insertion in the middle; linked lists give the reverse.

Think of it like this #

A treasure hunt. Each clue tells you where the next clue is. To reach clue seven, you must follow one through six — there is no shortcut.

But inserting a new clue between two existing ones is trivial: write a new card, point it at the old next clue, and point the previous card at your new card. No other clue in the hunt is affected.

Simple example #

A music player's playlist. Inserting a song after the current one should not shift anything, and you naturally walk forwards through the songs. That access pattern suits a linked list better than an array.

Code #

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None          # reference to the next node, or None


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

    def push_front(self, value):          # O(1)
        node = Node(value)
        node.next = self.head
        self.head = node
        self.size += 1

    def insert_after(self, node, value):  # O(1) once you have the node
        new_node = Node(value)
        new_node.next = node.next
        node.next = new_node
        self.size += 1

    def find(self, value):                # O(n) — no shortcuts
        current = self.head
        while current:
            if current.value == value:
                return current
            current = current.next
        return None

    def delete(self, value):              # O(n) to find, O(1) to unlink
        previous, current = None, self.head
        while current:
            if current.value == value:
                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 to_list(self):
        out, current = [], self.head
        while current:
            out.append(current.value)
            current = current.next
        return out


playlist = LinkedList()
for song in ["Ocean", "Mirage", "Sunset"]:
    playlist.push_front(song)

mirage = playlist.find("Mirage")
playlist.insert_after(mirage, "Echoes")
print(playlist.to_list())     # ['Sunset', 'Mirage', 'Echoes', 'Ocean']

# Detecting a loop with two pointers moving at different speeds
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

Array vs linked list

                      array        linked list
access by index       O(1)         O(n)
insert at front       O(n)         O(1)
insert after a node   O(n)         O(1)
search by value       O(n)         O(n)
memory per item       compact      value + pointer
cache friendliness    excellent    poor

How it works #

Node holds a value and a next reference. A list of three songs is three separate objects scattered in memory, chained by references.

push_front points the new node at the current head and makes it the new head. Two assignments, regardless of list length — that is the O(1) insertion linked lists are known for.

insert_after is the same idea in the middle: link the new node to whatever came next, then relink the previous node. Nothing shifts.

find has to walk. There is no arithmetic that gets you to position 500, so every lookup is a traversal. This is the cost you pay.

delete tracks the previous node because a singly linked list cannot look backwards. Handling the head case separately (when previous is None) is the part people forget.

has_cycle is the well-known two-speed pointer trick: one pointer moves one step, the other two. If the list loops back on itself, the fast one eventually laps the slow one. If it ends, the fast one hits None. It detects a cycle without any extra memory.

Real-world use #

You will rarely hand-write a linked list in application code, but the structure is all around you. Operating system schedulers, memory allocators and file systems use linked structures. LRU caches combine a hash map with a doubly linked list so both lookup and eviction are constant time.

Python's collections.deque is backed by a linked structure of blocks, which is why it adds and removes at both ends in constant time while a list cannot.

Understanding pointers and traversal also transfers directly to trees and graphs, which are linked structures with more than one next.

In practice, arrays win most of the time. Modern CPUs read contiguous memory extremely fast, so scanning an array often beats following pointers even when the theory says otherwise. Choose a linked list when you insert and remove constantly and rarely index.

Common mistakes #

• Losing the head reference during an operation, which discards the entire list.
• Forgetting the special case when deleting or inserting at the head.
• Assuming index access is cheap. There is no list[500] here.
• Creating an accidental cycle by pointing a node back at an earlier one, causing infinite traversal.
• Reaching for a linked list when a Python list or deque would be simpler and faster.

Practice #

Extend the class above with push_back (add at the end), reverse (flip the direction of all links in one pass), and middle (find the middle node using the slow and fast pointer trick). State the complexity of each.