Sự khác biệt giữa tìm kiếm trên mảng (Array) và tìm kiếm trên danh sách liên kết (Linked List) về mặt hiệu năng bộ nhớ và tốc độ truy xuất là gì?

Question

Accepted Answer

Mảng (Array)

Ưu điểm: Hỗ trợ truy cập ngẫu nhiên (random access) thông qua chỉ số, cho phép áp dụng các thuật toán như Binary Search (O(log n)).
Nhược điểm: Cần khối bộ nhớ liên tục, khó thay đổi kích thước khi đã khởi tạo.

Danh sách liên kết (Linked List)

Ưu điểm: Cấp phát bộ nhớ động, chèn/xóa phần tử nhanh nếu đã biết vị trí.
Nhược điểm: Không hỗ trợ truy cập ngẫu nhiên. Để tìm kiếm một phần tử, bắt buộc phải duyệt tuần tự từ đầu danh sách (Linear Search) với độ phức tạp O(n).

Kết luận
Trong các bài toán yêu cầu tìm kiếm hiệu năng cao, Array luôn là lựa chọn ưu tiên nhờ tính chất lưu trữ liên tục trong bộ nhớ (cache-friendly), giúp CPU truy xuất dữ liệu nhanh hơn nhiều so với việc nhảy qua các con trỏ (pointer) trong Linked List.