Data structures and patterns · Question 36 of 50
Array or linked list?
Memory layout, complexity, and the CPU cache.
The answer
An array is one block of memory: reading index i is O(1), and walking it is fast because neighbours sit in the CPU cache. Inserting or deleting in the middle is O(n), since everything after it shifts, and a dynamic array grows by copying (appends are O(1) on average).
A linked list is nodes scattered in memory, each pointing to the next: inserting or deleting at a node you already hold is O(1), but reaching index i is O(n), and following pointers misses the cache. In practice arrays win most of the time; linked lists shine in queues, in LRU caches (with a hash map) and when you splice a lot.
The picture
array: [10][20][30][40] side by side: a[2] in one step
list: (10)─▶(20)─▶(30)─▶(40) scattered: walk to reach the third
insert 25 after (20): change two pointers, nothing shiftsHow does a dynamic array give O(1) appends on average?
Show the answer
It doubles its capacity when it is full; the copying, spread across all the appends, averages out to a constant.