ก่อนจะเข้าใจ Linked List เราควรทราบข้อเสียของ Array และข้อดีของ Pointer ในภาษา C ก่อน
ข้อเสียของ Array (อาร์เรย์)
- ใช้การจัดสรรหน่วยความจำแบบคงที่ (Static Memory Allocation)
- เกิดการสูญเสียหน่วยความจำ (Memory Wastage) ได้
- อาจเกิดปัญหาหน่วยความจำไม่พอ (Insufficient Memory)
ข้อดีของ Pointer (พอยน์เตอร์)
- ใช้การจัดสรรหน่วยความจำแบบไดนามิก (Dynamic Memory Allocation)
- ใช้หน่วยความจำได้อย่างมีประสิทธิภาพ
Linked List คืออะไร?
Linked List ใช้การจัดสรรหน่วยความจำแบบไดนามิก จึงสามารถขยายหรือย่อขนาดได้ตามต้องการ ถูกนิยามเป็นชุดของโหนด (Nodes) โดยแต่ละโหนดประกอบด้วย 2 ส่วนคือ ส่วนข้อมูล (Data) และส่วนลิงก์ (Link) รูปแบบการแสดงผลดังภาพ
ประเภทของ Linked List
Linked List มี 4 ประเภทหลัก
- Singly Linked List (Linked List แบบเดี่ยว) - โหนดชี้ไปข้างหน้าเพียงทางเดียว
- Doubly Linked List (Linked List แบบคู่) - โหนดชี้ได้ทั้งหน้าและหลัง
- Circular Singly Linked List (Linked List แบบเดี่ยววน) - โหนดสุดท้ายชี้กลับไปหาตัวแรก
- Circular Doubly Linked List (Linked List แบบคู่วน) - โหนดแรกและสุดท้ายเชื่อมต่อกันแบบสองทาง
Singly Linked List (Linked List แบบเดี่ยว)
โหนดประกอบด้วย 2 ส่วน:
- Data (ข้อมูล)
- Link/Next (ลิงก์ชี้ไปยังโหนดถัดไป)
ลิงก์ของโหนดสุดท้ายจะเป็น NULL
Doubly Linked List (Linked List แบบคู่)
โหนดประกอบด้วย 3 ส่วน:
- Data (ข้อมูล)
- Left Link / Prev (ลิงก์ชี้ไปยังโหนดก่อนหน้า)
- Right Link / Next (ลิงก์ชี้ไปยังโหนดถัดไป)
Left Link ของโหนดแรก และ Right Link ของโหนดสุดท้าย จะเป็น NULL
Circular Singly Linked List (Linked List แบบเดี่ยววน)
โหนดประกอบด้วย 2 ส่วน:
- Data (ข้อมูล)
- Link (ลิงก์ชี้ไปยังโหนดถัดไป)
ลิงก์ของโหนดสุดท้ายจะชี้กลับไปยังโหนดแรก (Head)
Circular Doubly Linked List (Linked List แบบคู่วน)
โหนดประกอบด้วย 3 ส่วน:
- Data (ข้อมูล)
- Left Link / Prev (ลิงก์ชี้ไปทางซ้าย/ก่อนหน้า)
- Right Link / Next (ลิงก์ชี้ไปทางขวา/ถัดไป)
Left Link ของโหนดแรกชี้ไปยังโหนดสุดท้าย และ Right Link ของโหนดสุดท้ายชี้ไปยังโหนดแรก
