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

TL;DR: Linked list lưu trữ bằng các node rời rạc trên heap, mỗi node chứa dữ liệu và con trỏ đến node kế tiếp. Insert/delete tại đầu là O(1) — không cần shift như array. Nhưng Big-O che giấu constant factor quan trọng: mỗi bước traverse là một cache miss riêng, khiến sum 10 triệu phần tử qua linked list chậm hơn array 25 lần dù cùng O(n). Thêm vào đó, mỗi node chiếm 24 byte overhead; cộng Integer boxed thành 40 byte/phần tử — gấp 10 lần array nguyên thuỷ. Production Java hầu như không dùng LinkedList vì ArrayList và ArrayDeque thắng nhờ cache locality trong hầu hết trường hợp.

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 và con trỏ next trỏ đến node kế tiếp. Node cuối cùng có next = null.

graph LR
    HEAD(["head"])
    A["A | next →"]
    B["B | next →"]
    C["C | next →"]
    D["D | null"]

    HEAD --> A
    A --> B
    B --> C
    C --> D

Để 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.

graph LR
    HEAD(["head"])
    TAIL(["tail"])
    A["prev=null | A | next"]
    B["prev | B | next"]
    C["prev | C | next=null"]

    HEAD --> A
    A -->|"next"| B
    B -->|"next"| C
    B -->|"prev"| A
    C -->|"prev"| B
    C --> 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) — cập nhật prev.next và next.prev mà không cần traverse từ đầu.

1.3 Pseudocode cấu trúc node

-- Singly linked list node
Node:
    data   -- dữ liệu
    next   -- con trỏ đến node kế tiếp (null nếu là tail)

-- Doubly linked list node
Node:
    data   -- dữ liệu
    next   -- con trỏ đến node kế tiếp
    prev   -- con trỏ đến node trước đó

-- Simple linked list với head và tail cache
LinkedList:
    head   -- node đầu tiên (null nếu rỗng)
    tail   -- node cuối cùng (null nếu rỗng)
    size   -- số phần tử

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. Pseudocode các operation cốt lõi

3.1 addFirst và addLast

-- addFirst: thêm node mới lên đầu -- O(1)
addFirst(list, data):
    newNode <- Node(data, next=list.head)
    if list.head = null:
        list.head <- newNode      -- danh sách rỗng: head và tail cùng trỏ node mới
        list.tail <- newNode
    else:
        newNode.next <- list.head
        list.head <- newNode
    list.size <- list.size + 1

Time: O(1) Space: O(1)

-- addLast: thêm node mới vào cuối -- O(1) vì cache tail
addLast(list, data):
    newNode <- Node(data, next=null)
    if list.tail = null:
        list.head <- newNode      -- danh sách rỗng
        list.tail <- newNode
    else:
        list.tail.next <- newNode
        list.tail <- newNode
    list.size <- list.size + 1

Time: O(1) Space: O(1)

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

-- Xoá node SAU một node cho trước -- O(1) với singly linked list
-- (cần node predecessor, không phải node cần xoá)
removeAfter(list, pred):
    if pred = null or pred.next = null: return
    toRemove <- pred.next
    pred.next <- toRemove.next
    if toRemove = list.tail:
        list.tail <- pred         -- cập nhật tail nếu xoá node cuối
    list.size <- list.size - 1

-- Xoá theo giá trị -- O(n) vì phải tìm predecessor trước
remove(list, target):
    if list.head = null: return false
    if list.head.data = target:
        list.head <- list.head.next
        if list.head = null: list.tail <- null
        list.size <- list.size - 1
        return true
    prev <- list.head
    while prev.next != null:
        if prev.next.data = target:
            if prev.next = list.tail: list.tail <- prev
            prev.next <- prev.next.next
            list.size <- list.size - 1
            return true
        prev <- prev.next
    return false

Time: O(n) Space: O(1)

Đâ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

