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.
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.
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