116. When would you choose a linked list over a dynamic array?
EasyLinked lists
Technical
Show model answer
Linked lists give O(1) insertion and deletion at a known position (given a pointer to the node or its predecessor), O(1) concatenation and splitting, and no reallocation. Arrays give O(1) random access, compact contiguous storage and much better cache locality; inserting or deleting in the middle costs O(n) element shifts.
In practice arrays win for most workloads, even with middle insertions on moderate sizes, because of cache effects. Linked lists remain the right choice for LRU caches (a hash map plus a doubly linked list), free lists in allocators, intrusive lists in kernels and lock-free queues, where stable node addresses and O(1) splicing matter.