Array là một khối bộ nhớ liền kề chứa các phần tử cùng kiểu, được đánh index từ 0. Vì các phần tử nằm cạnh nhau, địa chỉ của phần tử i được tính trực tiếp là base + i * elementSize, cho truy cập ngẫu nhiên O(1).
index: 0 1 2 3 4
+-----+-----+-----+-----+-----+
arr = | 10 | 20 | 30 | 40 | 50 |
+-----+-----+-----+-----+-----+
address: base +4 +8 +12 +16 (số nguyên 4-byte)
arr = [10, 20, 30, 40, 50]
x = arr[3] # O(1) — tính index trực tiếp
arr.append(60) # amortized O(1) (dynamic array)
arr.insert(0, 5) # O(n) — dịch mọi phần tử sang phải
arr.pop(0) # O(n) — dịch mọi phần tử sang trái
| Thao tác | Thời gian |
|---|---|
| Truy cập theo index | O(1) |
| Tìm kiếm (chưa sắp xếp) | O(n) |
| Append (dynamic) | O(1) amortized |
| Chèn/xóa ở đầu/giữa | O(n) |
Array là nền tảng dưới hầu hết các cấu trúc khác — string, hash table, heap, và dynamic list đều xây dựng trên chúng.
Tính cục bộ cache (cache locality) của chúng thường khiến một array "chậm hơn" theo Big-O lại vượt qua một cấu trúc dựa trên pointer "nhanh hơn" trong các benchmark thực tế.