Array vs Linked List
Use an array by default. Reach for a linked list only when you insert or remove in the middle and already hold a reference to the node, which is rarer than the textbook comparison suggests.
The usual table says arrays are O(1) to read and O(n) to insert, and linked lists the reverse. That table is correct and still misleads, because it counts operations and ignores what the hardware does. An array's elements sit next to each other, so walking one is a sequential read the cache prefetches. A linked list's nodes can be anywhere, so walking one is a chain of dependent loads that the CPU cannot predict.
Side by side
| Dimension | Array | Linked List |
|---|---|---|
| Access by index | O(1) | O(n), you must walk there |
| Insert or delete at a known node | O(n), everything after it shifts | O(1), repoint two pointers |
| Insert or delete by position | O(n) | O(n), because finding it is O(n) |
| Append at the end | Amortised O(1) | O(1) with a tail pointer |
| Memory per element | Just the value | The value plus one or two pointers |
| Cache behaviour | Sequential, prefetchable | Scattered, a dependent load per node |
| Split or join | Requires copying | O(1), rewire the ends |
When to pick each
Array
- You read by index, or you scan the whole thing. This covers most code.
- Memory matters. An ArrayList of a million Integers already costs more than an int array; a LinkedList adds two more references per element.
- You need to sort, binary search, or take a subrange.
Linked List
- You splice nodes in and out and already hold the node, as an LRU cache does when its hash map hands over the exact node to move.
- You need to join or split sequences in constant time.
- The problem itself is about pointer manipulation, which in interviews it often is.
Choosing a linked list because insertion is O(1), then writing code that searches for the insertion point first. That search is O(n), so the whole operation is O(n) and you have paid the memory and cache cost for nothing. The O(1) only materialises when something else already gave you the node, which is why LRU caches pair a linked list with a hash map rather than using it alone.
Questions people ask
Why is ArrayList usually faster than LinkedList even for insertions?
Because shifting elements is one sequential memory move, which modern hardware does extremely fast, while walking a linked list to the insertion point is a series of unpredictable jumps. For lists below a few thousand elements ArrayList typically wins even where the complexity table says it should not.
When does the array's O(n) insert actually hurt?
When the list is large and insertions are frequent and in the middle. If you are appending, the amortised cost is O(1), and if you are inserting at the front repeatedly, an ArrayDeque solves it without giving up contiguity.
Do interviewers still ask this?
Often, and rarely to hear the complexity table. The answer that lands is the one that mentions cache locality and then names a concrete case where a linked list genuinely wins, such as the doubly linked list inside an LRU cache.