Linked lists · ลิงค์ลิสต์ (Linked lists)
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.
Node เชื่อมต่อกันด้วย Link
- Linked list คือ سلسلةของ nodes
- แต่ละ node เก็บ data ส่วนหนึ่งและมี link ไปยัง node ถัดไป
- Node สุดท้ายเชื่อมไปยัง
Noneซึ่งเป็นการระบุจุดสิ้นสุด
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.
Node คือ Record เล็กๆ
- เราสามารถเก็บ Node เด็ดๆ ไว้ใน Dictionary:
{"data": ..., "next": ...} "data"เก็บค่า;"next"เก็บ Node ถัดไป (หรือNone)- Node แรกเรียกว่า head ของรายการ
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.
Walk through the list
- เริ่มต้นที่ head และติดตาม
"next"link ต่อเนื่อง - หยุดเมื่อคุณถึง
None - การvisit ทุก node นี้เรียกว่า traversal
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.
ทำไมต้องใช้ Linked list?
- คุณสามารถเพิ่มหรือลบ node ได้โดยการ เปลี่ยน links — ไม่ต้องเลื่อนรายการ
- Array จะต้องย้ายรายการทั้งหมดหลังจาก发生改变
- แต่ลิงค์ลิสต์ไม่มี ดัชนี: ในการเข้าถึงรายการที่ 5 คุณต้องเดินจากหัว
In Cambridge pseudocode
- The exam stores nodes in an array;
Nextis the index of the next node, andNULLmarks the end.
ใน伪代码 Cambridge
- การสอบจัดเก็บโหนดในอาร์เรย์;
Nextคือดัชนีของโหนดถัดไป และNULLแสดงถึงจุดสิ้นสุด
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.
ข้อผิดพลาดที่พบบ่อย
- อย่าลืมชี้ที่
headเพราะถ้าจะหาทั้งลิงค์ลิสต์ไม่เจอเลย - โหนดสุดท้ายชี้ไปที่
None
Now you try
- A node is a dict
{"data": ..., "next": ...}. Follow"next"to walk the chain. - Press Check answer to test your code.
ลองดูเลย
- โหนดคือไดคท์
{"data": ..., "next": ...}. ติดตาม"next"เพื่อเดินผ่านห่วงโซ่ - กด Check answer เพื่อทดสอบโค้ดของคุณ
Nodes linked by pointers · โหนดเชื่อมต่อกันด้วยพอยเตอร์ (pointers)
Each node points to the next; you insert/delete by re-linking. · แต่ละโหนดชี้ไปยังโหนดถัดไป; เราสามารถแทรก/ลบได้โดย เชื่อมต่อใหม่ (re-linking)
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. · สร้างลิงค์ลิสต์ 1 → 2 → 3 โดยใช้ dictionary. สร้างโหนดทั้งสาม เชื่อมต่อแต่ละโหนดเข้ากับโหนดถัดไป และชี้ head ไปยังโหนดแรก. โหนดสุดท้ายต้องให้ "next" เป็น None
Click Run to see the output here. · คลิก Run เพื่อดูผลลัพธ์ที่นี่
Walk the linked list starting at head and add up every node's "data". Store the total in total (the answer is 60). · เดินผ่านลิงค์ลิสต์เริ่มจาก head และรวมค่าของโหนดทุกตัว "data". เก็บผลรวมไว้ใน total (คำตอบคือ 60)
Click Run to see the output here. · คลิก Run เพื่อดูผลลัพธ์ที่นี่
Write length(head) that returns how many nodes are in the linked list. An empty list (head is None) has length 0. · เขียน length(head) ที่ คืนค่า จำนวนโหนดในลิงค์ลิสต์. ลิงค์ลิสต์ว่าง (head เป็น None) มีความยาว 0
Click Run to see the output here. · คลิก Run เพื่อดูผลลัพธ์ที่นี่