Why This Matters
Array vs linked list is not a trivia question. It is a representation choice that changes indexing, traversal, memory layout, and update cost.
Decision Rule
Use an array or dynamic array when you need fast indexed access, compact storage, or repeated scanning. Use a linked list when you already hold node references and need cheap local insertion, deletion, or splicing.
Comparison Table
| Need | Array / dynamic array | Linked list |
|---|---|---|
| Access by index | O(1) | O(n) |
| Scan all elements | O(n), cache-friendly | O(n), pointer chasing |
| Insert at end | amortized O(1) for dynamic array | O(1) with tail pointer |
| Insert in middle | O(n) shift after finding index | O(1) after finding node |
| Memory overhead | low | extra pointers per node |
| Typical DSA use | two pointers, binary search, heaps | LRU links, adjacency nodes, splicing |
Worked Example
Suppose you need the 50,000th item many times. An array returns it by address calculation. A linked list must follow 50,000 links each time.
Now suppose you have a pointer to a node in the middle and need to remove it. A doubly linked list can relink neighbors in constant time. An array must shift every later element.
Common Mistakes
| Mistake | Correction |
|---|---|
Saying linked-list insertion is always O(1). | Finding the insertion point is often O(n); only the relink is O(1). |
| Ignoring cache locality. | Arrays often beat linked lists in practice for scans because memory is contiguous. |
| Using a linked list for binary search. | Binary search needs efficient middle access, so arrays fit better. |
Diagnostic Questions
| Question | Answer signal |
|---|---|
Which structure supports arr[i] in constant time? | Array or dynamic array. |
Is deleting a known doubly linked-list node O(1)? | Yes, if the node and neighbor links are available. |
| Why can an array scan be faster than a linked-list scan? | Contiguous memory gives better cache behavior. |
Exercises
- Beginner: Explain why binary search needs an array-like structure.
- Beginner: Give one problem where linked-list splicing is useful.
- Beginner: Mark each operation as array-friendly or linked-list-friendly: random access, stack push, middle splicing.
- Intermediate: Implement a tiny LRU cache using a hash table plus doubly linked list.
- Intermediate: Compare Python
listandcollections.dequefor appending at both ends. - Challenge: Benchmark scanning one million integers in a Python list versus walking a linked node structure.
References
- MIT OpenCourseWare. 6.006 Introduction to Algorithms, Spring 2020: https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/
- MIT OpenCourseWare. 6.006 Recitation on dynamic arrays, Fall 2011: https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/resources/recitation-1-asymptotic-complexity-peak-finding/