Trang chủ » Blog » ArrayList vs LinkedList: Memory Layout, Cache Locality và Complexity thực tế

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.

So sánh memory layout của ArrayList và LinkedList trong heap

Ả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ó nhiều tầng bộ nhớ đệm, với độ trễ tham khảo như sau (thay đổi tùy kiến trúc):

L1 cache: khoảng 1 ns (vài chu kỳ CPU).
L2 cache: khoảng 3–5 ns.
L3 cache: khoảng 10–20 ns.
RAM: khoảng 60–100 ns.

CPU không đọc từng byte mà đọc theo cache line, thường là 64 byte. Ngoài ra, bộ hardware prefetcher nhận ra mẫu truy cập tuần tự và nạp trước các cache line tiếp theo. Một cấu trúc dữ liệu “thân thiện với cache” sẽ tận dụng được cả hai cơ chế này; một cấu trúc rời rạc sẽ không tận dụng được cơ chế nào.

Đó là lý do vì sao hai thuật toán cùng O(n) có thể chênh nhau nhiều lần về thời gian chạy, và vì sao một thao tác O(n) chạy trên vùng nhớ liền mạch có thể thắng một thao tác “O(1)” phải nhảy khắp heap.

2. Memory Layout: hai cấu trúc nằm trong heap như thế nào

2.1. ArrayList: một mảng tham chiếu liền mạch

Bên trong, ArrayList chỉ là một mảng Object[] elementData cộng với biến size. Một số điểm đáng chú ý trong mã nguồn OpenJDK:

Tạo bằng new ArrayList<>() chưa cấp phát mảng ngay; mảng 10 phần tử chỉ được tạo ở lần add đầu tiên.
Khi đầy, mảng tăng khoảng 1.5 lần (newCapacity = oldCapacity + (oldCapacity >> 1)) và được sao chép bằng Arrays.copyOf.
Các tham chiếu nằm sát nhau trong một khối nhớ, nên duyệt tuần tự là truy cập tuần tự đúng nghĩa.

2.2. LinkedList: mỗi phần tử là một object riêng

LinkedList là danh sách liên kết đôi. Mỗi phần tử được bọc trong một object Node:

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
}

Thêm n phần tử nghĩa là cấp phát n object Node. Các Node có thể nằm ở bất kỳ đâu trong heap, đặc biệt sau khi GC di chuyển object hoặc khi danh sách được xây dựng xen kẽ với các cấp phát khác.

2.3. Tính chi phí bộ nhớ cụ thể

Trên JVM 64-bit với compressed oops (mặc định khi heap nhỏ hơn khoảng 32 GB): object header 12 byte, mỗi tham chiếu 4 byte, object được làm tròn lên bội số của 8 byte.

Một Node của LinkedList: 12 (header) + 3 × 4 (item, next, prev) = 24 byte.
Một ô trong mảng của ArrayList: 4 byte. Mảng có thêm header 16 byte và phần dung lượng dư (tối đa khoảng 50% sau mỗi lần grow).
Object rỗng: ArrayList 24 byte, LinkedList 32 byte.

Với 1 triệu phần tử, chỉ tính phần “khung” của collection (chưa tính bản thân các phần tử):

Collection	Chi phí khung	Số object cấp phát thêm
ArrayList	khoảng 4 MB (tối đa ~6 MB nếu còn dư capacity)	1 mảng
LinkedList	khoảng 24 MB	1.000.000 Node

LinkedList tốn bộ nhớ gấp khoảng 6 lần và tạo ra một triệu object mà GC phải theo dõi. Bạn có thể tự kiểm chứng bằng thư viện JOL (Java Object Layout):

// Maven: org.openjdk.jol:jol-core
List<Integer> array = new ArrayList<>();
List<Integer> linked = new LinkedList<>();
for (int i = 0; i < 1_000; i++) { array.add(i); linked.add(i); }
System.out.println(GraphLayout.parseInstance(array).toFootprint());
System.out.println(GraphLayout.parseInstance(linked).toFootprint());

