What is the difference between an array and a linked list?
An array stores elements in one continuous block of memory, so it gives fast access by index in O(1) but inserting or removing in the middle is slow because elements must shift. A linked list stores elements as nodes connected by pointers, so inserting or removing is fast in O(1) if you have the node, but finding an element takes O(n) because you must walk the list.
- Arrays store elements in one contiguous block, giving O(1) access by index but O(n) inserts due to shifting.
- Linked lists store nodes connected by pointers, giving O(1) inserts at a known node but O(n) search.
- Arrays are cache friendly because data is contiguous, which often makes them faster in practice.
How they store data
An array is like seats in a row that are numbered, so you can jump straight to seat 5. A linked list is like a treasure hunt where each note points to the next one, so to reach the fifth note you must follow four notes first.
Quick comparison
- Access by index: array is O(1), linked list is O(n).
- Insert or delete at a known position: array is O(n) due to shifting, linked list is O(1).
- Memory: array uses one block, linked list uses scattered nodes with extra pointer memory.
- Cache: arrays are cache friendly because data is contiguous, linked lists are not.
A great closing line is that arrays win when you read a lot by index, and linked lists win when you insert and remove a lot. Mentioning cache friendliness of arrays is a detail that impresses interviewers.
Frequently asked questions
When should you use a linked list over an array?
Use a linked list when you insert and remove often, especially at the front, and rarely need random access by index.
Why is array access faster than linked list access?
An array can jump straight to any index by computing an address, while a linked list must follow pointers one node at a time to reach a position.
What is a doubly linked list?
It is a linked list where each node points to both the next and the previous node, which makes moving backward and deleting a node easier.
Common follow up questions
Related interview questions
Want the full DSA guide?
Read every DSA concept with notes, diagrams, and code in one place. Track your progress as you go.
Open the DSA guide All DSA questions