กฎข้อ 1
Node รู้แค่ 2 อย่าง: value ของตัวเอง และ next
Node ไม่รู้อะไรเกี่ยวกับ list ทั้งระบบ — ไม่รู้ขนาด, ไม่รู้ว่าตัวเองอยู่ index ไหน, ไม่รู้ว่าใครชี้มาหาตัวเอง (ใน singly list)
Linked List
Linked List Foundations
ปูพื้นฐาน Linked List ตั้งแต่ node, head, tail, pointer ไปจนถึงภาพรวมว่าโครงสร้างนี้ต่างจาก array ยังไง
รู้จัก Linked List
Linked List คือโครงสร้างข้อมูลแบบลำดับที่ประกอบด้วย **node** หลายตัว — node แต่ละตัวบรรจุข้อมูลหนึ่งชิ้นและรู้ว่า node ถัดไปอยู่ที่ไหน (เก็บผ่าน pointer) แทนที่จะให้ข้อมูลทุกตัวอยู่ติดกันเหมือน array
ลองนึกภาพขบวนรถไฟ: ตู้โดยสารแต่ละตู้ (node) มีผู้โดยสารอยู่ข้างใน (value) และมีข้อต่อที่เชื่อมไปตู้ถัดไป (next pointer) — ถ้าอยากเดินทางจากตู้แรกไปตู้สุดท้าย ต้องเดินผ่านทุกตู้ตามข้อต่อ ไม่สามารถกระโดดข้ามตู้ได้
- Linked List เก็บข้อมูลใน node — ไม่ใช่ช่องต่อเนื่องแบบ array
- แต่ละ node มี value (ข้อมูล) และ pointer บอกตำแหน่ง node ถัดไป
- เข้าถึงสมาชิกต้องเดินทีละ node จากตัวแรกไป — ใช้เวลา O(n)
- เพิ่ม/ลบ node ท้ายหรือกลางทำได้ดีถ้ารู้ตำแหน่งอ้างอิง — O(1) ที่ตัว node เอง
Linked List: node แต่ละตัวเก็บข้อมูลและ pointer ชี้ไป node ถัดไป — ตัวสุดท้ายชี้ null
โครงสร้างของ Node — หน่วยย่อยที่เล็กที่สุดของ Linked List
**Node** คือหน่วยข้อมูลพื้นฐานของ Linked List — เปรียบเหมือนอิฐหนึ่งก้อนที่ประกอบด้วย 2 ส่วน: value (ข้อมูลที่เก็บ) และ next ( pointer บอกว่า node ถัดไปคือตัวไหน)
Node Structure — TypeScript TypeTS
โหนดพื้นฐานของ singly linked list: เก็บ value และ next pointer
จาก type ข้างบน: • `value: T` — ข้อมูลจริงที่ node นี้เก็บ (เป็น type ใด ๆ ก็ได้) • `next: SinglyNode<T> | null` — pointer ชี้ไป node ถัดไป หรือเป็น null ถ้าเป็น node สุดท้ายของรายการ Node ไม่รู้ว่ามีกี่ node ในลิสต์, ไม่รู้ว่า node ก่อนหน้าคือตัวไหน (ใน singly list), ไม่รู้ว่า index ของตัวเองคืออะไร — มันรู้แค่ข้อมูลของตัวเองและทางไป node ถัดไปเท่านั้น
Node — กฎสำคัญที่ต้องจำ
หัวใจของ node ที่เป็นรากฐานของ Linked List ทั้งระบบ
กฎข้อ 2
next ของ node สุดท้ายต้องเป็น null
null ในที่นี้แปลว่า "ไม่มี node ถัดไป" — มันคือสัญญาณบอกว่าจบรายการแล้ว ถ้าลืมตั้ง next เป็น null อาจทำให้เกิด infinite loop หรือ undefined behavior
กฎข้อ 3
Node เป็น reference type
node ถูกสร้างเป็น object ใน JavaScript — การ assign node ให้ตัวแปรใหม่เป็นการ copy reference ไม่ใช่ copy ข้อมูล จึงแก้ pointer ผิดที่ได้ง่าย ต้องระวัง
ระวัง
null ≠ undefined
ใน TypeScript ให้ใช้ null เพื่อสื่อว่า "ไม่มี node ถัดไป" อย่างชัดเจน — อย่าใช้ undefined ปนกันเพราะทำให้ type guard ทำงานไม่ตรงตามที่คิด
Head, Tail, และ Next Pointer — ส่วนประกอบสำคัญของ Linked List
Head คือทางเข้า, Tail คือทางออก, Next คือเส้นทางเดิน
- **Head** — reference ไปยัง node แรกของรายการ เปรียบเหมือน "ประตูเข้า" — ถ้าไม่มี head ก็เข้าไปใน list ไม่ได้ ทุกการดำเนินการ (traverse, search, insert, delete) ต้องเริ่มจาก head
- **Tail** — reference ไปยัง node สุดท้ายของรายการ (next เป็น null) การเก็บ tail ไว้ช่วยให้ append (เพิ่มท้าย) ทำได้ O(1) เพราะไม่ต้องเดินหาตัวสุดท้ายจาก head ใหม่ทุกครั้ง
- **Next Pointer** — field ใน node ที่เก็บ reference ไปยัง node ถัดไป เปรียบเหมือน "ลูกศร" หรือ "ข้อต่อ" ที่บอกเส้นทางเดิน — ถ้า pointer นี้ชี้ผิดหรือขาด โครงสร้าง linked list จะเสียหายทันที
การดำเนินการเกือบทุกอย่างบน linked list เริ่มจาก head เสมอ — ถ้า head เป็น null แปลว่าลิสต์ว่าง ไม่มี node ใด ๆ อยู่เลย
i
เก็บ tail ไว้ช่วยให้ append เร็วขึ้นจาก O(n) → O(1)
ใน singly linked list ที่ไม่มี tail การ append ต้องเดินจาก head ทีละ node จนสุดรายการ (O(n)) — แต่ถ้าเราเก็บ reference ไป tail ไว้ในคลาส เราสามารถต่อ node ใหม่ท้าย tail แล้วเลื่อน tail ได้ทันทีโดยไม่ต้องเดิน (O(1))
Linked List กับ Array — เข้าถึงข้อมูลต่างกันยังไง
Array และ Linked List ต่างเป็นโครงสร้างข้อมูลแบบลำดับ แต่หลักการทำงานภายในต่างกันสิ้นเชิง — มาทำความเข้าใจความแตกต่างว่าเมื่อไรควรใช้ตัวไหน
| หัวข้อ | Array | Linked List |
|---|---|---|
| การเก็บข้อมูลในหน่วยความจำ | ข้อมูลทุกตัวอยู่ติดกันเป็น contiguous block — แบบช่องจอดรถต่อเนื่อง | node แต่ละตัวกระจัดกระจายในหน่วยความจำ — เชื่อมกันด้วย pointer |
| Access by Index | O(1) — คำนวณตำแหน่งด้วยสูตร base + index × size | O(n) — ต้องเดินทีละ node จาก head จนถึง index เป้าหมาย |
| Insert ที่หัว | O(n) — ต้อง shift สมาชิกทุกตัวไปทางขวา | O(1) — สร้าง node ใหม่ชี้ next ไป head เดิม แล้วเลื่อน head |
| Insert ที่ท้าย | O(1) amortized — อาจต้อง resize ถ้าเต็ม | O(1) ถ้ามี tail — ชี้ next ของ tail ไป node ใหม่ |
| Delete ที่หัว | O(n) — ต้อง shift สมาชิกทุกตัวไปทางซ้าย | O(1) — เลื่อน head ไป next ของ head เดิม |
| ค้นหาข้อมูล | O(n) ไล่ไปเรื่อย ๆ หรือ O(log n) ถ้าเรียงแล้ว (binary search) | O(n) — ต้องเดินทีละ node จาก head |
| การใช้หน่วยความจำ | ประหยัดกว่า — มีแค่ข้อมูล ไม่มี pointer overhead | เปลืองกว่า — แต่ละ node มี overhead จาก next pointer |
i
ไม่มีโครงสร้างไหนดีกว่าเสมอ — ตัดสินจาก workload
ถ้างานของคุณเน้น random access และการอ่าน index บ่อย → เลือก Array ถ้าเน้น insert/delete บ่อย โดยเฉพาะต้น-กลาง list → เลือก Linked List
การเก็บข้อมูลของ Linked List ในหน่วยความจำ
Array = ช่องติดกัน, Linked List = โหนดกระจัดกระจายเชื่อมต่อกันด้วย pointer
โหนดใน linked list ไม่จำเป็นต้องอยู่ติดกันในหน่วยความจำ — มันถูกสร้างคนละตำแหน่ง แต่เชื่อมโยงกันผ่าน pointer ทำให้ linked list ยืดหยุ่นในการขยายขนาดสูงมาก (dynamic size) ไม่ต้องจองพื้นที่ล่วงหน้าเหมือน array
ข้อแลกเปลี่ยนคือ **cache locality** — เพราะข้อมูลอยู่กระจัดกระจาย CPU อาจ cache ข้อมูลได้ไม่ดีเท่า array ทำให้การ traverse ใน linked list จริง ๆ อาจช้ากว่า array traversal มาก (แม้ทั้งคู่จะเป็น O(n) ก็ตาม) แต่นี่เป็นเรื่องของ hardware ไม่ใช่ asymptotic complexity
ดูโค้ดทำงานทีละขั้น — สร้างและ traverse Linked List
ลองลงมือ — สร้าง Node Chain พร้อม Traverse
ได้เวลาลงมือสร้าง linked list ด้วยตัวเอง — เริ่มจากสร้าง node 3 ตัวเชื่อมกัน แล้ว traverse เพื่ออ่านค่าทั้งหมด
ทบทวนความเข้าใจ
5 questions
Linked List Foundations — Checkpoint
ทดสอบความเข้าใจก่อนไปเรียนรู้ singly linked list แบบลงลึก
1
4 choices
Text prompt
Node ใน linked list ประกอบด้วยอะไรบ้าง?
2
4 choices
Text prompt
ข้อใดคือวิธีการเข้าถึงสมาชิกตัวที่ 5 ของ linked list?
3
4 choices
Text prompt
ข้อใดคือ Time Complexity ของการ traverse linked list?
4
Fill in
Text input
node สุดท้ายของ linked list มีค่า next เป็นอะไร (เขียนเป็น JavaScript keyword)?
5
4 choices
Text prompt
ข้อใดเป็นข้อได้เปรียบของ Linked List เมื่อเทียบกับ Array?