Linked List (Danh sách liên kết) là một trong những cấu trúc dữ liệu nền tảng trong lập trình. Nó được hình thành từ một chuỗi các nút (nodes), trong đó mỗi node lưu giá trị (value) và một con trỏ (pointer) trỏ đến node tiếp theo trong danh sách. Cấu trúc này đặc biệt hữu ích khi làm việc với dữ liệu động hoặc các thao tác chèn, xoá phần tử thường xuyên.
Lưu ý: Bài viết này dành cho người mới bắt đầu. Tác giả chia sẻ lại quá trình tự học, với mong muốn truyền cảm hứng và củng cố kiến thức cho cộng đồng. Nếu bạn đã có kinh nghiệm, hãy tiếp tục luyện ở cấp độ cao hơn hoặc thử viết lại, giảng giải lại – vì đó là cách hiệu quả nhất để ghi nhớ và rèn luyện tư duy thuật toán.
1. Hiểu Linked List qua ví dụ trực quan
Hãy tưởng tượng Linked List giống như chuỗi ticket trên Jira hoặc Trello – mỗi ticket có liên kết “Next” dẫn đến ticket kế tiếp.
Trong thực tế, bạn bắt gặp Linked List ở rất nhiều nơi:
- Chức năng Undo/Redo trong Excel hoặc VS Code chính là ví dụ điển hình của Doubly Linked List:
- Ctrl + Z → đi lùi (prev)
- Ctrl + Y → đi tới (next)
- Trình duyệt web khi bạn nhấn Back hoặc Forward — chính là bạn đang di chuyển trong một Linked List hai chiều biểu diễn lịch sử truy cập.
2. Các loại Linked List phổ biến
Singly Linked List
Mỗi node chỉ có một con trỏ next trỏ đến node tiếp theo.
- Duyệt được từ
head → tailnhưng không thể quay lại. - Ưu điểm: đơn giản, tiết kiệm bộ nhớ, thao tác chèn hoặc xoá ở đầu danh sách nhanh (O(1)).
- Nhược điểm: không thể truy cập ngược; muốn tìm node trước phải duyệt từ đầu.
- Bài tập tiêu biểu: LeetCode 206 – Reverse Linked List.
Doubly Linked List
Mỗi node có cả hai con trỏ prev và next, cho phép duyệt hai chiều.
- Duyệt được theo cả hai hướng.
- Chèn/Xoá ở giữa thuận tiện hơn Singly List.
- Tốn thêm bộ nhớ để lưu
prev. - Cần cẩn trọng khi cập nhật con trỏ để tránh lỗi trỏ sai.
Circular Linked List
Node cuối cùng (tail) trỏ ngược lại node đầu (head), tạo thành vòng khép kín.
- Duyệt từ bất kỳ node nào cũng có thể đi qua toàn bộ danh sách.
- Ứng dụng trong round-robin scheduling hoặc các hệ thống cần vòng lặp liên tục.
- Cần xác định điều kiện dừng rõ ràng để tránh vòng lặp vô hạn.
3. So sánh Linked List và Array
| Tiêu chí | Array | Linked List |
|---|---|---|
| Truy cập theo index | O(1) | O(n) |
| Chèn/Xoá phần tử | O(n) | O(1) (nếu có pointer) |
| Bộ nhớ | Cấp phát cố định | Động, linh hoạt hơn |
| Ứng dụng | DB Index, Static Array | Undo/Redo, Cache, LRU Cache |
4. Các bài tập LeetCode nổi bật
- 206. Reverse Linked List → Đảo chiều con trỏ, dùng ba biến
prev,curr,next. - 141. Linked List Cycle → Phát hiện vòng lặp bằng hai con trỏ nhanh–chậm (
fast–slow pointers). - 21. Merge Two Sorted Lists → Gộp hai danh sách đã sắp xếp, cẩn thận trỏ đúng pointer.
- 146. LRU Cache → Kết hợp HashMap (O(1) lookup) và Doubly Linked List (O(1) reorder, delete).
5. Ví dụ code Python cơ bản
class Node:
def __init__(self, val):
self.val = val
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def insert_head(self, val):
node = Node(val)
node.next = self.head
self.head = node
def insert_end(self, val):
node = Node(val)
if not self.head:
self.head = node
return
curr = self.head
while curr.next:
curr = curr.next
curr.next = node
def print_list(self):
curr = self.head
while curr:
print(curr.val, end=" -> ")
curr = curr.next
print("None")
6. Cách học và luyện tập hiệu quả
Trước khi code, hãy vẽ sơ đồ Linked List trên giấy. Hầu hết lỗi sai khi thao tác với Linked List đến từ việc trỏ nhầm con trỏ (pointer), vì vậy hãy chắc chắn hiểu hướng đi của next và prev trước khi chạy code.
- Tập trung vào 4 nhóm bài: reverse list, detect cycle, merge lists, remove node, và LRU cache.
- Trong phỏng vấn backend/frontend, bạn thường được hỏi về trade-off giữa Array và Linked List.
- Chuẩn bị sẵn template
NodevàLinkedListđể code nhanh hơn. - Luôn tính trước time/space complexity để tối ưu giải pháp.
7. Tư duy rèn luyện quan trọng
Khi luyện Linked List, hãy bắt đầu bằng danh sách ngắn: [1 → 2 → 3 → None] hoặc [10 → 20 → 30 → 40 → None].
Với list ngắn, bạn dễ quan sát thay đổi sau từng thao tác insert, delete, reverse. Nếu gặp lỗi trỏ sai, việc in list nhỏ giúp phát hiện nhanh. Khi logic đã vững, hãy thử với test case lớn hơn.
Ngoài ra, hãy viết thêm helper function như print_list() hoặc to_array() để trực quan hóa dữ liệu sau mỗi bước.
8. Kết luận
- Linked List là nền tảng của nhiều cấu trúc dữ liệu khác như Stack, Queue, Graph và Cache.
- Hiểu bản chất con trỏ quan trọng hơn việc học thuộc công thức.
- Vẽ – Mô phỏng – Code – Tối ưu: đó là chu trình học hiệu quả nhất.
Tổng kết: Khi nắm vững Linked List, bạn sẽ hiểu sâu hơn cách dữ liệu vận hành trong bộ nhớ và mở rộng tư duy sang các cấu trúc phức tạp như Tree, Graph, Heap hay HashMap. Hiểu rõ bản chất trước, tối ưu sau – đó là tư duy đúng đắn khi học thuật toán.