Cả hai đều lưu trữ chuỗi (sequence), nhưng chúng có hồ sơ chi phí trái ngược nhau. Array là bộ nhớ liền kề với đánh index O(1); linked list là các node rải rác nối với nhau bằng pointer, với chèn/xóa O(1) ở hai đầu nhưng không đánh index được.
Cả hai đều lưu trữ chuỗi (sequence), nhưng chúng có hồ sơ chi phí trái ngược nhau. Array là bộ nhớ liền kề với đánh index O(1); linked list là các node rải rác nối với nhau bằng pointer, với chèn/xóa O(1) ở hai đầu nhưng không đánh index được.
| Thao tác | Array (dynamic) | Linked list |
|---|
| Truy cập theo index | O(1) | O(n) |
| Tìm kiếm | O(n) | O(n) |
| Chèn/xóa ở head | O(n) | O(1) |
| Chèn/xóa ở tail | O(1) amortized | O(1) với tail ptr |
| Chèn/xóa ở giữa | O(n) | O(n) tìm + O(1) nối |
| Chi phí bộ nhớ | thấp | cao (pointer mỗi node) |
| Tính cục bộ cache | xuất sắc | kém |
Array: [10][20][30][40] <- một khối liền kề
Linked list: [10|*]->[20|*]->[30|null] <- các node rải rác
Trong thực tế array thắng đa số trường hợp vì tính cục bộ cache lấn át các khác biệt Big-O với các kích thước thông thường.
Biết cả hai cho phép bạn biện minh lựa chọn của mình trong phỏng vấn thay vì mặc định một cách mù quáng — và giải thích tại sao "chèn O(1)" hiếm khi đánh bại một array liền kề.