Both store sequences, but they have opposite cost profiles. An array is contiguous memory with O(1) indexing; a linked list is scattered nodes joined by pointers, with O(1) insert/remove at the ends but no indexing.
Both store sequences, but they have opposite cost profiles. An array is contiguous memory with O(1) indexing; a linked list is scattered nodes joined by pointers, with O(1) insert/remove at the ends but no indexing.
| Operation | Array (dynamic) | Linked list |
|---|
| Access by index | O(1) | O(n) |
| Search | O(n) | O(n) |
| Insert/delete at head | O(n) | O(1) |
| Insert/delete at tail | O(1) amortized | O(1) with tail ptr |
| Insert/delete in middle | O(n) | O(n) find + O(1) splice |
| Memory overhead | low | high (pointer per node) |
| Cache locality | excellent | poor |
Array: [10][20][30][40] <- one contiguous block
Linked list: [10|*]->[20|*]->[30|null] <- scattered nodes
In practice arrays win most of the time because cache locality dwarfs Big-O differences for typical sizes.
Knowing both lets you justify your choice in interviews instead of defaulting blindly — and explain why "O(1) insert" rarely beats a contiguous array.