Cấu trúc dữ liệu và Giải thuật Bài 28: Danh sách liên kết (Linked List): Cấu trúc Node và Con trỏ.

Xuyên suốt 3 chương vừa qua, chúng ta đã thao tác dữ liệu dựa trên một nền tảng vật lý duy nhất: Mảng. Dù là mảng tĩnh hay mảng động, yêu cầu tiên quyết của hệ điều hành là phải tìm được một khối bộ nhớ (RAM) liên tục.

Nhưng điều gì sẽ xảy ra khi một hệ thống server chạy liên tục trong nhiều tháng, RAM liên tục bị cấp phát và giải phóng, dẫn đến hiện tượng Phân mảnh bộ nhớ (Memory Fragmentation)? Bạn có tổng cộng 1GB RAM trống, nhưng nó bị băm nát thành hàng vạn mảnh nhỏ nằm rải rác. Nếu bạn yêu cầu một mảng liên tục kích thước 100MB, hệ điều hành sẽ từ chối và báo lỗi Out Of Memory (OOM).

Đó là lúc cấu trúc dữ liệu kinh điển thứ hai xuất hiện để đập tan giới hạn vật lý này: Danh sách liên kết (Linked List).

1. Phá vỡ sự liên tục: Nguyên lý Dây chuyền

Thay vì bắt ép dữ liệu phải nằm xếp hàng cạnh nhau, Linked List cho phép dữ liệu nằm rải rác ở bất kỳ ngóc ngách nào trong bộ nhớ (vùng Heap). Để các mảnh dữ liệu rời rạc này không bị mất dấu nhau, chúng được kết nối bằng một khái niệm gọi là Con trỏ (Pointer).

Hãy tưởng tượng một trò chơi truy tìm kho báu. Bạn nhận được một mẩu giấy đầu tiên (chứa gợi ý A). Ở mặt sau của mẩu giấy ghi: "Hãy đến gốc cây đa để tìm mẩu giấy tiếp theo". Đến cây đa, bạn nhận được gợi ý B và địa chỉ của gợi ý C. Bạn không cần biết trước toàn bộ bản đồ, bạn chỉ cần nắm giữ manh mối của điểm đến ngay sau mình.

2. Giải phẫu cấu trúc Node

Trong Danh sách liên kết, mỗi "mẩu giấy" đó được gọi là một Node (Nút).

Một Node cơ bản nhất luôn chứa hai thành phần độc lập:

1. Data (Dữ liệu): Trọng tải thực sự bạn muốn lưu trữ (có thể là một số nguyên, một chuỗi, hoặc cả một object User phức tạp).

2. Next Pointer (Con trỏ Next): Một biến đặc biệt lưu trữ địa chỉ bộ nhớ của Node tiếp theo trong danh sách.

Node cuối cùng của danh sách sẽ trỏ về nil (hoặc NULL trong C/C++), đánh dấu điểm kết thúc của chuỗi dây chuyền.

3. Khởi tạo Node bằng Golang

Khác với mảng được ngôn ngữ hỗ trợ sẵn tận răng, để tạo ra một Linked List, bạn phải tự mình định nghĩa cấu trúc Node thông qua struct và thao tác trực tiếp với con trỏ.

Go

package main

import "fmt"

// Định nghĩa cấu trúc của một Node
type Node struct {
    Data int
    Next *Node // Con trỏ lưu địa chỉ của một Node khác
}

func main() {
    // 1. Cấp phát bộ nhớ rời rạc cho 3 Node
    node1 := &Node{Data: 10, Next: nil}
    node2 := &Node{Data: 20, Next: nil}
    node3 := &Node{Data: 30, Next: nil}
    
    // 2. Liên kết các Node lại với nhau
    node1.Next = node2 // node1 trỏ tới vị trí của node2
    node2.Next = node3 // node2 trỏ tới vị trí của node3
    
    // Head là điểm bắt đầu của danh sách
    head := node1
    
    // Duyệt qua danh sách bằng cách nhảy theo các con trỏ
    current := head
    for current != nil {
        fmt.Printf("%d -> ", current.Data)
        current = current.Next // Nhảy sang địa chỉ tiếp theo
    }
    fmt.Println("nil")
}

Trong đoạn mã trên, node1, node2, node3 có thể nằm ở các vùng địa chỉ hoàn toàn ngẫu nhiên như 0x10A, 0x5B2, 0x8C4. Con trỏ Next chính là chiếc cầu nối vật lý duy nhất giữ chúng lại thành một khối logic liền mạch.

4. Sự đánh đổi đắt giá: Mảng vs Linked List

Linked List giải quyết được bài toán phân mảnh bộ nhớ và kích thước linh hoạt, nhưng trong kỹ thuật phần mềm không có bữa trưa nào miễn phí.

Ưu điểm tuyệt đối:

• Thêm/Xóa phần tử siêu tốc $O(1)$: Nếu bạn đã đứng sẵn ở một vị trí trong Linked List, việc chèn thêm một Node mới chỉ đơn giản là cắt đứt 1 sợi dây liên kết cũ và nối 2 sợi dây mới. Không có bất kỳ phần tử nào phải dịch chuyển (như thảm họa $O(n)$ của mảng).

• Tận dụng tối đa bộ nhớ: Không cần khai báo trước sức chứa (Capacity). Cần bao nhiêu Node thì xin hệ điều hành cấp phát bấy nhiêu.

Hạn chế chí mạng:

• Mất đi quyền năng Random Access $O(1)$: Để tìm phần tử thứ 10,000 trong mảng, mảng chỉ dùng 1 phép toán địa chỉ. Với Linked List, bạn bắt buộc phải đi từ Head, dò hỏi qua 9,999 con trỏ mới đến được đích. Quá trình tìm kiếm luôn là $O(n)$.

• Chi phí không gian (Overhead): Mỗi phần tử giờ đây phải cõng thêm ít nhất 8 Bytes (trên hệ điều hành 64-bit) để lưu con trỏ Next. Nếu bạn chỉ lưu một số int 4 Bytes, dung lượng lưu trữ của con trỏ còn lớn hơn cả dữ liệu thực sự.

• Kẻ thù của CPU Cache (Cache Miss): Vì các Node nằm rải rác, CPU không thể bốc một cụm dữ liệu liền kề lên L1/L2 Cache như mảng (Spatial Locality). Quá trình duyệt Linked List liên tục gây ra Cache Miss, khiến tốc độ thực thi trong thực tế thường chậm hơn mảng rất nhiều khi duyệt dữ liệu.

Hiểu về cấu trúc Node là nền tảng để bạn kiến tạo nên mọi loại danh sách liên kết. Ở bài học tiếp theo, chúng ta sẽ bắt tay vào thao tác "phẫu thuật" nối và cắt các con trỏ để thực hiện việc thêm, chèn và xóa dữ liệu trong Linked List một cách an toàn.