Mỗi nút biết nút tiếp theo
Trong mô hình này, `Node` giữ `key` là dữ liệu và `next` là tham chiếu tới nút kế tiếp; `LL` giữ `head` là nút đầu. Danh sách rỗng có `head is None`. Nút cuối có `next is None`. Một chuỗi ví dụ là `head → 5 → 2 → 8 → None`. Đây là cấu trúc **liên kết đơn**: từ một nút chỉ biết nút sau, muốn tìm nút trước phải bắt đầu từ head và duyệt. Python `list` quen thuộc là kiểu dữ liệu khác, dù cũng lưu được một dãy giá trị.
Nối nút mới trước khi đổi head
```python
class Node:
def __init__(self, key):
self.key = key
self.next = None
class LL:
def __init__(self):
self.head = None
def chen_dau(L, key):
moi = Node(key)
moi.next = L.head
L.head = moi
def cac_khoa(L):
ket_qua = []
x = L.head
while x is not None:
ket_qua.append(x.key)
x = x.next
return ket_qua
L = LL()
chen_dau(L, 5)
chen_dau(L, 2)
chen_dau(L, 8)
print(cac_khoa(L))
```
Kết quả là `[8, 2, 5]`, vì mỗi nút mới lên **đầu**. Hai dòng trong `chen_dau` có thứ tự quan trọng: đặt `moi.next` trỏ vào đầu cũ, rồi mới cho `head` trỏ vào nút mới. Nếu đổi head trước mà không giữ đầu cũ, các nút cũ sẽ không còn nối với danh sách mới. Khi L rỗng, `moi.next` nhận `None`, nên cùng mã vẫn hoạt động.
Bài luyện
Danh sách liên kết rỗng trong mô hình này có `L.head` bằng gì?
Chưa có nút đầu nên head là None.
0 có thể là dữ liệu hợp lệ.
Danh sách rỗng không có nút.
Không có nút cuối khi rỗng.
Lời giải
Hàm khởi tạo LL gán self.head = None; đó là trạng thái chưa có nút nào.
Bài luyện
Chèn đầu lần lượt 5, 2, 8 thì thứ tự khi duyệt từ head là gì?
Đây là thứ tự gọi hàm, không phải thứ tự cuối.
8 được chèn cuối cùng nhưng đứng đầu.
2 không còn đứng đầu sau khi chèn 8.
5 đứng sau 2.
Lời giải
Sau 5 là [5], sau 2 là [2,5], sau 8 là [8,2,5].
Bài luyện
Trong `chen_dau`, vì sao gán `moi.next = L.head` trước `L.head = moi`?
Nút mới cần giữ đường tới chuỗi cũ.
Chèn đầu không sắp xếp.
Nút cũ vẫn còn.
key là dữ liệu của nút.
Lời giải
Gán next của nút mới tới head cũ giữ các nút cũ; sau đó đổi head sang nút mới mới hoàn tất chèn.
Đang học