Lưu ý: cả hai đều chứa các object Integer riêng (16 byte mỗi object, trừ các giá trị -128..127 được cache). Kết quả của JOL sẽ cộng cả phần này, nên hãy nhìn vào dòng java.util.LinkedList$Node và [Ljava.lang.Object; để so sánh phần khung.

2.4. Một ngoại lệ thú vị: danh sách rất nhỏ

Năm 2021, khi có đề xuất thay các LinkedList trong mã nguồn JDK bằng ArrayList (JDK-8263561), các reviewer của OpenJDK đã chỉ ra rằng với danh sách chỉ có 1 phần tử, ArrayList mặc định tốn khoảng 80 byte (vì mảng được cấp phát sẵn 10 ô) trong khi LinkedList chỉ khoảng 56 byte. Giải pháp được chọn không phải là giữ LinkedList, mà là tạo ArrayList với initial capacity phù hợp: new ArrayList<>(1) chỉ còn khoảng 48 byte. Bài học: nếu bạn tạo hàng triệu list nhỏ, hãy chỉ định capacity.

3. Cache Locality và Pointer Chasing

Ảnh 2: Một cache line 64 byte chứa 16 phần tử ArrayList, còn với LinkedList thường chỉ phục vụ được một Node

3.1. ArrayList: một lần nạp, dùng được 16 phần tử

Với tham chiếu 4 byte, một cache line 64 byte chứa 16 phần tử liên tiếp của mảng. Khi duyệt ArrayList, cứ 16 phần tử mới phát sinh một lần nạp cache line, và prefetcher thường đã nạp sẵn line đó trước khi CPU cần. JIT compiler của HotSpot còn có thể loại bỏ kiểm tra biên và tối ưu vòng lặp trên mảng rất mạnh.

3.2. LinkedList: pointer chasing

Với LinkedList, để biết địa chỉ Node thứ i+1, CPU phải đọc xong trường next của Node thứ i. Các lần đọc này phụ thuộc lẫn nhau (dependent loads), nên CPU không thể thực thi song song hay đoán trước. Prefetcher cũng không giúp được nhiều vì địa chỉ không theo một bước nhảy cố định. Hiện tượng này gọi là pointer chasing.

Hệ quả: nếu các Node không nằm trong cache, mỗi bước duyệt có thể tốn trọn một lần truy cập RAM. Dữ liệu cần dùng thực sự (tham chiếu item 4 byte) chỉ chiếm một phần nhỏ của mỗi Node 24 byte, nên mỗi cache line nạp về cũng chứa ít dữ liệu hữu ích hơn.

3.3. Thí nghiệm kinh điển của Bjarne Stroustrup

Trong keynote GoingNative 2012, Bjarne Stroustrup (tác giả C++) đưa ra bài toán: chèn N số ngẫu nhiên vào một dãy sao cho dãy luôn được sắp xếp, sau đó xóa lần lượt từng phần tử ở vị trí ngẫu nhiên. Về lý thuyết, bài toán này có lợi cho danh sách liên kết vì chèn/xóa là O(1). Thực tế, std::vector thắng std::list áp đảo ở mọi kích thước được thử. Lý do: cả hai đều phải tìm vị trí bằng duyệt tuyến tính O(n), và phần duyệt trên vùng nhớ liền mạch nhanh hơn nhiều so với phần dịch mảng mà vector phải trả thêm.

Java còn bất lợi hơn C++ ở điểm này: std::list có thể lưu giá trị ngay trong node, còn LinkedList của Java lưu tham chiếu, nên mỗi phần tử có thể cần thêm một bước nhảy nữa tới object thật.

3.4. Một sắc thái cần biết

Không phải lúc nào LinkedList cũng rời rạc. Nếu bạn xây dựng danh sách liên tục trong một vòng lặp, JVM cấp phát object theo kiểu “bump pointer” trong TLAB (Thread-Local Allocation Buffer), nên các Node và các Integer thường nằm sát nhau. Một số phép đo bằng hardware counter thậm chí ghi nhận LinkedList ít L2 miss hơn trong những trường hợp như vậy. Tuy nhiên, trạng thái “đẹp” này không bền: GC di chuyển object, danh sách bị chèn/xóa xen kẽ với các cấp phát khác, và theo thời gian các Node bị phân tán. Ngoài ra, với ArrayList chứa object (không phải kiểu nguyên thủy), bản thân các object phần tử cũng có thể nằm rải rác; mảng chỉ đảm bảo phần tham chiếu là liền mạch.

4. Complexity thực tế của từng thao tác

Thao tác	ArrayList	LinkedList	Thực tế
get(i) / set(i)	O(1)	O(n), duyệt từ đầu gần hơn (tối đa n/2 bước)	ArrayList nhanh hơn rất nhiều
add(e) vào cuối	O(1) khấu hao (thỉnh thoảng grow)	O(1), nhưng mỗi lần cấp phát một Node	ArrayList thường nhanh hơn hoặc ngang
add(i, e) / remove(i) ở giữa	O(n) dịch mảng bằng System.arraycopy	O(n) để tìm vị trí + O(1) để nối	ArrayList thường thắng, trừ list rất nhỏ
Thêm/xóa ở đầu	O(n)	O(1)	LinkedList thắng, nhưng ArrayDeque còn tốt hơn
Duyệt toàn bộ	O(n), liền mạch	O(n), pointer chasing	ArrayList nhanh hơn nhiều lần
Xóa qua Iterator.remove()	O(n) mỗi lần	O(1) mỗi lần	Dùng removeIf cho ArrayList: O(n) cho cả lượt
Bộ nhớ mỗi phần tử	~4 byte (+ dư capacity)	~24 byte	LinkedList gấp ~6 lần

4.1. Cái bẫy “chèn giữa là O(1)”

LinkedList chỉ chèn O(1) khi bạn đã đứng sẵn ở vị trí cần chèn, tức là đang giữ một ListIterator. Lời gọi list.add(i, e) vẫn phải duyệt tới vị trí i trước, nên tổng chi phí vẫn là O(n), và phần duyệt này lại là phần chậm nhất vì pointer chasing.

Trong khi đó, ArrayList dịch mảng bằng System.arraycopy, một intrinsic được JVM biên dịch thành lệnh sao chép khối bộ nhớ tối ưu (tương tự memmove). Sao chép vài nghìn tham chiếu liền mạch chỉ tốn rất ít thời gian.

4.2. Xóa nhiều phần tử: dùng removeIf

// Chậm với ArrayList: mỗi lần remove dịch phần còn lại, tổng O(n^2)
Iterator<Order> it = orders.iterator();
while (it.hasNext()) {
    if (it.next().isCancelled()) it.remove();
}
// Nhanh: ArrayList.removeIf đánh dấu rồi nén mảng một lần, tổng O(n)
orders.removeIf(Order::isCancelled);

4.3. Tự đo bằng JMH

Đừng đo hiệu năng Java bằng System.nanoTime() trong hàm main: JIT warm-up, dead code elimination và GC sẽ làm kết quả sai lệch. Hãy dùng JMH:

@State(Scope.Benchmark)
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MICROSECONDS)
@Warmup(iterations = 5) @Measurement(iterations = 5) @Fork(2)
public class ListBenchmark {
    @Param({"100", "10000", "1000000"})
    int size;
    List<Integer> arrayList;
    List<Integer> linkedList;
    @Setup
    public void setup() {
        arrayList = new ArrayList<>();
        linkedList = new LinkedList<>();
        for (int i = 0; i < size; i++) {
            arrayList.add(i);
            linkedList.add(i);
        }
    }
    @Benchmark
    public long iterateArrayList() {
        long sum = 0;
        for (int x : arrayList) sum += x;
        return sum;
    }
    @Benchmark
    public long iterateLinkedList() {
        long sum = 0;
        for (int x : linkedList) sum += x;
        return sum;
    }
    @Benchmark
    public void insertMiddleArrayList(Blackhole bh) {
        arrayList.add(size / 2, 42);
        bh.consume(arrayList.remove(size / 2));
    }
    @Benchmark
    public void insertMiddleLinkedList(Blackhole bh) {
        linkedList.add(size / 2, 42);
        bh.consume(linkedList.remove(size / 2));
    }
}

