Linked Lists6 min read

Singly Linked List

A chain of boxes — each one knows only where the next box is

access: \(O(n)\)insert head: \(O(1)\)insert tail: \(O(n)\)delete: \(O(n)\)space: \(O(n)\)

Imagine a treasure hunt. You start with one clue. That clue doesn't give you the treasure — it points you to the next clue. That next clue points to the one after that, and so on until the last clue says "X marks the spot."

A singly linked list works exactly like that. Each item — called a node — is a small box that holds two things: a value (the actual data) and a pointer (a sticky note pointing to the next box in the chain). The very last node's pointer says null — meaning the chain ends here.

The only entry point is the head pointer, which always points to the very first node. To reach any other node, you must follow the chain from the head, one node at a time.

How is this different from an array?

In an array, all boxes sit side-by-side in memory — you can jump directly to box number 5. In a linked list, the boxes can be scattered anywhere in memory. The only path between them is the pointer inside each node. This makes access slow, but makes adding and removing nodes at the front incredibly fast.

◈ Follow the chain!

← → arrow keys to step · click elements to interact

Linked List Operations

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

class LinkedList:
    def __init__(self):   self.head = None
    def prepend(self, v): n=Node(v); n.next=self.head; self.head=n
    def append(self, v):
        n = Node(v)
        if not self.head: self.head = n; return
        cur = self.head
        while cur.next: cur = cur.next
        cur.next = n
    def to_list(self):
        out, cur = [], self.head
        while cur: out.append(cur.val); cur = cur.next
        return out

ll = LinkedList()
ll.append(1); ll.append(2); ll.append(3)
ll.prepend(0)
print(ll.to_list())  # [0, 1, 2, 3]

Output

[0, 1, 2, 3]

Why is access \(O(n)\)?

Want the 4th node? There's no shortcut. You start at the head, follow its pointer to node 2, follow that to node 3, follow that to node 4. Every step costs one pointer-follow. If your list has 1,000 nodes and you want the last one, you follow 1,000 pointers. That's \(O(n)\) — it grows with the size of the list.

Compare that to an array: arr[999] is instant because the computer calculates the memory address directly. Linked lists give up that superpower in exchange for flexibility.

Why is inserting at the head \(O(1)\)?

Here's the magic. To add a new node at the front, you only need to do two things:

Set the new node's pointer to point at the current head.
Update the head pointer to point at the new node.

That's it — two pointer changes, regardless of how long the chain is. No shifting, no copying. The rest of the list doesn't even know anything happened.

Deleting a node

To delete a node from the middle of the list, you first need to find it — which costs \(O(n)\). Once you've found its predecessor, deletion itself is just one pointer change: make the predecessor point to the deleted node's successor. The actual removal is \(O(1)\), but the search to get there is \(O(n)\).

Note: Think of a linked list as a paper chain — each ring is linked to the next. To find ring #10, you have to count through rings 1, 2, 3... one by one. But adding a new ring at the start? Just hook it onto the front — takes one second.

Complexity

Access by positionMust follow chain from head

Slow\(O(n)\)

Insert at headTwo pointer changes only

Instant\(O(1)\)

Insert at tailMust traverse to find the tail

Slow\(O(n)\)

Delete (find + remove)\(O(n)\) to find, \(O(1)\) to unlink

Slow\(O(n)\)

SpaceOne node per element

Grows with n\(O(n)\)

When should you use a singly linked list?

You're frequently inserting or deleting at the front of the collection
You don't need random access by index
You want to implement a stack or a simple queue
The size of the data changes unpredictably and you don't want to allocate a large buffer

When should you avoid it?

You frequently access elements by position — use an array instead
You need to traverse both forwards and backwards — consider a doubly linked list
Memory is tight — every node carries extra overhead for its pointer

Challenge

Find Middle Node (Slow & Fast Pointers)

class Node:
    def __init__(self, v): self.val=v; self.next=None

def find_middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow.val

# Build: 1 -> 2 -> 3 -> 4 -> 5
vals = [1, 2, 3, 4, 5]
nodes = [Node(v) for v in vals]
for i in range(len(nodes)-1): nodes[i].next = nodes[i+1]

print(find_middle(nodes[0]))  # 3

Output

Quick check

A singly linked list has 5 nodes. How many steps does it take to read the value of the 5th node?

Doubly Linked List

A two-way chain — each node knows both its neighbour ahead and the one behind

→

Reversing a Linked List

Flip the entire chain so the last node becomes first — iteratively or recursively

→

Floyd's Cycle Detection

Catch a loop in a linked list using just two pointers and no extra memory

→