ArrayList vs LinkedList: Memory Layout, Cache Locality và Complexity thực tế

Theo lý thuyết, LinkedList chèn và xóa phần tử với độ phức tạp O(1), còn ArrayList mất O(n) vì phải dịch mảng. Vì vậy nhiều lập trình viên Java tin rằng cứ thêm/xóa nhiều thì dùng LinkedList. Trên phần cứng hiện đại, kết luận đó thường sai. Big-O chỉ đếm số bước, không tính chi phí mỗi bước: một lần truy cập RAM vì cache miss có thể chậm hơn hàng chục đến hàng trăm lần so với đọc dữ liệu đã nằm trong cache. Bài viết này mổ xẻ cách hai cấu trúc được bố trí trong bộ nhớ JVM, vì sao cache locality quyết định hiệu năng thực tế, độ phức tạp thật của từng thao tác, và đưa ra quy tắc chọn collection phù hợp với Java 21 trở lên. Ảnh 1: ArrayList lưu tham chiếu liền mạch trong Object[], LinkedList cấp phát Node rời rạc trong heap 1. Big-O không phải là toàn bộ câu chuyện Big-O mô tả tốc độ tăng của số thao tác khi n tăng, với giả định mọi thao tác truy cập bộ nhớ có chi phí như nhau. Giả định này không còn đúng từ lâu. CPU hiện đại có […]
Nguồn: https://codegym.vn/blog/arraylist-vs-linkedlist-memory-layout-cache-locality-va-complexity-thuc-te/