Linked list — Vì sao production Java gần như không dùng LinkedList

Tutorial DSA kinh điển dạy: LinkedList.add() là O(1), ArrayList.add() là amortized O(1) — nghe có vẻ tương đương. Vậy khi nào dùng cái nào? Hầu hết học viên kết luận: tùy.

Nhưng grep qua production Java codebase thực tế: hầu như không có new LinkedList nào. Effective Java (Bloch) Item 28 cũng khuyên không dùng. Nếu O(1) tương đương, tại sao không ai chọn LinkedList?

Bài này giải thích cơ chế bên trong linked list, vì sao Big-O không nói hết câu chuyện, và những trường hợp hiếm hoi linked list thực sự là lựa chọn đúng.

1. Định nghĩa và cấu trúc

1.1 Singly linked list

Mỗi node chứa hai thứ: dữ liệu (data) và con trỏ (next) trỏ đến node kế tiếp. Node cuối cùng có next = null.

[A | next]-->[B | next]-->[C | next]-->[D | null]
  head                                    tail

Để duyệt list, bắt đầu từ head và theo next cho đến khi gặp null. Không có cách nào đi ngược lại.

1.2 Doubly linked list

Thêm con trỏ prev để traverse 2 chiều. Node đầu có prev = null, node cuối có next = null.

null<--[A | prev | next]<-->[B | prev | next]<-->[C | prev | next]-->null
         head                                        tail

Lợi thế quan trọng: nếu bạn đang giữ reference đến một node cụ thể, xóa node đó chỉ tốn O(1) — update prev.next và next.prev mà không cần traverse từ đầu.

1.3 Java implementation cơ bản

// Singly linked list node
class Node<T> {
    T data;
    Node<T> next;

    Node(T data) {
        this.data = data;
        this.next = null;
    }
}

// Simple singly linked list with head and tail cache
class MyLinkedList<T> {
    private Node<T> head;
    private Node<T> tail;
    private int size;

    public MyLinkedList() {
        head = null;
        tail = null;
        size = 0;
    }

    public int size() { return size; }
}

Cache tail là kỹ thuật quan trọng: nếu không có tail, mỗi lần addLast() phải traverse toàn bộ list — O(n) thay vì O(1).

2. Operations và complexity

Chú ý dòng "delete tail" của singly: dù có tail cache, để xóa node đó vẫn cần tìm node ngay trước nó (prev) — không có con trỏ prev thì phải traverse từ head. Doubly giải quyết hoàn toàn vì tail.prev cho biết node trước đó ngay lập tức.

3. Implement các operation cốt lõi

3.1 addFirst và addLast

// Add at head -- O(1)
public void addFirst(T data) {
    Node<T> newNode = new Node<>(data);
    if (head == null) {
        // Empty list: head and tail point to same node
        head = newNode;
        tail = newNode;
    } else {
        newNode.next = head;
        head = newNode;
    }
    size++;
}

// Add at tail -- O(1) because we cache tail
public void addLast(T data) {
    Node<T> newNode = new Node<>(data);
    if (tail == null) {
        // Empty list
        head = newNode;
        tail = newNode;
    } else {
        tail.next = newNode;
        tail = newNode;
    }
    size++;
}

3.2 removeAt — và tại sao singly list phức tạp hơn

// Remove node AFTER a given node -- O(1) for singly
// (We need the predecessor, not the node itself)
public void removeAfter(Node<T> pred) {
    if (pred == null || pred.next == null) return;
    Node<T> toRemove = pred.next;
    pred.next = toRemove.next;
    if (toRemove == tail) {
        // Removed the tail, update tail pointer
        tail = pred;
    }
    size--;
}

// Remove by value -- O(n) because we must find predecessor first
public boolean remove(T target) {
    if (head == null) return false;
    if (head.data.equals(target)) {
        head = head.next;
        if (head == null) tail = null;
        size--;
        return true;
    }
    Node<T> prev = head;
    while (prev.next != null) {
        if (prev.next.data.equals(target)) {
            if (prev.next == tail) tail = prev;
            prev.next = prev.next.next;
            size--;
            return true;
        }
        prev = prev.next;
    }
    return false;
}

Đây là điểm quan trọng: singly linked list không thể xóa một node tùy ý trong O(1) chỉ với pointer đến node đó — cần biết node trước (prev) để cập nhật prev.next. Nếu không có prev, phải traverse từ head để tìm. Doubly linked list giải quyết bằng node.prev.

3.3 Diagram delete node

Truoc: [A] --> [B] --> [C] --> [D] --> null
               ^
               pred

Xoa [C] (node sau pred):
   pred.next = C.next = D

Sau:  [A] --> [B] --> [D] --> null
                        ^
                       tail (neu C la tail, cap nhat lai)

4. Cache penalty — Big-O không cover

Đây là lý do chính LinkedList ít xuất hiện trong production. Bài 04 Module 1 đã đo con số: sum 10 triệu int qua int[] mất khoảng 8ms, qua LinkedList<Integer> mất khoảng 200ms — chênh lệch 25 lần dù cả hai đều O(n).

