Array vs Linked List for Interviews — When to Use Which, and Why Array Almost Always Wins
The trade-off between arrays (dynamic arrays) and linked lists in coding interviews — random access vs constant-time insertion, cache locality vs pointer chasing, and the small set of problems where linked list actually earns its keep.
The array-vs-linked-list debate is settled in production — use an array. But interviewers keep asking about linked lists because they're a clean stress-test for pointer arithmetic. This post is the tie-breaker: which one belongs in your solution, when linked list genuinely wins (spoiler: rarely), and which interview problems only exist because linked lists are the input.
The verdict
Array (dynamic array). O(1) random access, O(1) amortised append, excellent cache locality. The right default for almost every interview problem where you get to choose.
Linked list. O(1) insert and delete given a node pointer, O(n) access. Wins only in a narrow band: constant-time mid-sequence splicing with many operations, or when the problem hands you a linked list as input.
Ask two questions:
- Did the problem hand me a linked list? If yes, work with it — no choice. LC 21, 141, 143, 206, 234 all give you linked list inputs. The pattern is pointer manipulation (
prev,curr,next) not "should I convert this to an array?" - Do I need O(1) mid-sequence insert or delete with many operations? If yes and you have a pointer to the position, linked list. This is the LRU-cache case — but the LRU cache also needs O(1) lookup, so it pairs the linked list with a hash map.
Everything else: array.
When to reach for an array
- Random access.
nums[i]is O(1). Any problem that hits arbitrary indices belongs here. - Iteration. Dynamic arrays are contiguous — cache lines pull in multiple elements per fetch. Iteration is often 10× faster in practice than a linked list of the same length, despite identical O(n) asymptotics.
- Small n. Under a few thousand elements, the constant-factor gap swamps any theoretical linked-list advantage.
- Any pattern that needs indices. Sliding window, two-pointer, binary search, monotonic stack — all rely on random access.
- Building an output list.
result.append(x)is amortised O(1); the linked-list equivalent needs a tail pointer to avoid O(n) per append.
When to reach for a linked list
- The problem hands you one. LC 21 Merge Two Sorted Lists, LC 141 Linked List Cycle, LC 143 Reorder List, LC 206 Reverse Linked List, LC 234 Palindrome Linked List. Work with the pointers you're given; converting to an array either violates the problem or wastes O(n) auxiliary space.
- Constant-time splice at a known position, with many operations. Removing a node given a pointer to it is O(1) on a doubly linked list. On an array it's O(n). If your algorithm does this a lot, the linked list wins.
- LRU cache. Doubly linked list + hash map: O(1) lookup (via the map), O(1) move-to-front (via the list), O(1) evict. Neither structure alone works.
- A fixed-size ring buffer / free list, common in embedded and systems interviews.
That's the list. Anything not on it: array.
Side by side
| Operation | Dynamic array | Singly linked list | Doubly linked list |
|---|---|---|---|
Access [i] | O(1) | O(n) | O(n) |
| Search by value | O(n) | O(n) | O(n) |
| Insert at head | O(n) | O(1) | O(1) |
| Insert at tail | O(1)* | O(1) with tail ptr | O(1) with tail ptr |
| Insert at arbitrary position (given index) | O(n) | O(n) — walk to node | O(n) — walk to node |
| Insert at arbitrary position (given node pointer) | O(n) | O(1) | O(1) |
| Delete at head | O(n) | O(1) | O(1) |
| Delete given node pointer | O(n) — need to walk | O(n) — need prev pointer | O(1) |
| Delete by value | O(n) | O(n) | O(n) |
| Iteration | O(n), cache-friendly | O(n), cache-hostile | O(n), cache-hostile |
| Space overhead per element | O(1) — just the value | O(1) — value + pointer | O(1) — value + 2 pointers |
| Reverse | O(n) | O(n) | O(n) |
The bolded advantages of linked lists — O(1) insert-at-head and O(1) delete-given-pointer — only cash in when the problem actually needs them. For the vast majority of interview problems, the dynamic array's O(1) random access is the deciding factor.
Worked example — array (LC 26 Remove Duplicates from Sorted Array, in place)
Given a sorted array, remove duplicates in place and return the new length.
Two-pointer scan with a write pointer trailing a read pointer. Trivial with random access; painful with a linked list because you'd need a prev pointer to unlink duplicates.
def removeDuplicates(nums):
if not nums:
return 0
write = 1
for read in range(1, len(nums)):
if nums[read] != nums[read - 1]:
nums[write] = nums[read]
write += 1
return write
O(n) time, O(1) space. The array's O(1) nums[write] = nums[read] is what makes the two-pointer pattern natural.
Worked example — linked list (LC 206 Reverse Linked List)
Reverse a singly linked list.
The problem gives you a linked list; you work with pointers. No array involved.
def reverseList(head):
prev = None
while head:
head.next, prev, head = prev, head, head.next
return prev
The single-line multi-assignment is the interview-classic form. Doing this "with an array" — copy values into a list, reverse, rebuild the list — is O(n) space instead of O(1) and defeats the point of the exercise.
Bottom line
Ask: did the problem hand me a linked list, or do I need O(1) mid-sequence splicing with many operations?
- Yes to either — linked list. Work with pointers; don't convert.
- No — array. Every pattern in the series (sliding window, two-pointer, binary search, monotonic stack, backtracking, BFS / DFS) assumes O(1) random access. Reaching for a linked list voluntarily is almost always a step backward.
For the per-language details on linked-list implementations — Python doesn't ship one; Java's LinkedList is almost always slower than ArrayList in practice — see the time-complexity-of-common-operations post.