ลิงค์ลิสต์ (Linked lists)
หน้านี้ต้องใช้เบราว์เซอร์ล่าสุด (รองรับ SharedArrayBuffer) กรุณาอัปเดต Chrome, Edge, Firefox หรือ Safari เป็นเวอร์ชันล่าสุด
Node เชื่อมต่อกันด้วย Link
- ลิงก์ liste คือสายโซ่ของ โหนด
- แต่ละ node เก็บ data ส่วนหนึ่งและมี link ไปยัง node ถัดไป
- Node สุดท้ายเชื่อมไปยัง
Noneซึ่งเป็นการระบุจุดสิ้นสุด
Node คือ Record เล็กๆ
- เราสามารถเก็บ Node เด็ดๆ ไว้ใน Dictionary:
{"data": ..., "next": ...} "data"เก็บค่า;"next"เก็บ Node ถัดไป (หรือNone)- Node แรกเรียกว่า head ของรายการ
English
second = {"data": "b", "next": None}
first = {"data": "a", "next": second}
print(first["data"])
print(first["next"]["data"])
เดินผ่านรายการ
- เริ่มต้นที่ head และติดตาม
"next"link ต่อเนื่อง - หยุดเมื่อคุณถึง
None - การvisit ทุก node นี้เรียกว่า traversal
English
head = {"data": 1, "next": {"data": 2, "next": None}}
node = head
while node is not None:
print(node["data"])
node = node["next"]
ทำไมต้องใช้ Linked list?
- คุณสามารถเพิ่มหรือลบ node ได้โดยการ เปลี่ยน links — ไม่ต้องเลื่อนรายการ
- An array would have to move every item after the change.
- แต่ลิงค์ลิสต์ไม่มี ดัชนี: ในการเข้าถึงรายการที่ 5 คุณต้องเดินจากหัว
In Cambridge pseudocode
- การสอบจัดเก็บโหนดในอาร์เรย์;
NextIndexคือดัชนีของโหนดถัดไป และNULLแสดงถึงจุดสิ้นสุด
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
ข้อผิดพลาดที่พบบ่อย
- อย่าลืมชี้ที่
headเพราะถ้าจะหาทั้งลิงค์ลิสต์ไม่เจอเลย - โหนดสุดท้ายชี้ไปที่
None
ลองดูเลย
- โหนดคือไดคท์
{"data": ..., "next": ...}. ติดตาม"next"เพื่อเดินผ่านห่วงโซ่ - กด Check answer เพื่อทดสอบโค้ดของคุณ
สำรวจ
โหนดเชื่อมต่อกันด้วยพอยเตอร์ (pointers)
แต่ละโหนดชี้ไปยังโหนดถัดไป; เราสามารถแทรก/ลบได้โดย เชื่อมต่อใหม่ (re-linking)
ความยาก 4/5 · 280 เหรียญ + บอนัสน้อยๆ เมื่อทำสำเร็จครั้งแรกในวันนี้
สร้างลิงค์ลิสต์ 1 → 2 → 3 โดยใช้ dictionary. สร้างโหนดทั้งสาม เชื่อมต่อแต่ละโหนดเข้ากับโหนดถัดไป และชี้ head ไปยังโหนดแรก. โหนดสุดท้ายต้องให้ "next" เป็น None
คลิก Run เพื่อดูผลลัพธ์ที่นี่
ความยาก 4/5 · 280 เหรียญ + บอนัสน้อยๆ เมื่อทำสำเร็จครั้งแรกในวันนี้
เดินผ่านลิงค์ลิสต์เริ่มจาก head และรวมค่าของโหนดทุกตัว "data". เก็บผลรวมไว้ใน total (คำตอบคือ 60)
คลิก Run เพื่อดูผลลัพธ์ที่นี่
ความยาก 4/5 · 280 เหรียญ + บอนัสน้อยๆ เมื่อทำสำเร็จครั้งแรกในวันนี้
เขียน length(head) ที่ คืนค่า จำนวนโหนดในลิงค์ลิสต์. ลิงค์ลิสต์ว่าง (head เป็น None) มีความยาว 0
คลิก Run เพื่อดูผลลัพธ์ที่นี่