Linked List
👋 อ่านฟรีทั้งหมดบน Aph's Blog — เนื้อหาภาษาไทย ทำตามทีละหน้าใน sidebar ได้เลย หากมีข้อเสนอแนะหรืออยากให้เพิ่มหัวข้อไหน บอกได้เสมอ
โครงสร้างที่แต่ละ node ชี้ไป node ถัดไป — เข้าใจ pointer และโจทย์สัมภาษณ์คลาสสิก
linked list คือลำดับของ node ที่แต่ละตัวเก็บข้อมูล + ตัวชี้ (pointer) ไป node ถัดไป Python ใช้ list เป็นหลัก แต่ linked list สำคัญในการเข้าใจ pointer และเจอบ่อยในโจทย์สัมภาษณ์
node + pointer
python
class Node:
def __init__(self, value):
self.value = value
self.next = None # ชี้ไป node ถัดไป (None = จบ)
# สร้าง: 1 -> 2 -> 3
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
# เดินผ่าน (traverse)
node = head
while node:
print(node.value) # 1, 2, 3
node = node.nextlist vs linked list
| operation | array/list | linked list |
|---|---|---|
| เข้าถึง index i | O(1) | O(n) |
| เพิ่ม/ลบหัว | O(n) | O(1) |
| ค้นหาค่า | O(n) | O(n) |
reverse linked list (โจทย์คลาสสิก)
python
def reverse(head):
prev = None
curr = head
while curr:
nxt = curr.next # จำตัวถัดไป
curr.next = prev # กลับทิศ
prev = curr # ขยับ prev
curr = nxt # ขยับ curr
return prev # หัวใหม่two-pointer กับ linked list
เทคนิค fast/slow pointer (ตัวเดินเร็ว 2 ก้าว, ช้า 1 ก้าว) ใช้หา "กลางลิสต์" หรือ "ตรวจ cycle" ได้ — เป็นจุดเชื่อมไปหัวข้อ two-pointer ที่กำลังจะเรียน
สรุปหัวข้อนี้
- linked list = node (ข้อมูล + next pointer) ต่อกัน
- เข้าถึง index ช้า O(n) แต่เพิ่ม/ลบหัว O(1) (ต่างจาก array)
- traverse ด้วย while node: ... node = node.next
- reverse และ fast/slow pointer คือโจทย์ที่เจอบ่อย
แบบฝึกหัด
1) สร้าง linked list 1->2->3->4 แล้ว print ทุกค่า 2) เขียน reverse linked list 3) หา node กลางด้วย fast/slow pointer 4) นับจำนวน node ใน list