3.2 โครงสร้างข้อมูลแบบลิงก์ลิสต์ (Linked List Data Structure)
สำหรับโครงสร้างข้อมูลลิงก์ลิสต์ ประกอบด้วย
3.2 โครงสร้างข้อมูลแบบลิงก์ลิสต์ (Linked List Data Structure)
สำหรับโครงสร้างข้อมูลลิงก์ลิสต์ ประกอบด้วย
โครงสร้างโหนดส่วนหัว (Head Node Structure)
ภายในโหนดส่วนหัวจะมีเพียงหนึ่งพอยน์เตอร์ที่จะชี้ไปยังลิสต์ คือ เฮดพอยน์เตอร์ ภายในโครงสร้างส่วนนี้จะมี Metadata ที่เอาไว้อธิบายข้อมูลภายในลิสต์ ภายในนี้คือฟิลด์ Count
เพื่อเอาไว้บอกว่าในลิสต์นี้มีจำนวนสมาชิกทั้งหมดเท่าไร ซึ่งสามารถเพิ่มหรือลดลงได้ หากมีการแก้ไขข้อมูลในลิสต์
โครงสร้างโหนดข้อมูล (Data Node Structure)
โครงสร้างโหนดข้อมูลประกอบด้วยส่วนข้อมูลและลิงก์ สำหรับข้อมูล (Data type) ของลิสต์นั้นจะขึ้นอยู่กับการนำไปประยุกต์ใช้ แต่ปกติแล้ว ชนิดข้อมูลจะเป็นไปในลักษณะที่แสดงไว้ที่ด้านล่างและที่สำคัญ ชนิดข้อมูลจะต้องได้รับการปรับปรุงรายละเอียดอยู่เสมอหลังจากถูกสร้างขึ้น
ความจริงแล้วมีโครงสร้างข้อมูลอยู่หลายชนิดที่สามารถนำมาสร้างลิสต์ แต่หัวข้อต่อไปนี้จะขอกล่าวถึงการสร้างลิสต์ด้วยลิงก์ลิสต์เป็นสำคัญ โดยสามารถสรุปคุณสมบัติของลิงก์ลิสต์ได้ดังนี้ คือ
1. ลิงก์ลิสต์จะใช้เฮดพอยน์เตอร์ (pHead) เป็นตัวชี้ไปยังโหนดแรกของลิสต์ ในขณะที่พอยน์เตอร์หรือลิงก์ของแต่ละโหนดก็จะเชื่อมโยงลิงก์ไปยังโหนดตัวถัดไป โดยโหนดตัวสุดท้ายที่ไม่มีลิงก์ให้เชื่อมต่อจะถูกกำหนดค่าให้เป็น null ซึ่งในที่นี้ใช้สัญลักษณ์ S แทน
2. โหนดข้อมูลจะประกอบด้วย Data และ Link โดยที่
- Data คือข้อมูลหรือสารสนเทศที่สามารถนำไปใช้ประโยชน์
- Link คือตัวชี้หรือพอยน์เตอร์ที่ใช้สำหรับเชื่อมโยงไปยังโหนดถัดไป
3. ไม่มีความสัมพันธ์ทางกายภาพระหว่างโหนด
4. ข้อมูลที่จัดเก็บภายในหน่วยความจำไม่จำเป็นต้องอยู่ติดกัน
5. กรณีที่พอยน์เตอร์ไม่มีตัวชี้หรือไม่มีสมาชิก เฮดพอยน์เตอร์จะถูกกำหนดค่าเป็น null ซึ่งหมายถึงลิสต์ว่านั่นเองลิงก์ลิสต์จัดเป็นโครงสร้างข้อมูลที่ดีโครงสร้างหนึ่ง เพราะว่าเป็นโครงสร้างที่ง่ายต่อการเพิ่มและลบข้อมูลไม่ว่าจะกระทำที่ส่วนหน้า ส่วนหลัง หรือส่วนกลางของข้อมูล
ข้อดีของลิงก์ลิสต์
1.เป็นโครงสร้างที่ง่ายต่อการเพิ่มหรือลบข้อมูล
2.ไม่จำเป็นต้องขยับอิลิเมนต์ของลิสต์ไปข้างหน้าเพื่อให้เกิดพื้นที่ว่าง ในกรณีที่มีการลบอิลิเมนต์ตรงส่วนหน้าหรือส่วนกลางของลิสต์เช่นเดียวกับอาร์เรย์
3.ใช้พื้นที่หน่วยความจำได้เต็มประสิทธิภาพ เนื่องจากหากข้อมูลภายในลิสต์มีน้อยก็ใช้น้อยซึ่งผิดกับอาร์เรย์ที่ต้องสูญเสียพื้นที่ไปในทันที ถึงแม้จะไม่มีข้อมูลภายในลิสต์ก็ตาม