Danh sách liên kết
Các nút nối bởi liên kết
- Một linked list (danh sách liên kết) là một chuỗi các nodes (nút).
- Mỗi node chứa một phần data (dữ liệu) và một link (liên kết) đến node tiếp theo.
- Node cuối cùng liên kết với
None, đánh dấu sự kết thúc.
Một node là một bản ghi nhỏ
- Chúng ta có thể lưu trữ một node trong dictionary:
{"data": ..., "next": ...}. "data"giữ giá trị;"next"giữ nút tiếp theo (hoặcNone).- Node đầu tiên được gọi là head (đầu) của danh sách.
second = {"data": "b", "next": None}
first = {"data": "a", "next": second}
print(first["data"])
print(first["next"]["data"])
Duyệt qua danh sách
- Bắt đầu từ head và theo dõi mỗi link
"next". - Dừng lại khi bạn đạt đến
None. - Việc thăm hỏi mỗi node này được gọi là traversal (duyệt traversing).
head = {"data": 1, "next": {"data": 2, "next": None}}
node = head
while node is not None:
print(node["data"])
node = node["next"]
Tại sao dùng linked list?
- Bạn có thể chèn hoặc xóa một node bằng cách thay đổi links (liên kết) — không cần dịch chuyển các mục.
- Một array (mảng) sẽ phải di chuyển mọi mục sau khi thay đổi.
- Nhưng danh sách liên kết không có chỉ mục: để đến phần tử thứ 5, bạn phải đi từ đầu danh sách.
Trong pseudocode Cambridge
- Đề thi lưu các nút trong mảng;
NextIndexlà chỉ mục của nút tiếp theo, vàNULLđánh dấu sự kết thúc.
TYPE Node
DECLARE Data : INTEGER
DECLARE NextIndex : INTEGER // index of the next node, or NULL
ENDTYPE
current ← head
WHILE current <> NULL
OUTPUT list[current].Data
current ← list[current].NextIndex
ENDWHILE
Lỗi thường gặp
- Đừng bao giờ mất con trỏ
head, nếu không toàn bộ danh sách sẽ không thể truy cập được. - Nút cuối cùng trỏ về
None.
Bây giờ bạn thử
- Một nút là một dict
{"data": ..., "next": ...}. Theo"next"để di chuyển qua chuỗi. - Nhấn Check answer (Kiểm tra câu trả lời) để thử mã của bạn.
Các nút được liên kết bởi con trỏ
Mỗi nút chỉ trỏ đến nút tiếp theo; bạn chèn/xóa bằng cách gắn lại liên kết.
Độ khó 4/5 · 280 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
Xây dựng danh sách liên kết 1 → 2 → 3 dùng dictionaries. Tạo ba nút, liên kết mỗi nút với nút kế tiếp, và trỏ head vào nút đầu tiên. Nút cuối cùng phải có "next" bằng None.
Nhấn Chạy để xem kết quả ở đây.
Độ khó 4/5 · 280 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
Duyệt danh sách liên kết bắt đầu từ head và cộng tổng mọi node's "data". Lưu tổng vào total (kết quả là 60).
Nhấn Chạy để xem kết quả ở đây.
Độ khó 4/5 · 280 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
Viết length(head) trả về số lượng nút trong danh sách liên kết. Danh sách rỗng (head bằng None) có độ dài 0.
Nhấn Chạy để xem kết quả ở đây.