Danh sách liên kết đơn

Bạn sẽ học được gì

Danh sách liên kết (linked list) lưu dữ liệu theo cách hoàn toàn khác mảng: các phần tử không nằm liền kề, mà nối với nhau bằng "mũi tên". Bạn sẽ hiểu đánh đổi của nó — mất truy cập ngẫu nhiên, nhưng được thêm/xóa đầu cực nhanh.

1. Trực quan: chuỗi kho báu lần theo manh mối

Mảng giống dãy ô tủ đánh số. Danh sách liên kết giống trò chơi truy tìm kho báu: mỗi mảnh giấy ghi một giá trị và chỉ dẫn tới mảnh tiếp theo. Bạn không thể nhảy thẳng tới mảnh thứ 5 — phải lần theo từng manh mối.

 head
  │
  ▼
┌─────┬───┐   ┌─────┬───┐   ┌─────┬────┐
│ 10  │ ●─┼──▶│ 20  │ ●─┼──▶│ 30  │None│
└─────┴───┘   └─────┴───┘   └─────┴────┘
 (val)(next)

Mỗi nút (node) gồm 2 phần: val (giá trị) và next (con trỏ tới nút kế). head trỏ tới nút đầu. Nút cuối có next = None.

2. Định nghĩa nút và tạo danh sách

Đang tải trình chạy code…

3. Chạy debug: duyệt bằng cách lần theo next

Không có chỉ số để nhảy — phải đi từ head, mỗi bước nhảy theo next. Bước qua để thấy:

🐞 Duyệt 10 -> 20 -> 30Bước 1/8

1cur = head
2while cur is not None:
3  print(cur.val)
4  cur = cur.next

Biến tại bước này

cur

nút(10)

👉 Bắt đầu từ head (nút 10).

4. Khác biệt cốt lõi so với mảng

	Mảng	Danh sách liên kết
Bộ nhớ	liền kề	rải rác, nối bằng con trỏ
Truy cập phần tử thứ i	O(1) (nhảy thẳng)	O(n) (phải lần từ head)
Thêm/xóa ở ĐẦU	O(n) (dịch)	O(1) (đổi vài con trỏ)
Bộ nhớ thêm	không	mỗi nút tốn thêm 1 con trỏ

Đánh đổi rõ ràng: linked list mất truy cập ngẫu nhiên nhanh, nhưng được thêm/xóa đầu O(1). Bài 2.2.4 sẽ so kỹ khi nào chọn cái nào.

5. Vì sao KHÔNG có truy cập O(1)?

Vì các nút rải rác khắp bộ nhớ, không có công thức "đầu + i×kích thước" như mảng. Cách duy nhất tới nút thứ i là lần theo i mũi tên từ head → O(n). Đây là cái giá của sự linh hoạt.

6. Mẫu nhận diện

• Cần thêm/xóa liên tục ở đầu (hoặc ở vị trí đã có con trỏ) → linked list O(1), thắng mảng.
• Cần truy cập theo chỉ số nhiều → mảng thắng (O(1) vs O(n)).
• Nhiều bài (stack, queue, một số cây) xây trên linked list.

7. 🎮 Trò chơi: Hiểu linked list

🎮 Hiểu linked listCâu 1/4· Điểm 0· 🔥 0

Nhớ: nút = val + next; không nằm liền kề; muốn tới giữa phải lần từ head.

Mỗi nút trong linked list đơn chứa gì?

8. Quiz kiểm tra nhanh

📝 Quiz kiểm tra nhanh

1. Khác biệt cốt lõi giữa mảng và linked list là?

2. Ưu điểm chính của linked list so với mảng?

3. Vì sao linked list không có truy cập ngẫu nhiên O(1)?

9. Hoàn thành

…

☑️ Tiếp theo: 2.2.2 — Danh sách liên kết đôi & vòng.