Roadmap › Data Structures & Algorithms — How They Work Inside › Module: Linear Data Structures
Lessons in this course (10)
2. Arrays and dynamic arrays (how List<T> grows)
Basic★ Must knowLesson 2 of 10
An array is a contiguous block of memory: element i is at start + i × elementSize, so index access is O(1) and iteration is cache-friendly. Size is fixed.
A dynamic array (List<T>) wraps an array and grows when full:
text
Capacity 4: [a][b][c][d] Add(e) → no room
Allocate capacity 8, copy 4 items: [a][b][c][d][e][ ][ ][ ]Doubling makes Add amortised O(1): n adds cost about 2n copies in total.
| Operation | Array / List |
|---|---|
| Get/set by index | O(1) |
| Add at end | O(1) amortised |
| Insert/remove at start or middle | O(n) — shift elements |
| Search unsorted | O(n) |
| Search sorted (binary search) | O(log n) |
csharp
var list = new List<int>(capacity: 10_000); // pre-size when you know the count → no re-allocations