Để thấy rõ tác động của sự phân tán, bạn có thể thêm một biến thể trong đó LinkedList được xây dựng xen kẽ với các cấp phát rác, hoặc được trộn bằng nhiều lần chèn/xóa ngẫu nhiên trước khi đo.

5. Chi phí ẩn: Garbage Collection

Mỗi Node là một object mà GC phải đánh dấu, quét và có thể di chuyển. Một LinkedList một triệu phần tử nghĩa là thêm một triệu object sống trong heap. Khi danh sách sống lâu và được promote lên old generation, GC phải lần theo chuỗi con trỏ dài (cũng là pointer chasing) trong giai đoạn marking. Với ArrayList, toàn bộ phần khung chỉ là một mảng duy nhất. Trong các hệ thống cần độ trễ thấp, khác biệt này ảnh hưởng trực tiếp đến thời gian pause và lượng CPU dành cho GC.

6. Vậy khi nào nên dùng gì? (Java 21+)

Ảnh 3: Sơ đồ chọn collection phù hợp trong Java 21+

6.1. ArrayList là lựa chọn mặc định

Với hầu hết nhu cầu “một danh sách các phần tử”, hãy dùng ArrayList. Nếu biết trước kích thước, truyền initial capacity để tránh grow: new ArrayList<>(expectedSize). Với danh sách không đổi, dùng List.of(…) hoặc stream.toList().

