Insert or delete at the front: array O(n) (shift everything), linked list O(1).
Insert or delete in the middle: both O(n) to find the spot; the linked list is O(1) once you hold the node.
Append at the end: dynamic array amortised O(1), linked list O(1) with a tail pointer.
Memory: arrays are compact and cache-friendly; each list node carries a pointer and sits anywhere in memory.
Default to an array (Python list, Java ArrayList, JS array). Use a linked list when you insert or remove at the ends or at known nodes far more than you index.
✦ Definition~90s read
What is Linked List vs Array?
An array stores elements side by side in one block of memory, so you can jump to any index instantly. A linked list stores each element in its own node that points to the next one, so inserting or removing at a known position is cheap but reaching index i means walking i nodes.
★
An array is a row of numbered lockers: walk straight to locker 500.
Plain-English First
An array is a row of numbered lockers: walk straight to locker 500. A linked list is a treasure hunt: each clue tells you where the next one is, so finding the 500th clue means following 499 clues first, but slipping a new clue in between two others is easy.
"Linked list vs array" is one of the first comparisons every data structures course makes, and one of the most common interview warm-ups. The Big-O table is only half the story: on real hardware, memory layout matters as much as operation counts. This guide covers both, and you can race the two structures yourself in the array vs linked list benchmark.
How Each One Is Laid Out in Memory
An array is one contiguous block: element i lives at base address + i × element size, which is why indexing is a single calculation. A linked list allocates each node separately; a node holds a value and a pointer to the next node (and, in a doubly linked list, the previous one). Nodes can be anywhere in memory, so the only way to reach node i is to follow the pointers from the head.
layout.pyPYTHON
1
2
3
4
5
6
7
8
9
10
11
12
13
14
# Array (Python list): index straight in
prices = [10, 20, 30, 40]
print(prices[2]) # 30, one step# Linked list: follow pointersclassNode:
def__init__(self, val, nxt=None):
self.val, self.next = val, nxt
head = Node(10, Node(20, Node(30, Node(40))))
node = head
for _ in range(2): # walk 2 links to reach index 2
node = node.next
print(node.val) # 30
The linked list's O(1) splice only helps when you already hold the node; finding it is still O(n).
🎯 Key Takeaway
Arrays win indexing; linked lists win changes at the ends or at a held node.
Why Arrays Usually Win in Practice
CPUs read memory in cache lines of around 64 bytes. Scanning an array pulls in many neighbouring elements at once, so most reads hit the cache. Linked list nodes are scattered, so each step can be a cache miss, which is far slower than the operation itself. That's why, even for some operations with the same Big-O, arrays are often several times faster. Try it in the live benchmark.
💡Default choice
Reach for your language's dynamic array first: Python list, Java ArrayList, C++ std::vector, JavaScript array. Switch only when profiling or the access pattern says so.
🎯 Key Takeaway
Cache locality makes arrays faster than Big-O alone suggests.
When a Linked List Is the Right Tool
Linked lists shine when you need O(1) insert and remove at both ends or next to a node you're holding, and never need random access. Real uses: queues and deques, LRU caches (a hash map pointing into a doubly linked list), undo history, and free lists in memory allocators. In Python, collections.deque gives you the fast-ends behaviour without writing nodes yourself.
queue.pyPYTHON
1
2
3
4
5
from collections import deque
jobs = deque()
jobs.append("a"); jobs.append("b")
print(jobs.popleft()) # O(1); list.pop(0) would be O(n)
Output
a
🎯 Key Takeaway
Use linked structures for queues, LRU caches and splicing at known nodes.
● Production incidentPOST-MORTEMseverity: high
The Queue That Got Slower Every Hour
Symptom
A worker's throughput fell steadily as the backlog grew, with CPU at 100% and no single slow job.
Assumption
The team assumed removing the first element of a list was as cheap as removing the last.
Root cause
Every pop from the front of the array shifted all remaining elements: O(n) per dequeue, so draining a backlog of n items cost O(n²).
Fix
Switched to a deque (a linked or ring-buffer structure with O(1) operations at both ends), and throughput became flat regardless of backlog.
Key lesson
Removing from the front of an array is O(n).
Queues belong in a deque or linked structure, not a plain array.
Test with production-sized data: O(n²) hides at small n.
Production debug guideMatch the structure to the operations you do most4 entries
Symptom · 01
Lots of reads by index
→
Fix
Use an array. O(1) access and cache-friendly scans.
Symptom · 02
Frequent insert or remove at the front
→
Fix
Use a deque or linked list. An array shifts every element each time.
Symptom · 03
Insert or remove next to a node you already hold
→
Fix
A linked list (often doubly linked) does it in O(1); this is how LRU caches work.
Symptom · 04
Slow loops over a big list of objects
→
Fix
Arrays iterate faster because elements are contiguous; a linked list's nodes are scattered and miss the CPU cache.
⚙ Quick Reference
2 commands from this guide
File
Command / Code
Purpose
layout.py
prices = [10, 20, 30, 40]
How Each One Is Laid Out in Memory
queue.py
from collections import deque
When a Linked List Is the Right Tool
Key takeaways
1
Arrays
O(1) access, O(n) insert at the front.
2
Linked lists
O(n) access, O(1) insert at the front or at a held node.
3
Cache locality usually makes arrays faster in practice.
4
Default to a dynamic array; use a deque or linked list for queue-like work.
5
list.pop(0) in Python is O(n)
use collections.deque.
Common mistakes to avoid
3 patterns
×
Using list.pop(0) as a queue
Symptom
Gets slower as the queue grows.
Fix
Use collections.deque (Python) or ArrayDeque (Java).
×
Choosing a linked list for 'fast inserts' then searching for the position
Symptom
Still O(n) per insert.
Fix
The O(1) splice only applies when you already hold the node.
×
Indexing into a Java LinkedList in a loop
Symptom
list.get(i) in a for loop is O(n²).
Fix
Iterate with an iterator, or use ArrayList.
INTERVIEW PREP · PRACTICE MODE
Interview Questions on This Topic
Q01JUNIOR
Why is accessing an element by index O(1) in an array but O(n) in a link...
Q02SENIOR
When would you choose a linked list over an array?
Q03SENIOR
Both are O(n) to iterate. Why is the array usually faster?
Q01 of 03JUNIOR
Why is accessing an element by index O(1) in an array but O(n) in a linked list?
ANSWER
Array elements are contiguous, so the address of element i is computed directly. List nodes are scattered and only reachable by following next pointers from the head.
Q02 of 03SENIOR
When would you choose a linked list over an array?
ANSWER
When you mostly insert or remove at the ends or next to nodes you already hold and rarely index, such as queues, deques and LRU caches.
Q03 of 03SENIOR
Both are O(n) to iterate. Why is the array usually faster?
ANSWER
Cache locality: contiguous elements are loaded together in cache lines, while list nodes cause frequent cache misses.
01
Why is accessing an element by index O(1) in an array but O(n) in a linked list?
JUNIOR
02
When would you choose a linked list over an array?
SENIOR
03
Both are O(n) to iterate. Why is the array usually faster?
SENIOR
FAQ · 3 QUESTIONS
Frequently Asked Questions
01
Which is faster, a linked list or an array?
For indexing and scanning, the array, usually by a lot. For inserting or removing at the front, the linked list.
Was this helpful?
02
Is a Python list an array or a linked list?
A dynamic array of references: O(1) indexing and amortised O(1) append, but O(n) insert or pop at the front.
Was this helpful?
03
Does a linked list use more memory than an array?
Yes. Every node stores at least one pointer besides the value, and separate allocations add overhead.