Linked lists

A linked list stores each value in its own little box called a node, anywhere in memory. Each node holds its value and a pointer (the address) of the next node. The list itself only remembers the first node, the head. The last node points to nothing (None).

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

head = Node("a", Node("b", Node("c")))
node = head
while node:
    print(node.value)
    node = node.next

This flips the trade-offs of an array. Inserting at the front is instant: make a node that points to the old head, and call it the new head. Nothing else moves. Inserting after a node you already have is just as quick: change two pointers.

But there's no sum to find item number 500. You have to start at the head and follow 500 pointers, one at a time. Linked lists also use extra memory for every pointer, and following pointers around memory is slower for the processor than reading a tidy block.

In a doubly linked list each node also points back to the one before it, so you can walk both ways and remove a node without searching for its neighbour. Browsers' back and forward history and music playlists are often built this way.