Array versus linked list
“When would you choose a linked list over an array, and when is that choice wrong?”
What this tests
- Whether the candidate distinguishes asymptotic cost from real cost (cache locality).
- Understanding that
O(1)insertion in a linked list requires already holding the node. - Knowledge of the cases where linked lists genuinely win.
Strong answer
An Array stores elements contiguously: O(1) index access, excellent cache behaviour, but O(n) insertion or deletion in the middle because elements shift. A Linked List stores nodes with pointers: O(1) insertion or deletion given a reference to the neighbouring node, but O(n) to reach position i and poor locality because every step is a pointer dereference to a possibly distant address.
The linked list wins in a narrow set of cases: you already hold a pointer to the node being spliced (an LRU Cache moving a node to the front, a queue implemented as a list, an iterator that removes as it goes), or you need stable references that survive insertions elsewhere. It loses in almost every other case, including the textbook "lots of insertions in the middle" — because finding the middle is O(n) anyway, and a Dynamic Array shifting memory with memmove is often faster in practice than pointer chasing.
A strong candidate says that in interviews the linked list mostly appears as a *given* input (reverse it, detect a cycle with Fast & Slow Pointers, merge two sorted lists) rather than a structure you should choose, and that a dynamic array is the sane default.
Green flags · Red flags
- Qualifies "O(1) insertion" with "if you already have the node".
- Brings up cache locality unprompted.
- Names LRU cache as the canonical case where a doubly linked list is the right answer.
- Says dynamic array is the default choice.
- Claims linked lists are better "when there are many insertions" without qualification.
- Thinks linked list access by index is
O(1). - Does not know what a dynamic array is or how amortized append works.
Follow-up questions
Each follow-up changes a requirement; the right answer changes with it.
O(1) LRU cache?O(1) if resizing is O(n)?