Linked lists

A linked list is a sequence of nodes, each holding a value and a pointer to the next. O(1) insert/remove at either end (if you keep a tail pointer), but O(n) to reach an element by index, because you have to chase pointers from the head. Unlike arrays, memory isn't contiguous — which matters more than textbooks admit: pointer chasing defeats the CPU cache, so even O(n) operations that should be fast run slower than on an array. That's why linked lists are rare in practice despite being beloved in interviews — a dynamic array usually beats them for real workloads. They do shine when insertion cost dominates (big queues with frequent front-pops), when you need to splice mid-list without copying, or when building richer structures (LRU caches combine a hash map with a doubly-linked list to get O(1) access plus O(1) reordering).