3.2 โครงสร้างข้อมูลแบบลิงก์ลิสต์ (Linked List Data Structure)

                 สำหรับโครงสร้างข้อมูลลิงก์ลิสต์ ประกอบด้วย

          ความจริงแล้วมีโครงสร้างข้อมูลอยู่หลายชนิดที่สามารถนำมาสร้างลิสต์ แต่หัวข้อต่อไปนี้จะขอกล่าวถึงการสร้างลิสต์ด้วยลิงก์ลิสต์เป็นสำคัญ โดยสามารถสรุปคุณสมบัติของลิงก์ลิสต์ได้ดังนี้ คือ

         1. ลิงก์ลิสต์จะใช้เฮดพอยน์เตอร์ (pHead) เป็นตัวชี้ไปยังโหนดแรกของลิสต์ ในขณะที่พอยน์เตอร์หรือลิงก์ของแต่ละโหนดก็จะเชื่อมโยงลิงก์ไปยังโหนดตัวถัดไป โดยโหนดตัวสุดท้ายที่ไม่มีลิงก์ให้เชื่อมต่อจะถูกกำหนดค่าให้เป็น null ซึ่งในที่นี้ใช้สัญลักษณ์   S  แทน

          2. โหนดข้อมูลจะประกอบด้วย Data และ Link โดยที่

              - Data คือข้อมูลหรือสารสนเทศที่สามารถนำไปใช้ประโยชน์
              - Link คือตัวชี้หรือพอยน์เตอร์ที่ใช้สำหรับเชื่อมโยงไปยังโหนดถัดไป

         3. ไม่มีความสัมพันธ์ทางกายภาพระหว่างโหนด

         4. ข้อมูลที่จัดเก็บภายในหน่วยความจำไม่จำเป็นต้องอยู่ติดกัน

         5. กรณีที่พอยน์เตอร์ไม่มีตัวชี้หรือไม่มีสมาชิก เฮดพอยน์เตอร์จะถูกกำหนดค่าเป็น null ซึ่งหมายถึงลิสต์ว่านั่นเองลิงก์ลิสต์จัดเป็นโครงสร้างข้อมูลที่ดีโครงสร้างหนึ่ง เพราะว่าเป็นโครงสร้างที่ง่ายต่อการเพิ่มและลบข้อมูลไม่ว่าจะกระทำที่ส่วนหน้า ส่วนหลัง หรือส่วนกลางของข้อมูล

ข้อดีของลิงก์ลิสต์

1.เป็นโครงสร้างที่ง่ายต่อการเพิ่มหรือลบข้อมูล

2.ไม่จำเป็นต้องขยับอิลิเมนต์ของลิสต์ไปข้างหน้าเพื่อให้เกิดพื้นที่ว่าง ในกรณีที่มีการลบอิลิเมนต์ตรงส่วนหน้าหรือส่วนกลางของลิสต์เช่นเดียวกับอาร์เรย์

3.ใช้พื้นที่หน่วยความจำได้เต็มประสิทธิภาพ เนื่องจากหากข้อมูลภายในลิสต์มีน้อยก็ใช้น้อยซึ่งผิดกับอาร์เรย์ที่ต้องสูญเสียพื้นที่ไปในทันที ถึงแม้จะไม่มีข้อมูลภายในลิสต์ก็ตาม