Trước: [A] --> [B] --> [C] --> [D] --> null
                ^
               pred

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

Sau:  [A] --> [B] --> [D] --> null
                        ^
                       tail (nếu C là tail, cập nhật lại)

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 array nguyên thuỷ mất khoảng 8ms, qua danh sách liên kết 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:

Array nguyên thuỷ — layout liên tiếp trong bộ nhớ:
[1][2][3][4][5][6][7][8]...[16]   -- 1 cache line (64 bytes) = 16 int
  ^-- prefetcher nạp cả khối, 16 phần tử với 1 cache miss

LinkedList<Integer> — layout rải rác trên heap:
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ư array nguyên thuỷ.

Thêm vào đó, java.util.LinkedList.Node chiếm khoảng 24 byte (object header 12 + item 4 + prev 4 + next 4 — đã bội số 8 nên không padding), cộng Integer boxed 16 byte — tổng 40 byte mỗi phần tử. So với 4 byte của array nguyên thuỷ: gấp 10 lần RAM. 10 triệu phần tử: array nguyên thuỷ khoảng 40 MB, danh sách liên kết khoảng 400 MB.

5. Pitfall tổng hợp

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

-- BUG assumption: "linked list insert là O(1)"
L <- LinkedList với 100.000 phần tử

for i <- 0 đến 999:
    L.add(50000, i)     -- O(n) traverse đến index + O(1) pointer update = O(n) tổng

-- Vòng lặp O(1000) x O(n) = O(n²) -- với n = 100.000 là 10^10 phép tính!

-- CORRECT: dùng ListIterator nếu cần chèn liên tiếp
it <- L.listIterator(50000)
for i <- 0 đến 999:
    it.add(i)           -- O(1) pointer update, vì iterator đã ở vị trí đó

Time bug: O(n²) Time correct: O(n + 1000)

LinkedList.add(index, value) 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 linked list trông đẹp nhưng tốn kém:

Danh sách liên kết cũng có thể gọi get(index) — và người học hay nhầm đây là O(1) như danh sách động thông thường.

-- BUG: O(n) mỗi lần get() -- tổng O(n²)
for i <- 0 đến L.size()-1:
    process(L.get(i))   -- get(i) traverse đến i -- O(n) mỗi lần

-- CORRECT: dùng enhanced for-loop (iterator nội bộ -- O(1) mỗi bước)
for each item trong L:
    process(item)

Time bug: O(n²) Time correct: O(n)

Nếu cần random access theo index thường xuyên, linked list là lựa chọn sai. Danh sách động cấp phát liên tiếp trong array, get(i) là O(1) vì index trực tiếp vào backing array; linked list phải traverse từ đầu — O(n).

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

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

Danh sách động với 1 triệu phần tử: khoảng 20 MB (Integer objects) + tối đa 17% slack = khoảng 23 MB. Danh sách liên kết với 1 triệu phần tử: 1 triệu Node object (24 byte) + 1 triệu Integer object (16 byte) = khoảng 40 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 linked list 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.

Danh sách động không thể làm điều này — remove tại index bất kỳ 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). Danh sách động 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 (Thuật toán Cốt lõi — Module 1) 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. Applied to tech

Effective Java Item 28 (Bloch): "Prefer lists to arrays" — và trong context sequences with random access, prefer danh sách động over danh sách liên kết. Bloch chỉ ra danh sách liên kết 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ỉ. 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 Thuật toán Cốt lõi — Module 1): 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 CAS (Compare-And-Swap) 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.

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

9. 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 linked list 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 array nguyên thuỷ sequential access dù cùng O(n).
• Bộ nhớ gấp 10 lần array nguyên thuỷ: 40 byte/phần tử (Node + Integer) so với 4 byte.
• Linked list 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 danh sách động cho list dùng chung, ArrayDeque cho queue/stack, danh sách liên kết chỉ cho pattern đặc thù đã đo benchmark.

10. 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