Singly and doubly linked lists

A linked list stores each item in its own node, and each node points to the next one, like a trail of clues where each tells you where the next is. In a singly linked list the nodes only point forward. In a doubly linked list each node also points back to the previous one.

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 start (the head), which is O(n). You will rarely pick one over a dynamic array, but they matter for two reasons.

They are the building block of other structures, such as LRU caches and the chains inside hash maps. And pointer problems, like reversing, merging or finding the middle, are the best practice there is for careful code. A dummy head node, a fake first node before the real ones, removes most edge cases.