Chuyển tới nội dung chính

Mảng vs linked list: chọn cái nào?

Bạn sẽ học được gì

Hai cấu trúc cùng lưu một dãy phần tử, nhưng đánh đổi ngược nhau. Bài này tổng kết khi nào chọn mảng, khi nào chọn linked list — kèm một yếu tố thực tế hay bị bỏ quên: cache.

1. Bảng so sánh đầy đủ​

Tiêu chíMảngLinked list
Truy cập phần tử thứ iO(1) ✅O(n)
Tìm kiếm (chưa sắp xếp)O(n)O(n)
Thêm/xóa ở ĐẦUO(n)O(1) ✅
Thêm/xóa ở CUỐIO(1)*O(1) nếu giữ con trỏ đuôi
Thêm/xóa ở GIỮA (đã có con trỏ)O(n)O(1) ✅
Bộ nhớ thêmkhôngmỗi nút +1 con trỏ
Tính cục bộ cachetốt ✅kém

*Thêm cuối mảng động là amortized O(1).

2. Yếu tố ẩn: tính cục bộ cache (cache locality)​

Trên lý thuyết cả hai đều "O(n) khi duyệt". Nhưng thực tế mảng thường nhanh hơn khi duyệt, vì các phần tử nằm liền kề → CPU nạp cả khối vào cache một lần, đọc rất nhanh. Linked list rải rác khắp bộ nhớ → mỗi nút có thể là một lần "đi tìm" tốn kém (cache miss).

Bài học thực tế: với dữ liệu duyệt tuần tự nhiều, mảng thường thắng dù cùng Big-O, nhờ cache. Big-O cho biết xu hướng, nhưng hằng số ẩn (do cache) cũng quan trọng trong đời thực.

3. So tốc độ thực tế (chạy thử)​

Đang tải trình chạy code…

Chèn đầu mảng (O(n) mỗi lần) đắt hơn hẳn — đây chính là lúc linked list (chèn đầu O(1)) toả sáng.

4. Cây quyết định: chọn cái nào?​

Cần truy cập theo chỉ số nhiều?  ──Có──▶  MẢNG (O(1) truy cập)
        │ Không
        ▼
Thêm/xóa liên tục ở đầu/giữa?    ──Có──▶  LINKED LIST (O(1) sửa con trỏ)
        │ Không
        ▼
Duyệt tuần tự là chính?          ──Có──▶  MẢNG (cache tốt hơn)
        │
        ▼
   Mặc định: MẢNG (đơn giản, cache tốt, đủ dùng đa số trường hợp)

Sự thật thực tế: đa số lúc, mảng động là lựa chọn mặc định tốt nhờ đơn giản + cache. Linked list toả sáng ở các tình huống chuyên biệt: hàng đợi/ngăn xếp, deque, LRU cache, khi thêm/xóa đầu là thao tác chính.

5. Mẫu nhận diện​

  • Hỏi "truy cập theo vị trí nhiều không?" → Có thì mảng.
  • Hỏi "thêm/xóa đầu/giữa nhiều không?" → Có thì linked list.
  • Không chắc → mặc định mảng (cache + đơn giản), đổi sang linked list khi đo được lợi ích.

6. 🎮 Trò chơi: Chọn cấu trúc​

🎮 Mảng hay linked list?Câu 1/4· Điểm 0· 🔥 0

Truy cập chỉ số / duyệt tuần tự → mảng. Thêm/xóa đầu-giữa liên tục → linked list.

Cần lấy phần tử thứ i rất thường xuyên theo chỉ số.

7. Quiz kiểm tra nhanh​

📝 Quiz kiểm tra nhanh
1. Mảng thắng linked list rõ nhất ở thao tác nào?
2. Linked list thắng mảng rõ nhất ở?
3. Vì sao mảng thường nhanh hơn khi duyệt dù cùng O(n)?

8. Hoàn thành — XONG Chương 2.2! 🎉​

…

☑️ Hết Chương 2.2 (Danh sách liên kết). Tiếp theo: 2.3.1 — Ngăn xếp (Stack).