Cấu trúc dữ liệu và Giải thuật Bài 32: Danh sách liên kết đôi (Doubly Linked List) và nền tảng của LRU Cache.

Danh sách liên kết đơn (Singly Linked List) có một điểm mù vật lý chí mạng: Bạn chỉ có thể di chuyển tiến về phía trước. Nếu bạn vừa đi qua một Node và nhận ra đó là dữ liệu mình cần tìm, cách duy nhất để quay lại là xuất phát lại từ con trỏ Head. Sự bất tiện này được giải quyết triệt để bằng Danh sách liên kết đôi (Doubly Linked List) thông qua việc bổ sung thêm một sợi dây liên kết ngược.

1. Cấu trúc Node hai chiều

Trong Doubly Linked List, mỗi Node phải mang theo 3 khối thông tin độc lập:

1. Data: Dữ liệu thực tế.

2. Next Pointer: Trỏ tới địa chỉ của Node tiếp theo.

3. Prev (Previous) Pointer: Trỏ ngược về địa chỉ của Node đứng ngay trước nó.

Việc cõng thêm con trỏ Prev đồng nghĩa với việc mỗi Node tiêu tốn thêm 8 Bytes bộ nhớ (trên kiến trúc 64-bit). Tuy nhiên, sự hi sinh không gian này mang lại quyền năng tuyệt đối về tốc độ định vị.

2. Quyền năng O(1) khi chèn và xóa

Ở bài 29, để xóa một Node trong Singly Linked List, bạn mất O(n) thời gian vì phải duyệt từ đầu danh sách để tìm ra Node đứng trước nó (nhằm nối dây vòng qua Node cần xóa).

Với Doubly Linked List, nếu bạn đã nắm trong tay con trỏ của Node cần xóa, thao tác diễn ra trong đúng O(1) vật lý. Bản thân Node đó đã lưu trữ sẵn địa chỉ của người tiền nhiệm qua con trỏ Prev. Bạn chỉ cần thực hiện "phẫu thuật" 4 chiều:

• Trỏ Next của Node phía trước vào Node phía sau.

• Trỏ Prev của Node phía sau ngược lại Node phía trước.

3. Kiến trúc lõi của LRU Cache

Ứng dụng vĩ đại nhất của Doubly Linked List trong kỹ thuật backend chính là nền tảng xây dựng bộ nhớ đệm LRU (Least Recently Used) Cache – cơ chế dọn rác kinh điển được sử dụng trong Redis, Memcached và CPU Cache.

LRU Cache giải quyết bài toán: Khi bộ nhớ đệm đã đầy, phần tử nào ít được truy cập nhất trong thời gian gần đây sẽ bị xóa đi để nhường chỗ cho dữ liệu mới. Kiến trúc này là sự kết hợp hoàn hảo giữa 2 cấu trúc:

• Hash Map (Bảng băm): Lưu trữ các Key trỏ thẳng vào các địa chỉ Node trong Linked List, cho phép tra cứu dữ liệu siêu tốc độ O(1).

• Doubly Linked List: Đảm nhận việc sắp xếp thứ tự ưu tiên. Mỗi khi một dữ liệu được truy cập (đọc hoặc ghi), Node đó bị cắt khỏi vị trí hiện tại và bốc lên đầu danh sách (Head - Vị trí ưu tiên nhất). Phần tử bị đẩy dồn về cuối danh sách (Tail) chính là phần tử "Least Recently Used" và sẽ bị chém bỏ đầu tiên khi dung lượng đầy.

4. Hiện thực hóa bằng Golang

Dưới đây là phác đồ thiết kế kiến trúc chuẩn của một LRU Cache kết hợp Hash Map và các Dummy Nodes (Node mồi ở hai đầu) để loại bỏ hoàn toàn các lỗi dính đến con trỏ nil.

Go

type Node struct {
    Key, Value int
    Prev, Next *Node
}

type LRUCache struct {
    capacity int
    cache    map[int]*Node
    head     *Node // Dummy Head
    tail     *Node // Dummy Tail
}

func Constructor(capacity int) LRUCache {
    lru := LRUCache{
        capacity: capacity,
        cache:    make(map[int]*Node),
        head:     &Node{},
        tail:     &Node{},
    }
    // Khởi tạo liên kết ban đầu giữa 2 Node mồi
    lru.head.Next = lru.tail
    lru.tail.Prev = lru.head
    return lru
}

// Hàm đẩy một Node vừa được truy cập lên đầu danh sách (ngay sau Dummy Head)
func (this *LRUCache) moveToHead(node *Node) {
    // 1. Cắt đứt liên kết tại vị trí cũ
    node.Prev.Next = node.Next
    node.Next.Prev = node.Prev
    
    // 2. Chèn Node vào ngay sau Head
    node.Next = this.head.Next
    node.Prev = this.head
    this.head.Next.Prev = node
    this.head.Next = node
}

Sự linh hoạt trong việc thao tác con trỏ 2 chiều không chỉ dừng lại ở bài toán bộ nhớ đệm. Bằng cách thiết lập các quy tắc khắt khe về vị trí thêm và xóa Node (chỉ được thao tác ở 1 đầu, hoặc 2 đầu), chúng ta sẽ tạo ra được những cỗ máy xử lý luồng công việc tự động.