Arrays vs Linked Lists — When to Use Each
The Interview Question
What are the differences between arrays and linked lists? When would you choose one over the other?
Expert Answer
Arrays store elements in contiguous memory with O(1) random access by index. Linked lists store elements in nodes scattered across memory, each pointing to the next, with O(n) access by index but O(1) insertion/deletion at a known position. But the textbook analysis misses the most important real-world factor: cache locality. Because array elements are contiguous in memory, iterating through an array is dramatically faster in practice — CPU cache lines load adjacent elements automatically. Linked list nodes are scattered across the heap, causing cache misses on nearly every access. This is why arrays (and dynamic arrays like ArrayList/Vector) are the default choice in almost every scenario. Linked lists win in specific cases: when you need constant-time insertion/deletion at arbitrary positions with a known reference (not index), or when you're implementing a queue (doubly-linked list), LRU cache (linked list + hash map), or operating system memory allocator (free lists).
Key Points to Hit in Your Answer
- Array: O(1) access, O(n) insert/delete (shifting), contiguous memory
- Linked List: O(n) access, O(1) insert/delete at known node, scattered memory
- Cache locality makes arrays vastly faster for iteration in practice
- Dynamic arrays (ArrayList) amortize resize cost to O(1) append
- Linked lists are used in: LRU caches, queues, free memory lists, undo stacks
- In interviews, default to arrays unless the problem specifically needs linked list properties
Code Example
// Dynamic array — amortized O(1) append
// When full, allocate 2x array and copy
// Cost of n appends: n + n/2 + n/4 + ... ≈ 2n → O(1) amortized
// Linked List — O(1) insert at head
class ListNode {
constructor(value, next = null) {
this.value = value;
this.next = next;
}
}
function insertAtHead(head, value) {
return new ListNode(value, head); // O(1)
}
// LRU Cache = HashMap + Doubly Linked List
// HashMap gives O(1) lookup
// Linked List gives O(1) move-to-front and evictionWhat Interviewers Are Really Looking For
Mentioning cache locality immediately signals real-world understanding beyond textbook complexity. Knowing that linked lists are rarely the right choice in modern code (except specific patterns like LRU cache) shows practical judgment. Follow-up: 'Reverse a linked list' — the most common linked list interview question.
Practice This Question with AI Grading
Reading about interview questions is a start — but practicing with real-time AI feedback is how you actually get better. Goliath Prep grades your answers instantly and tells you exactly what you're missing.
Start Practicing Free →