6.2. Cần queue, stack hoặc deque: dùng ArrayDeque

Lý do phổ biến nhất để dùng LinkedList là vì nó implement Deque. Javadoc của chính JDK nói ArrayDeque “likely to be faster than LinkedList when used as a queue”. ArrayDeque dùng mảng vòng (circular array): thêm/xóa ở cả hai đầu đều O(1) mà vẫn giữ được cache locality. Lưu ý duy nhất: ArrayDeque không chấp nhận phần tử null.

Deque<Task> stack = new ArrayDeque<>();   // thay cho Stack và LinkedList
Queue<Task> queue = new ArrayDeque<>();   // thay cho LinkedList làm queue

6.3. Java 21 Sequenced Collections

Từ Java 21 (JEP 431), interface SequencedCollection bổ sung getFirst(), getLast(), addFirst(), addLast(), removeFirst(), removeLast() và reversed() cho cả ArrayList. Bạn không cần chuyển sang LinkedList chỉ để có API getLast() gọn gàng nữa. Cần nhớ: trên ArrayList, getFirst/getLast/addLast/removeLast là O(1), nhưng addFirst/removeFirst vẫn là O(n) vì phải dịch mảng. Nếu thao tác ở đầu là việc thường xuyên, đó là tín hiệu để dùng ArrayDeque.

6.4. LinkedList còn chỗ đứng không?

Rất hẹp. Có thể cân nhắc khi bạn thường xuyên chèn/xóa ở giữa một danh sách lớn thông qua một ListIterator đang giữ sẵn vị trí, và đã đo bằng benchmark thấy LinkedList thực sự nhanh hơn trên dữ liệu của mình. Joshua Bloch, người thiết kế Java Collections Framework, được cho là từng viết: “Does anyone actually use LinkedList? I wrote it, and I never use it.”

Kết bài

Big-O cho biết thuật toán mở rộng ra sao, nhưng không cho biết mỗi bước tốn bao nhiêu. Trên phần cứng hiện đại, chi phí đó do cách dữ liệu nằm trong bộ nhớ quyết định. Những điểm cần nhớ:

Memory layout: ArrayList lưu tham chiếu trong một mảng liền mạch (~4 byte/phần tử); LinkedList cấp phát một Node 24 byte cho mỗi phần tử, tốn bộ nhớ gấp khoảng 6 lần và tạo áp lực lên GC.
Cache locality: ArrayList tận dụng cache line và prefetcher; LinkedList bị pointer chasing, mỗi bước có thể là một lần truy cập RAM.
Complexity thực tế: “chèn giữa O(1)” của LinkedList chỉ đúng khi đã đứng sẵn ở vị trí đó; trong đa số trường hợp, ArrayList với System.arraycopy vẫn nhanh hơn.
Lựa chọn: ArrayList là mặc định, ArrayDeque cho queue/stack/deque, chỉ định initial capacity cho list nhỏ, và luôn đo bằng JMH trước khi kết luận.