Difference Between Array and Linked List
Array vs linked list compared — memory layout, access, insertion and deletion complexity, cache locality — with examples and DSA interview questions answered.
Expected Interview Answer
An array stores elements in contiguous memory with fixed-size, index-based access in O(1), while a linked list stores elements as nodes scattered in memory, each pointing to the next, giving O(1) insertion/deletion but O(n) access.
Arrays give instant random access by index and are cache-friendly, but inserting or deleting in the middle costs O(n) because elements must shift, and resizing may require reallocation. Linked lists make insertion and deletion cheap once you hold the node, and grow without reallocation, but reaching the k-th element requires walking from the head, and the per-node pointers add memory overhead and hurt cache locality.
- Array: O(1) random access by index
- Array: cache-friendly contiguous memory
- Linked list: O(1) insert/delete at a known node
- Linked list: grows without reallocation
AI Mentor Explanation
An array is like numbered stadium seats in a row — seat 34 is instantly found because seats are contiguous and numbered, but squeezing a new seat into the middle means shifting everyone down. A linked list is like a relay of players where each holds the next one’s hand: adding a player mid-chain just re-links two hands, but reaching the tenth player means passing down the chain from the first. Instant access versus cheap insertion — the core trade.
Step-by-Step Explanation
Step 1
Memory layout
Array: contiguous block. Linked list: scattered nodes joined by pointers.
Step 2
Access
Array: O(1) by index. Linked list: O(n) — walk from the head.
Step 3
Insert/delete
Array: O(n) shifting. Linked list: O(1) at a known node.
Step 4
Overhead
Linked list stores extra pointers and is less cache-friendly than an array.
Step 5
Choose
Frequent indexed reads → array; frequent mid-sequence edits → linked list.
What Interviewer Expects
- Contiguous vs pointer-based memory layout
- Access, insert and delete complexities for both
- Cache locality and pointer overhead awareness
- When to prefer each
Common Mistakes
- Saying linked lists allow O(1) random access
- Forgetting arrays need shifting on middle insertion
- Ignoring cache-friendliness of arrays
- Claiming one is always faster than the other
Best Answer (HR Friendly)
“An array stores items side by side so you can jump to any position instantly, but adding or removing in the middle is slow. A linked list chains items with pointers, making insertion and deletion cheap, but reaching a specific item means walking through the chain. You pick based on whether you read by position or edit the middle more often.”
Code Example
arr = [10, 20, 30, 40]
print(arr[2]) # O(1) direct access → 30
class Node:
def __init__(self, val):
self.val = val
self.next = None
# find the 3rd node → O(n) traversal from head
node = head
for _ in range(2):
node = node.next
print(node.val)Follow-up Questions
- What is a doubly linked list and when is it useful?
- How does a dynamic array (e.g. Python list) resize?
- What is the time complexity of inserting at the head of each?
- Why are arrays more cache-friendly than linked lists?
MCQ Practice
1. Random access by index is O(1) for?
Contiguous memory lets arrays compute an element’s address directly.
2. Inserting in the middle is cheaper (O(1) at a known node) for?
A linked list just re-points neighboring nodes; an array must shift elements.
3. Which structure is generally more cache-friendly?
Arrays store elements contiguously, improving CPU cache locality.
Flash Cards
Array access time? — O(1) random access by index (contiguous memory).
Linked list access time? — O(n) — must traverse from the head node.
Linked list insert/delete? — O(1) at a known node; no shifting required.
Array insert/delete in middle? — O(n) — elements must shift to fill or make room.