Tại sao? Mỗi node trong java.util.LinkedList là một object riêng biệt được cấp phát trên heap tại thời điểm add(). Theo thời gian, các node này nằm rải rác ở các địa chỉ không liên tiếp:

int[] sequential layout:
[1][2][3][4][5][6][7][8]...[16]  <-- 1 cache line (64 bytes) = 16 int
  ^-- prefetcher load ca khoi, 16 phan tu voi 1 cache miss

LinkedList<Integer> scattered layout:
Node@0x1A00 --> Node@0x8F40 --> Node@0x3B80 --> Node@0xC120
   |MISS|           |MISS|           |MISS|           |MISS|
   100ns            100ns            100ns            100ns

Mỗi bước traverse là một pointer chase — CPU phải fetch node tiếp theo từ địa chỉ ngẫu nhiên, không thể dự đoán trước. Hardware prefetcher vô hiệu. Mỗi node là 1 cache miss riêng thay vì chia đều 1 cache miss cho 16 phần tử như int[].

Thêm vào đó, java.util.LinkedList.Node chiếm khoảng 32 byte (object header 12 byte + item ref 4 byte + prev ref 4 byte + next ref 4 byte + padding 8 byte), cộng với Integer boxed object 16 byte — tổng 48 byte mỗi phần tử. So với 4 byte của int[]: gấp 12 lần RAM. 10 triệu phần tử: int[] khoảng 40 MB, LinkedList<Integer> khoảng 480 MB.

5. Pitfall tổng hợp

Pitfall 1 — linkedList.add(index, value) không phải O(1):

LinkedList<Integer> list = new LinkedList<>();
// ... add 100_000 elements ...

// WRONG assumption: "linked list insert is O(1)"
for (int i = 0; i < 1000; i++) {
    list.add(50_000, i); // O(n) traverse to index + O(1) pointer update = O(n) total
}
// Loop O(1000) x O(n) = O(n^2) -- voi n = 100_000, day la 10^10 operations

// CORRECT approach if you need sequential insert: use iterator
ListIterator<Integer> it = list.listIterator(50_000);
for (int i = 0; i < 1000; i++) {
    it.add(i); // O(1) pointer update, vi iterator da o vi tri do
}

LinkedList.add(int index, E element) gọi method node(index) bên trong — traverse từ head hoặc tail đến vị trí đó, tốn O(n/2). Chỉ thao tác pointer update sau đó mới là O(1). Dùng trong vòng lặp n lần là O(n²) — nguy hiểm với list lớn.

Pitfall 2 — list.get(i) trên LinkedList trông đẹp nhưng tốn kém:

java.util.LinkedList implements cả List và Deque. Vì implement List, nó có method get(int index) — và beginner hay nhầm đây là O(1) như ArrayList.

List<String> list = new LinkedList<>();
// ... add 100_000 elements ...

// WRONG: O(n) per get() -- tong O(n^2)
for (int i = 0; i < list.size(); i++) {
    process(list.get(i)); // LinkedList.get(i) traverse toi i -- O(n) moi lan
}

// CORRECT: use enhanced for-loop (uses iterator internally -- O(1) per step)
for (String item : list) {
    process(item);
}

Nếu cần random access theo index thường xuyên, LinkedList là lựa chọn sai. ArrayList.get(i) là O(1) vì index trực tiếp vào backing array; LinkedList.get(i) traverse từ đầu — O(n).

Pitfall 3 — "LinkedList không resize nên memory ổn định hơn":

Lý luận nghe có vẻ đúng: ArrayList đôi khi tăng gấp 1.5 lần backing array, có thể có capacity slack. LinkedList alloc từng node — không bao giờ "dư". Nhưng thực tế ngược lại:

ArrayList<Integer> với 1 triệu phần tử: khoảng 20 MB (Integer objects) + tối đa 17% slack = khoảng 23 MB. LinkedList<Integer> với 1 triệu phần tử: 1 triệu Node object (32 byte) + 1 triệu Integer object (16 byte) = khoảng 48 MB.

Mỗi node alloc riêng còn tạo GC pressure cao hơn — nhiều object nhỏ rải rác trên heap, GC phải track và collect từng node riêng lẻ thay vì 1 backing array duy nhất.

6. Khi nào LinkedList thực sự thắng

Ba trường hợp trong thực tế linked list là lựa chọn đúng — không phải java.util.LinkedList cho mọi thứ, mà là cấu trúc dựa trên linked list khi pattern phù hợp:

Trường hợp 1 — Build LRU cache:

LRU (Least Recently Used) cache cần hai thứ: lookup O(1) và insert/delete O(1) ở 2 đầu. Kết hợp HashMap (lookup nhanh) với doubly linked list (reorder nhanh): khi một key được truy cập, xóa node tương ứng khỏi vị trí hiện tại và chuyển lên đầu — cả hai thao tác là O(1) vì HashMap cho trực tiếp reference đến node.

ArrayList không thể làm điều này — remove(index) là O(n) vì phải shift. Module 2 bài 07 sẽ implement LRU cache đầy đủ.

Trường hợp 2 — Nối hai list không cần copy:

