Data structures and patterns · Question 36 of 50

Array or linked list?

What they're checking

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 shifts
The follow-up they'll ask

How 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.

Your progress stays on this device.