1. Mở đầu

Bạn có bao giờ tự hỏi: “Tại sao không dùng luôn mảng (array) mà lại phải học cái gọi là linked list?” Thực ra, linked list là một cách tổ chức dữ liệu đơn giản mà rất hay ho—giúp bạn dễ thêm bớt phần tử mà không cần dịch chuyển cả mảng đi nơi khác. Bài viết này sẽ giúp bạn hiểu bằng ngôn ngữ “dân dã” nhất về cấu trúc này nhé.

2. Nội dung chính

2.1. Linked List là gì?

Khái niệm đơn giản: Mình tưởng tượng mỗi phần tử là một “người bạn” đứng thành hàng, và mỗi người đều chỉ tay (gọi là pointer) vào người tiếp theo, tạo thành một chuỗi. Người đứng đầu được gọi là head, người cuối cùng (hoặc phần còn lại của danh sách sau head) gọi là tail. (doeken.org)
Các loại phổ biến:
- Singly Linked List: mỗi node chỉ biết người tiếp theo, chỉ đi được hướng thuận. (doeken.org)
- Circular Linked List: node cuối lại chỉ về node đầu, tạo vòng tròn. (doeken.org)
- Doubly Linked List: mỗi node có thêm con trỏ về node trước, giúp đi ngược cũng được. (doeken.org, Wikipedia)
- Circular Doubly Linked List: vừa có trỏ trước sau, vừa nối vòng tròn. (doeken.org, Wikipedia)

2.2. Ví dụ minh họa

Ví dụ 1: Hàng người mua vé
- Mỗi người là một node, người này chỉ biết người kế tiếp—đó là singly linked list.
- Nếu cuối hàng quay lại đứng đầu thành vòng tròn—đó là circular linked list.
Ví dụ 2: Danh sách bạn bè có thể đi cả về trước lẫn sau
- Bạn A biết B và C; B biết cả A và C; C cũng biết B và A. Đây giống doubly linked list.

2.3. Mã minh họa đơn giản trong PHP

<?php
// 1 node chứa data và pointer đến node kế tiếp
class Node {
    public $data;
    public $next;
    public function __construct($data) {
        $this->data = $data;
        $this->next = null;
    }
}

// Quản lý danh sách liên kết
class LinkedList {
    private $head;
    public function __construct() {
        $this->head = null;
    }
    // Thêm node vào cuối danh sách
    public function append($data) {
        $newNode = new Node($data);
        if ($this->head === null) {
            $this->head = $newNode;
        } else {
            $current = $this->head;
            while ($current->next !== null) {
                $current = $current->next;
            }
            $current->next = $newNode;
        }
    }
}
?>

Giải thích cho bạn mới:

Node: là một “người bạn” có dữ liệu (data) và biết người kế tiếp (next).
append(): thêm người vào cuối hàng, cứ lần lượt đi tới hết cuối và nối thêm.

2.4. Khi nào dùng linked list thay vì array?

Ưu điểm:
- Thêm/xóa giữa danh sách dễ dàng, không phải “dời chỗ” các phần tử khác như với mảng. (Wikipedia, GeeksforGeeks)
Nhược điểm:
- Muốn truy xuất phần tử thứ n phải đi lần lượt từ đầu—a kiểu “đi bộ chậm chạp”. Mảng thì ngược lại: chỉ cần chỉ đến index là ra liền. (Wikipedia, GeeksforGeeks)

3. Tương tác nhẹ

Bạn thử nghĩ:

Nếu muốn chèn một node vào giữa danh sách—ví dụ giữa người thứ 3 và thứ 4—thì cách làm ra sao?
Với linked list xoay vòng (circular), nếu bạn đang ở node cuối và gọi next, nó sẽ là gì? Hãy vẽ phác bằng sơ đồ nhỏ (ASCII art) để hiểu nhé!

4. Kết luận & lời khuyên

Tóm tắt:

Linked list là cách tổ chức dạng từng node nối nhau, dễ thêm/xóa.
Có nhiều biến thể: đơn, kép, vòng tròn, vừa kép vừa vòng.
Viết trong PHP khá đơn giản: chỉ cần class Node và LinkedList là chạy được.
Ưu điểm: thêm/xóa linh hoạt; Nhược điểm: chậm khi truy xuất ngẫu nhiên.

Mẹo học tốt hơn:

Hãy tự tay triển khai thêm các hàm như: insertAt, delete, printList.
Vẽ sơ đồ node–>node để hình dung dữ liệu chạy như thế nào.
So sánh trực tiếp với array để thấy điểm mạnh/yếu của từng kiểu.

5. Tài liệu tham khảo

Bài gốc “(Singly) Linked Lists explained in PHP”, do doeken.org - giải thích cơ bản và ví dụ thật sát với PHP. (doeken.org)
Wikipedia – Linked list: lý thuyết chi tiết, cấu trúc và ưu–nhược điểm. (Wikipedia)
GeeksforGeeks – Linked List Data Structure: bổ sung ví dụ, bài tập và so sánh array vs list. (GeeksforGeeks)

Mình hy vọng bài viết này giúp bạn cảm thấy hiểu hơn, gần gũi hơn và tự tin hơn với khái niệm Linked List. Nếu bạn cần mình giải thích thêm phần nào—ví dụ Circular, Doubly, hoặc thấy chỗ nào khó hiểu—hãy hỏi nhé!

Giải thích về Linked List trong PHP