บทที่ 3 ลิงค์ลิสต์

         ลิงค์ลิสต์ (Linked List)
               เป็นการจัดเก็บชุดข้อมูลเชื่อมโยงต่อเนื่องกันไปตามลำดับ โครงสร้างข้อมูลแบบลิงค์ลิสต์จะประกอบไปด้วยส่วนที่เรียกว่าสมาชิก ( Node) ส่วนเก็บข้อมูล (Data) และตำแหน่งของสมาชิกตัวถัดไป (Link)

       โครงสร้างข้อมูลลิงค์ลิสต์

      โครงสร้างของโหนด

     คุณสมบัติของลิงค์ลิสต์

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

             ➤  Data คือข้อมูลหรือสารสนเทศที่สามารถนำไปใช้ประโยชน์   

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

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

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

    

      การแทรกโหนด

     ขั้นตอนในการแทรกโหนดจัดสรรหน่วยความจำสำหรับโหนดใหม่พร้อมกับข้อมูลกำหนดตัวชี้ให้กับลิงค์ฟิลด์ของโหนดใหม่นำตัวชี้ที่อยู่ก่อนหน้าโหนดใหม่ชี้มายังโหนดใหม่ในการแทรกโหนดเพิ่มเข้าไปในลิสต์สามารถทำได้ 4 รูปแบบคือ

            ⟲ การแทรกโหนดในลิสต์ว่าง

            ⟲ การแทรกโหนดที่ตำแหน่งแรก

            ⟲การแทรกโหนดตรงส่วนกลางของลิสต์

            ⟲การแทรกโหนดที่ท้ายลิสต์

      การแทรกโหนดในลิสต์ว่าง (Insert into Empty List)

      

    

      การแทรกโหนดที่ตำแหน่งแรก (Insert at Beginning)

    การแทรกโหนดตรงส่วนกลางของลิสต์ (Insert in Middle)

       

   การแทรกโหนดที่ท้ายลิสต์ (Insert at End)

      การลบโหนด (Delete Node)
           อัลกอริธึมการลบโหนดออกจากลิสต์ นอกจากจะนำโหนดที่ถูกลบส่งคืนแก่หน่วยความจำระบบเพื่อจะได้นำไปใช้งานอื่นต่อไปแล้วยังต้องมีการปรับเปลี่ยนตัวชี้ใหม่ด้วย
        การลบข้อมูลออกจากโครงสร้างลิงค์ลิสต์ เกิดขึ้นได้หลายลักษณะสรุปได้ดังนี้
            1. การลบโหนดแรก
            2. การลบโหนดที่อยู่หลังโหนดที่กำหนด
            3. การลบโหนดสุดท้าย

        ขั้นตอนการลบโหนดมีดังนี้

                1. เก็บค่าตำแหน่งและค่าของ Pointer ของโหนดที่ต้องการลบ

                2. กำหนดค่าของ Pointer ของโหนดที่ต้องการลบ ไปยังโหนดก่อนหน้านั้น

                3. กำหนดตำแหน่งของโหนดที่ต้องการลบคืนกลับไปยัง Storage Pool

      

       Linked List Operation

        Retrieve Node➟ เป็นการดึงข้อมูลตัวที่ต้องการจากลิงค์ลิสต์ โดยค่าในลิงค์ลิสต์นั้นยังคงเดิม

        Empty List ➟เป็นการตรวจสอบว่าลิงค์ลิสต์นั้นไม่มีข้อมูล ใด ๆ เก็บไว้ใช่หรือไม่

        Full List ➟เป็นการตรวจสอบว่าลิงค์ลิสต์นั้นมีข้อมูลเก็บอยู่เต็มตามข้อกำหนดใช่หรือไม่

     List Count ➟เป็นการนับจำนวนข้อมูลที่เก็บอยู่ในลิงค์ลิสต์ ซึ่งจะเสียเวลาในการทำงานมาก ดังนั้นจึงควรเก็บจำนวน ข้อมูลในลิงค์ลิสต์ไว้ด้วยเมื่อมีการเพิ่มหรือลบข้อมูล

      Traverse List ➟เป็นการท่องไปในทุกโหนดของลิงค์ลิสต์

       Destroy List➟ เป็นการคืนพื้นที่หน่วยความจำ

       Search List ➟เป็นการค้นหาข้อมูลในลิสต์

     ลิงค์ลิสต์ชนิดอื่นๆ (Others Linked Lists)

      ⏩ เซอร์คูลาร์ลิงค์ลิสต์ (Circular-Linked List)

      ⏩ ดับเบิลลิงค์ลิสต์ (Double-Linked List)

      ⏩ มัลติลิงค์ลิสต์ (Multilinked List)

     เซอร์คูลาร์ลิงค์ลิสต์ (Circular-Linked List)  หมายถึง ลิงค์ลิสต์ที่โหนดสุดท้ายสามารถวกกลับมาที่

      โหนดแรกได้  ดังเช่นตัวอย่างต่อไปนี้

    ดับเบิลลิงค์ลิสต์ (Double-Linked List)หมายถึง ลิงค์ลิสต์ที่ทุกโหนดสามารถวกกลับมาที่โหนดก่อนหน้าของตนเองได้  ดังเช่นตัวอย่างต่อไปนี้

มัลติลิงค์ลิสต์ (Multilinked List)หมายถึง ลิงค์ลิสต์ที่สามารถเข้าถึงข้อมูลได้มากกว่า 1 คีย์

ดังเช่นตัวอย่างต่อไปนี้