Chuyển tới nội dung chính

Danh sách liên kết đôi & vòng

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

Linked list đơn chỉ đi một chiều. Bài này thêm hai biến thể: đôi (doubly) — mỗi nút biết cả nút trước, đi được hai chiều; và vòng (circular) — nút cuối nối lại về đầu. Mỗi loại giải một nhu cầu khác nhau.

1. Danh sách liên kết ĐÔI (doubly)​

Mỗi nút có hai con trỏ: next (nút sau) và prev (nút trước). Nhờ vậy đi được cả hai chiều.

        ┌────┬───┬───┐   ┌────┬───┬───┐   ┌────┬───┬────┐
None◀───┼─●  │10 │ ●─┼──▶┼─●  │20 │ ●─┼──▶┼─●  │30 │None│
        │prev│val│nxt│◀──┼prev│val│nxt│◀──┼prev│val│nxt │
        └────┴───┴───┘   └────┴───┴───┘   └────┴───┴────┘

Được: đi lùi dễ, xóa một nút khi đã có con trỏ tới nó là O(1) (vì biết cả nút trước). Trả giá: mỗi nút tốn thêm con trỏ prev; code phải cập nhật hai chiều khi sửa.

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

2. Chạy debug: đi NGƯỢC nhờ prev​

Điều linked list đơn không làm được: đi từ cuối về đầu. Bước qua:

🐞 Đi ngược 30 -> 20 -> 10 nhờ prevBước 1/7
1cur = cuoi          # bat dau tu nut cuoi (30)
2while cur is not None:
3  print(cur.val)
4  cur = cur.prev  # nhay LUI theo prev
Biến tại bước này
curnút(30)
👉 Bắt đầu từ nút cuối.

3. Danh sách liên kết VÒNG (circular)​

Nút cuối thay vì trỏ None thì trỏ ngược về đầu → tạo thành một vòng tròn không điểm kết.

   ┌──▶┌────┬───┐   ┌────┬───┐   ┌────┬───┐──┐
   │   │ 10 │ ●─┼──▶│ 20 │ ●─┼──▶│ 30 │ ●─┼─ │
   │   └────┴───┘   └────┴───┘   └────┴───┘  │
   └──────────────────────────────────────────┘

Ứng dụng: mọi thứ xoay vòng — lượt chơi trong game nhiều người, vòng phát nhạc lặp lại, lập lịch round-robin của CPU, bộ đệm vòng (circular buffer).

Cẩn thận vòng lặp vô hạn

Vì không có None kết thúc, duyệt danh sách vòng phải có điều kiện dừng riêng (vd quay lại đúng nút đầu), nếu không sẽ chạy mãi mãi.

4. Ba loại — chọn loại nào?​

LoạiĐặc điểmDùng khi
Đơnchỉ next, đi một chiềuđơn giản, tiết kiệm bộ nhớ; stack, queue cơ bản
Đôinext + prev, hai chiềucần đi lùi / xóa nút O(1); deque, LRU cache, undo/redo
Vòngcuối nối về đầudữ liệu xoay vòng; round-robin, circular buffer

5. Mẫu nhận diện​

  • Cần đi lùi hoặc xóa nhanh khi đã trỏ tới nút → danh sách đôi.
  • Dữ liệu lặp vòng (lượt, vòng phát, lịch xoay) → danh sách vòng.
  • Không cần hai thứ trên → danh sách đơn cho gọn nhẹ.

6. 🎮 Trò chơi: Đôi hay vòng?​

🎮 Chọn loại linked listCâu 1/4· Điểm 0· 🔥 0

Đôi = đi hai chiều (có prev). Vòng = cuối nối về đầu, dùng cho dữ liệu xoay vòng.

Quản lý lượt chơi xoay vòng giữa n người chơi → dùng?

7. Quiz kiểm tra nhanh​

📝 Quiz kiểm tra nhanh
1. Điểm khác của danh sách đôi so với đơn?
2. Danh sách vòng khác danh sách thường ở chỗ?
3. LRU cache / undo-redo thường dùng loại nào?

8. Hoàn thành​

…

☑️ Tiếp theo: 2.2.3 — Thao tác: chèn, xóa, đảo ngược.