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

Linked list: chèn, xóa, đảo ngược

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

Sức mạnh thật của linked list nằm ở sửa con trỏ: thêm/xóa nút mà không phải dịch gì. Bạn sẽ nắm cách chèn/xóa, và học thuật toán đảo ngược danh sách liên kết — một bài phỏng vấn kinh điển.

1. Chèn vào đầu — O(1)​

Tạo nút mới, cho nó trỏ vào head cũ, rồi đổi head. Không dịch ai cả:

Trước:  head ──▶ [20] ──▶ [30] ──▶ None
Chèn 10:
  [10] ──▶ (head cũ)
Sau:    head ──▶ [10] ──▶ [20] ──▶ [30] ──▶ None
def chen_dau(head, val):
    moi = Node(val)
    moi.next = head      # tro vao head cu
    return moi           # head moi

So với mảng (chèn đầu O(n) vì phải dịch — nhớ bài 2.1.2), linked list chỉ đổi vài con trỏ → O(1).

2. Xóa nút kế tiếp — O(1)​

Cho con trỏ "nhảy qua" nút cần xóa:

Trước:  [10] ──▶ [20] ──▶ [30]
Xóa 20: [10] ─────────────▶ [30]   (10.next = 20.next)
def xoa_sau(nut):
    if nut.next:
        nut.next = nut.next.next   # bo qua nut ke

3. Chạy debug: ĐẢO NGƯỢC danh sách (3 con trỏ)​

Bài kinh điển. Ý tưởng: đi qua từng nút, lật mũi tên trỏ về phía sau. Cần 3 con trỏ: prev (đã đảo), cur (đang xét), nxt (nhớ trước khi mất). Bước qua với 1 -> 2 -> 3:

🐞 Đảo ngược 1 -> 2 -> 3Bước 1/9
1prev = None
2cur = head
3while cur is not None:
4  nxt = cur.next       # nho nut ke
5  cur.next = prev      # LAT mui ten ve sau
6  prev = cur           # tien prev
7  cur = nxt            # tien cur
8return prev              # head moi
Biến tại bước này
prevNone
cur1
👉 prev rỗng, cur ở nút 1.

4. Code mẫu (chạy thật)​

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

5. Vì sao đảo bằng 3 con trỏ cần nhớ nxt?​

Khi gán cur.next = prev, ta phá liên kết tới nút sau → mất đường đi tiếp. Vì vậy phải nhớ nxt = cur.next TRƯỚC khi lật. Quên bước này là lỗi phổ biến nhất của bài đảo danh sách.

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

  • Thêm/xóa nút → tư duy đổi con trỏ, không dịch dữ liệu.
  • "Đảo ngược linked list" → mẫu ba con trỏ (prev/cur/nxt), nhớ lưu nxt trước khi lật.
  • Xóa nút khi chỉ có con trỏ tới chính nó (không có nút trước) → mẹo: copy giá trị nút sau rồi xóa nút sau.

7. 🎮 Trò chơi: Thao tác linked list​

🎮 Thao tác linked listCâu 1/4· Điểm 0· 🔥 0

Thêm/xóa = đổi con trỏ → O(1). Đảo ngược = 3 con trỏ, nhớ nxt trước khi lật.

Đảo ngược linked list n nút tốn thời gian & bộ nhớ?

8. Quiz kiểm tra nhanh​

📝 Quiz kiểm tra nhanh
1. Vì sao thêm/xóa trong linked list thường O(1) (khi đã có con trỏ)?
2. Thuật toán đảo ngược linked list dùng mấy con trỏ?
3. Lỗi phổ biến nhất khi đảo linked list là?

9. Hoàn thành​

…

☑️ Tiếp theo: 2.2.4 — Mảng vs linked list: khi nào dùng gì.