A guaranteed interview question — and the answer reveals whether you understand memory, not just syntax.
The difference that drives everything
Arrays are contiguous — elements sit side by side in memory, so index access is instant math. Linked lists are scattered — each node points to the next, so reaching item 500 means walking 500 pointers.
The complexity table
- Access by index: array O(1) · list O(n)
- Insert/delete at front: array O(n) (shift everything) · list O(1)
- Insert/delete in middle (given the node): array O(n) · list O(1)
- Memory: array compact · list +1 pointer per node
The senior-level point
Big-O hides cache locality: arrays are prefetched by the CPU; pointer-chasing lists cause cache misses. In practice arrays beat lists even at things lists are "better" at, until n is large. Saying this in an interview separates you from the crowd.
Where lists actually live
- Implementing queues/deques, LRU caches (hashmap + doubly linked list)
- Undo history, music playlists
Practice the classic: Reverse a Linked List on our judge — three pointers, prev/cur/next.
← All Articles