Với singly linked list tự quản lý, nối hai list chỉ cần: tail1.next = head2. Tốn O(1). ArrayList phải copy toàn bộ list 2 vào backing array của list 1 — O(n). Kỹ thuật này xuất hiện trong các algorithm merge/split thao tác trực tiếp trên node.

Trường hợp 3 — External chained-storage trong hệ thống lớn:

LSM tree (dùng trong LevelDB, Cassandra, RocksDB) dùng linked list để chain các SSTable. B+tree dùng linked list nối các leaf node để range scan hiệu quả. Skip list (Module 3) dùng nhiều tầng linked list với O(log n) expected search — Redis ZSET implement bằng skip list. Đây là các cấu trúc tự thiết kế, không phải java.util.LinkedList.

7. Java LinkedList source — Bên trong thực sự trông như thế nào

java.util.LinkedList trong OpenJDK implement doubly linked list với Node private static inner class:

// Trich tu OpenJDK 21 -- java.util.LinkedList
private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

Ba điểm đáng chú ý trong implementation:

Thứ nhất, prev và next được khai báo transient trong LinkedList class-level fields — Java serialization bỏ qua chúng. LinkedList có writeObject() và readObject() custom để serialize giá trị từng node theo thứ tự, sau đó rebuild linked structure khi deserialize.

Thứ hai, LinkedList.iterator() trả về ListItr private inner class, track lastReturned (node vừa return), next (node kế tiếp), và nextIndex. ListIterator.add() và remove() update cả linked pointers lẫn size và modCount atomically — đây là lý do ListIterator.add() an toàn trong khi iterate, còn list.add() trực tiếp thì không.

Thứ ba, node(int index) — method nội bộ để tìm node theo index — tối ưu nhỏ: nếu index < size/2 traverse từ head, ngược lại traverse từ tail. Vẫn O(n) worst case nhưng trung bình O(n/2).

8. Applied to tech

Effective Java Item 28 (Bloch): "Prefer lists to arrays" — và trong context sequences with random access, prefer ArrayList over LinkedList. Bloch chỉ ra LinkedList có lợi thế lý thuyết nhưng trong thực tế cache penalty thường vượt lợi thế complexity.

Linux kernel list.h: Kernel Linux dùng doubly linked list rất nhiều — task scheduler, device driver list, filesystem. Nhưng đây là C, không phải Java: các struct kernel được alloc trong contiguous pool (slab allocator), neighbor nodes thường gần nhau về địa chỉ. C struct không có object header overhead. Pointer chasing vẫn tốn kém nhưng ít nghiêm trọng hơn Java heap fragmentation.

Skip list (sẽ gặp Module 3): Variant linked list với nhiều tầng "express link" — có thể skip qua nhiều node mỗi bước. Expected O(log n) search thay vì O(n). Redis ZSET (sorted set) implement bằng skip list vì insert/delete O(log n) và range scan liên tiếp hiệu quả hơn balanced BST.

ConcurrentLinkedQueue: Lock-free queue implement Michael-Scott algorithm — dùng AtomicReference để CAS trên head/tail thay vì lock. Linked structure cho phép multiple producers/consumers không cần global lock. Phân tích chi tiết trong extension Module 2 về concurrent data structures.

9. Deep Dive tài liệu gốc

10. Tóm tắt

• Linked list lưu trữ bằng node rải rác trên heap: mỗi node chứa data + pointer(s). Không có backing array liên tiếp.
• Singly linked list không thể xóa node tùy ý trong O(1) nếu chỉ có pointer đến node đó — cần prev để update. Doubly linked list giải quyết vì có prev field.
• LinkedList.add(index, value) là O(n), không O(1) — phải traverse đến index trước. Dùng trong vòng lặp là O(n²).
• list.get(i) trên LinkedList là O(n) — traverse từ đầu mỗi lần. Vòng for index là O(n²). Dùng iterator hoặc enhanced for-loop thay thế.
• Cache penalty thường vượt lợi thế O(1) insert: pointer chasing = 1 cache miss mỗi node × 100ns = 25x chậm hơn int[] sequential access dù cùng O(n).
• Bộ nhớ gấp 12 lần int[] cho LinkedList<Integer>: 48 byte/phần tử (Node + Integer) so với 4 byte.
• LinkedList thực sự thắng khi kết hợp HashMap cho LRU cache (cần insert/delete O(1) với ref node sẵn), hoặc nối list O(1), hoặc cấu trúc tự thiết kế (skip list, B+tree leaf chain).
• Production code prefer ArrayList cho list dùng chung, ArrayDeque cho queue/stack, LinkedList chỉ cho pattern đặc thù đã đo benchmark.

11. Tự kiểm tra

LinkedList<Integer> list = new LinkedList<>();
// ... fill with 1_000_000 elements ...
long sum = 0;
for (int i = 0; i < list.size(); i++) {
  sum += list.get(i); // is this O(1)?
}

long sum = 0;
for (int x : list) { // uses ListIterator.next() -- O(1) per step
  sum += x;
}
// Total: O(n) -- correct

Bài tiếp theo: Stack — LIFO, call stack, undo