Linked Lists

What is a linked list?

A linked list stores a sequence of values in separate little boxes called nodes. Each node holds two things: a value, and a reference (a pointer) to the next node. The list itself only needs to remember where the first node is. That first node is called the head. The last node points to nothing, which we write as null (None in Python, nullptr in C++).

Think of a train. Each coach is a node. You can only reach coach 5 by walking through coaches 1 to 4, but adding a new coach at the front, or unhooking one from the middle, only touches the couplings next to it. Nothing else has to move.

That is the key difference from an array. An array keeps its values side by side in one block of memory, so it can jump straight to any index. A linked list scatters its nodes around memory and connects them with pointers, so it can't jump, but it can rearrange itself cheaply.

How it works

Every operation on a linked list comes down to following pointers and changing pointers. Step through the animation to see the two most common changes: adding a node at the front, and removing a node from the middle.

Operations and their cost

Building one yourself

The implementation below keeps three fields: head, tail and size. Keeping a tail pointer is what makes adding at the back O(1). Without it you would have to walk the whole list to find the end every time.

Read through the methods in this order:

1. push_front creates a node, points it at the current head, and makes it the new head. If the list was empty, it is also the tail.
2. push_back links the current tail to the new node and moves the tail. An empty list is the special case where head and tail both become the new node.
3. insert_after walks until it finds the target value, then splices the new node in: first node.next = curr.next, then curr.next = node. Doing these the other way round loses the rest of the list.
4. remove walks with two pointers, prev and curr, so that when it finds the value it can make prev skip over curr. Removing the head (no prev) and removing the tail (update tail) are the two edge cases.
5. reverse walks once, turning each next pointer around. Save curr.next before you overwrite it.

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


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

    def push_front(self, value):
        node = Node(value)
        node.next = self.head
        self.head = node
        if self.tail is None:
            self.tail = node
        self.size += 1

    def push_back(self, value):
        node = Node(value)
        if self.tail is None:
            self.head = self.tail = node
        else:
            self.tail.next = node
            self.tail = node
        self.size += 1

    def insert_after(self, target, value):
        curr = self.head
        while curr is not None and curr.value != target:
            curr = curr.next
        if curr is None:
            return False
        node = Node(value)
        node.next = curr.next      # first, keep hold of the rest of the list
        curr.next = node           # then link the new node in
        if curr is self.tail:
            self.tail = node
        self.size += 1
        return True

    def contains(self, value):
        curr = self.head
        while curr is not None:
            if curr.value == value:
                return True
            curr = curr.next
        return False

    def remove(self, value):
        prev, curr = None, self.head
        while curr is not None and curr.value != value:
            prev, curr = curr, curr.next
        if curr is None:
            return False
        if prev is None:
            self.head = curr.next  # removing the head
        else:
            prev.next = curr.next  # bypass curr
        if curr is self.tail:
            self.tail = prev
        self.size -= 1
        return True

    def reverse(self):
        prev, curr = None, self.head
        self.tail = self.head
        while curr is not None:
            nxt = curr.next        # save the rest before overwriting next
            curr.next = prev
            prev, curr = curr, nxt
        self.head = prev

    def __str__(self):
        parts, curr = [], self.head
        while curr is not None:
            parts.append(str(curr.value))
            curr = curr.next
        return " -> ".join(parts + ["null"])


def yes_no(flag):
    return "true" if flag else "false"


items = LinkedList()
for v in (10, 20, 30):
    items.push_back(v)
print("after push_back:", items)
items.push_front(5)
print("after push_front(5):", items)
items.insert_after(20, 25)
print("after insert_after(20, 25):", items)
print("contains 25:", yes_no(items.contains(25)))
print("contains 99:", yes_no(items.contains(99)))
items.remove(10)
print("after remove(10):", items)
items.remove(30)
print("after remove(30):", items)
items.push_back(40)
print("after push_back(40):", items)
items.reverse()
print("after reverse:", items)
print("size:", items.size)

after push_back: 10 -> 20 -> 30 -> null
after push_front(5): 5 -> 10 -> 20 -> 30 -> null
after insert_after(20, 25): 5 -> 10 -> 20 -> 25 -> 30 -> null
contains 25: true
contains 99: false
after remove(10): 5 -> 20 -> 25 -> 30 -> null
after remove(30): 5 -> 20 -> 25 -> null
after push_back(40): 5 -> 20 -> 25 -> 40 -> null
after reverse: 40 -> 25 -> 20 -> 5 -> null
size: 4

Notice the remove(30) line followed by push_back(40). Removing the last node must move tail back to the previous node; if it didn't, 40 would be attached to a node that is no longer in the list. Tests like this are how you catch the classic linked-list bugs.

Doubly linked lists

In a doubly linked list every node also points back at the node before it. That costs one more pointer per node, but it lets you walk backwards and delete a node in O(1) when you already have a reference to it, without searching for its predecessor. Browser history (back and forward) and LRU caches are built this way.

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

Linked lists in the standard libraries

You will rarely need to write your own linked list outside of interviews and coursework, but it helps to know what each language gives you:

• Python: no general linked list. collections.deque is a doubly linked structure of blocks with O(1) appends and pops at both ends.
• JavaScript: no built-in linked list. Arrays cover most needs; write a class like the one above when you need O(1) inserts in the middle.
• Java: java.util.LinkedList is a doubly linked list that also works as a queue and a deque.
• C++: std::list (doubly linked) and std::forward_list (singly linked).

Common mistakes

• Losing the rest of the list. When relinking, save curr.next before you overwrite it.
• Forgetting the edge cases. Empty list, a one-node list, removing the head and removing the tail each need a moment's thought.
• Not updating tail. If you keep a tail pointer, every operation that can change the last node must update it.
• Following a null pointer. Check curr != null before reading curr.next.
• Leaking memory in C++. Every new needs a matching delete; a destructor that frees the nodes is the simplest way.

When to use a linked list

• You add and remove items at the front, or in the middle at positions you already hold, much more often than you read by index.
• You need a queue or deque and want to understand how one works underneath.
• As a building block: hash maps with chaining, LRU caches (a hash map plus a doubly linked list) and adjacency lists in graphs all use linked lists.

Avoid one when you need to jump to the i-th element quickly, or when you mostly loop over the data, where an array's memory layout wins.