Linked lists · Danh sách liên kết
Nodes joined by links
- A linked list is a chain of nodes.
- Each node holds a piece of data and a link to the next node.
- The last node links to
None, which marks the end.
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.
A node is a small record
- We can store one node in a dictionary:
{"data": ..., "next": ...}. "data"holds the value;"next"holds the next node (orNone).- The first node is called the head of the list.
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"])
Walk the list
- Start at the head and follow each
"next"link. - Stop when you reach
None. - This visiting of every node is called traversal.
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"]
Why a linked list?
- You can insert or remove a node by changing links — no shifting of items.
- An array would have to move every item after the change.
- But a linked list has no index: to reach item 5 you must walk from the head.
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.
In Cambridge pseudocode
- The exam stores nodes in an array;
Nextis the index of the next node, andNULLmarks the end.
Trong pseudocode Cambridge
- Đề thi lưu các nút trong mảng;
Nextlà 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 Next : INTEGER // index of the next node, or NULL
ENDTYPE
current ← head
WHILE current <> NULL
OUTPUT list[current].Data
current ← list[current].Next
ENDWHILE
Common mistakes
- Never lose the
headpointer, or the whole list is unreachable. - The last node points to
None.
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.
Now you try
- A node is a dict
{"data": ..., "next": ...}. Follow"next"to walk the chain. - Press Check answer to test your code.
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.
Nodes linked by pointers · Các nút được liên kết bởi con trỏ
Each node points to the next; you insert/delete by re-linking. · 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.
Build a linked list 1 → 2 → 3 using dictionaries. Make the three nodes, link each to the next, and point head at the first one. The last node's "next" must be None. · 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.
Click Run to see the output here. · Nhấn Chạy để xem kết quả ở đây.
Walk the linked list starting at head and add up every node's "data". Store the total in total (the answer is 60). · 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).
Click Run to see the output here. · Nhấn Chạy để xem kết quả ở đây.
Write length(head) that returns how many nodes are in the linked list. An empty list (head is None) has length 0. · 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.
Click Run to see the output here. · Nhấn Chạy để xem kết quả ở đây.