Linked lists

A linked list stores each item in its own node, together with a pointer to the next node. In a doubly linked list, each node also points to the one before. Inserting or removing a node you already hold is O(1), because nothing has to shift.

But reaching the i-th item means walking from the head (the first node), which is O(n). Nodes scattered around memory are also slow for the CPU cache. In everyday code you will nearly always choose a dynamic array instead.

Build a linked list anyway. Writing insert, delete and reverse makes references concrete, and linked nodes are how stacks, queues, trees and graphs are built. Draw boxes and arrows on paper before you write any pointer code.