Array vs. Linked List
After this topic
You will be able to explain the difference in memory structure between arrays and linked lists, and determine which one to choose depending on the situation.
Array – Contiguous Memory
An array stores data contiguously in memory.
Memory Address: 100 104 108 112 116
+----+----+----+----+----+
Value: | 10 | 20 | 30 | 40 | 50 |
+----+----+----+----+----+
Index: 0 1 2 3 4The advantage is immediate access by index.
arr = [10, 20, 30, 40, 50]print(arr[3]) # 40 — immediate access (O(1))If you say "the 3rd slot," it's simply the starting address + (3 × size) = directly to that location. No matter how many elements, it finds it at once.
Array's Weakness: Insertion and Deletion
To insert 15 at index 1 in [10, 20, 30, 40, 50]?
Step 1: Shift 20, 30, 40, and 50 one slot to the right.
Step 2: Place 15 in the empty slot.
[10, 15, 20, 30, 40, 50]If there are 1 million data points, inserting at the very beginning requires shifting all 1 million data points.
Linked List – Scattered Memory
A linked list stores each data point and remembers the location of the next data point.
[10|→] → [20|→] → [30|→] → [40|→] → [50|∅]
Each node = value + address of the next node (pointer)It doesn't need to be stored contiguously in memory. Each node just needs to know "what's next."
Linked List's Advantage: Insertion and Deletion
To insert 25 after 20 in [10|→] → [20|→] → [30|→]:
Step 1: Create a new node [25|→].
Step 2: Change the pointer of 20 to 25, and the pointer of 25 to 30.
[10|→] → [20|→] → [25|→] → [30|→]No need to move other nodes. Just change two pointers. O(1).
Linked List's Weakness: Access
# "What is the 3rd value?"# Array: arr[3] → immediate (O(1))# Linked list: must follow 1→2→3 from the beginning (O(n))Since there is no index, finding the nth value requires following from the beginning n times.
Comparison Summary
| Operation | Array | Linked List |
|---|---|---|
| Index Access | O(1) Immediate | O(n) Requires traversal |
| Search | O(n) Traversal | O(n) Traversal |
| Insert at Beginning | O(n) Shift all elements | O(1) Change pointer |
| Insert at End | O(1) Add to the end | O(1) if tail pointer exists |
| Insert in Middle | O(n) Shifting | O(1) Change pointer |
| Memory | Requires contiguous memory | Can be scattered |
Selection Criteria
| Situation | Recommendation |
|---|---|
| Frequent access by index | Array |
| Frequent insertions/deletions | Linked list |
| Size changes frequently | Linked list |
| Memory efficiency is important | Array (no pointer overhead) |
| Cache friendliness is needed | Array (contiguous memory) |
In practice, most of the time we use arrays (Python's list, JavaScript's Array). Modern languages' dynamic arrays automatically adjust the size and are beneficial for CPU caching. Linked lists are used in special cases (queue, stack implementation, large-scale insertions/deletions).