DTS 21-07-52

สรุปบทเรียน Linked list

โครงสร้างข้อมูลแบบลิงค์ลิสต์ (Linked list)
โครงสร้างข้อมูลแบบนี้ จะให้ความสะดวกแก่การจัดการข้อมูลมาก อย่างไรก็ดีในบางครั้งก็ให้ความยุ่งยากแก่ผู้ใช้เนื่องจากจะซับซ้อนกว่าแบบใช้อาร์เรย์ ข้อจำกัดของการใช้อาร์เรย์คืออาร์เรย์มีขนาดคงที่ ถ้าเราจะใช้อาร์เรย์ขนาด 100 ช่อง เมื่อใช้หมด 100 ช่องก็ใช้อาร์เรย์นั้นไม่ได้ ถ้าไม่อนุญาตให้เคลียร์พื้นที่อาร์เาย์เพื่อใช้ซ้ำถึงแม้อนุญาตให้เคลียร์พื้นที่อาร์เรย์เพื่อใช้ซ้ำก็ไม่เป็นการสะดวก เนื่องจากอาจต้องตรวจทุกช่องในอาร์เรย์เพื่อหาว่าช่องไหนสามารถใช้ซ้ำได้ นอกจากนี้การใช้พื้นที่ซ้ำยังต้องเลื่อนข่าวสารทั้งหมดไปอยู่ในส่วนอาร์เรย์อีกประการคือ ในภาวะการทำงานแบบ real - time ที่ต้องมีการนำข้อมูลเข้า (insertion) หรือดึงข้อมูลออก (deletion) อาร์เรย์จะไม่สะดวกแก่การใช้มาก ในภาวะการทำงานแบบนี้โครงสร้างแบบลิงค์ลิสต์จะสะดวกกว่า การแทนแบบใช้พอยเตอร์นี้เราต้องใช้พื้นที่เพิ่มเติมเป็นส่วนของพอยน์เตอร์ (pointer) หรือลิงค์ (link) เพื่อแสดงให้เห็นขัดว่าโหนดที่ต่อจากโหนดนั้นคือโหนดใด ลักษณะของแต่ละโหนดจึงประกอบด้วยช่อง 2 ช่อง



ประเภทของ Linked list
1. แบบทิศทางเดียว
2. แบบสองทิศทาง
3. แบบวงกลม
4. แบบหลายทิศทาง


โครงสร้างของ Linked list มี 2 ส่วนใหญ่ๆ คือ
1. โครงสร้าง Head Node
2. โครงสร้าง Data Node


ลิงค์ลิสต์เดี่ยว (Singly Linked List)
ลิงค์ลิสต์เดี่ยว หมายถึง ลิงค์ลิสต์ที่แต่ละข่าวสารมีการแสดงออกถึงลำดับก่อนหลังอย่างชัดเจนโดยใช้พอยน์เตอร์ นั่นคือในแต่ละข่าวสารจะมีส่วนที่บอกว่าข่าวสารตัวต่อไปอยู่ที่ใด แต่ละข่าวสารจะเรียกว่าโหนด (node) แต่ละโหนดจะมี 2 ช่อง ดูรูปที่ 1 เป็นตัวอย่าง เราจะใช้สัญลักษณ์ต่อไปนี้ในการเรียกชื่อแต่ละโหนด

NODE(P) หมายถึง โหนดที่ระบุ(ถูกชี้) โดยพอยน์เตอร์ P
INFO(P) หมายถึง ส่วนข่าวสารของโหนดที่ถูกชี้โดย P
LINK(P) หมายถึง ส่วนแอดเดรสของโหนดที่ถูกชี้ P

ลิงค์ลิสต์คู่ (Doubly Linked List)
ลิงค์ลิสต์คู่ (Doubly Linked List) ลิงค์ลิสต์แบบนี้เป็นลิงค์ลิสต์ที่แต่ละโหนดมีสองพอยน์เตอร์คือ LLINK และ RLINK ซึ่งจะชี้ไปยังโหนดข้างซ้ายและข้างขวาของโหนดนั้นตามลำดับ ตัวอย่างเช่น ถ้าต้องการจะเก็บค่า A,B,C,D ในลิงค์ลิสต์ชนิดนี้จะได้โครงสร้างซึ่งปลายทั้งสองข้างของลิงค์ลิสต์ชนิดนี้จะมีพอยน์เตอร์ F และ R แสดงถึงโหนดแรกในทิศนั้น ถ้าใช้อาร์เรย์สร้างลิงค์ลิสต์ตามรูปที่ 19 จะต้องใช้อาร์เรย์ 3 ชุดคือ อาร์เรย์สำหรับช่องข่าวสาร (INFO) , อาร์เรย์สำหรับพอยน์เตอร์ทางซ้าย (LLINK) และอาร์เรย์สำหรับพอยน์เตอร์ทางขวา (RLINK)
เมื่อเปรียบเทียบลิงค์ลิสต์คู่กับลิงค์ลิสต์เดี่ยว จะเห็นได้ชัดว่าลิงค์ลิสต์คู่ต้องใช้เนื้อที่มากกว่า เนื่องจากต้องใช้ 2 พอยน์เตอรืสำหรับแต่ละโหนดแน่นอน ที่เสียไปนั้นก็เพื่อที่จะได้สิ่งบางอย่างเพิ่มเติม นั่นคือ ความสะดวกในการนำข่าวสารเข้าหรือออกจากลิงค์ลิสต์ ในกรณีลิงค์ลิสต์คู่ เราสามารถนำโหนดใหม่เข้าทาง ด้านหน้า หรือ ด้านหลังโหนด H1 ในลิงค์ลิสต์นั้นได้ นอกจากนี้เรายังสามารถคืนโหนด H1 ไปสู่ storage pool โดยตรงได้อีกด้วย อย่าลืมว่าเราไม่สามารถคืนโหนด H1 ไปสู่ storage pool ในกรณีลิงค์ลิสต์เดี่ยว