ลิงก์ลิสต์ (Linked Lists)

แนวคิดพื้นฐานเกี่ยวกับลิสต์แบบเชิงเส้น (Linear List Concepts)
                      การเรียงลำดับของข้อมูลภายในลิสต์ที่มีลักษณะเป็นลำดับต่อเนื่อง สามารถอธิบายได้ โดย
         สมาชิก หรืออิลิเมนต์แต่ละตัวจะเชื่อมโยงอิลิเมนต์ตัวถัดไปลักษณะเป็นรายการต่อเนื่องกันไปตัว
         อย่างเช่น อิลิเมนต์ ลำดับที่สองจะอยู่ถัดจากอิลิเมนต์ลำดับที่หนึ่ง หรืออิลิเมนต์ลำดับที่สามจะอยู่ถัด
         จากอิลิเมนต์ตัวที่สอง ซึ่งจะลำดับเช่นนี้ไปเรื่อยๆ จนกระทั่งถึงอิลิเมนต์ลำดับที่ n+1ซึ่งจะอยู่ถัดจาก
         อิลิเมนต์ลำดับที่ n และด้วยคุณสมบัติดังที่กล่าวมานั้นเราจึงเรียกว่าลิสต์นั่นเอง

                       รูปที่ 3.1 โครงสร้างข้อมูลแบบเชิงเส้น (Linear List)

นอกจากนี้แล้ว ลิสต์แบบเชิงเส้นยังสามารถแบ่งออกเป็น 2 ประเภทด้วยกันคือ

 - ลิสต์แบบทั่วไป (General List) 

           ลักษณะของลิสต์แบบทั่วไป เราสามารถแทรกหรือลบรายการลิสต์ ณ ตำแหน่งใดๆก็ได้ โดย
ปราศจากข้อจำกัดในด้านของการดำเนินงานภายในลิสต์ นอกจากนี้แล้ว ลิสต์แบบทั่วไปยังสามารถ
แบ่งออกเป็น

1. ลิสต์แบบสุ่ม (Random List) ซึ่งข้อมูลภายในลิสต์จะไม่เรียงลำดับ
2. ลิสต์แบบเรียงลำดับ (Order List) ที่ข้อมูลภายในลิสต์จะถูกจัดเรียงอย่างเหมาะสมด้วย
   คีย์
3. ลิสต์แบบมีข้อจำกัด (Restricted List)ข้อมูลที่อยู่ภายในลิสต์แบบมีข้อจำกัด ไม่ว่าจะ
   เป็นการเพิ่มหรือการลบข้อมูลออกจากลิสต์จะต้องกระทำที่จุดปลายด้านใดด้านหนึ่งของลิสต์
   เท่านั้น เช่น ลิสต์แบบ FIFO ก็คือคิว ในขณะที่ลิสต์แบบ LIFO ก็คือสแต็ก

การดำเนินงานพื้นฐานของลิสต์ (Basic Operations)

           การดำเนินงานพื้นฐานของลิสต์ ประกอบด้วยการแทรก (Insertion) การลบ (Delete)
การอ่าน (Retrieval) และการท่องเข้าไปในลิสต์ (Traversal) โดยการแทรกก็คือการเพิ่มสมาชิก
ใหม่เข้าไปในลิสต์ การลบก็คือการนำสมาชิกออกจากลิสต์ การอ่านก็คือการประมวลผลในแต่ละอิลิ
เมนต์ภายในลิสต์ตามลำดับ เช่น การท่องเข้าไปในลิสต์เพื่อหาผลรวมของคะแนนดิบของนักศึกษา
ทั้งหมด และนำมาคิดเป็นคะแนนเฉลี่ย เป็นต้น

3.1 แนวคิดของลิสต์ลิสต์ (Linked List Concepts)

แนวคิดพื้นฐานเกี่ยวกับลิสต์แบบเชิงเส้น (Linear List Concepts)

             โครงสร้างข้อมูลแบบอาร์เรย์และโครงสร้างข้อมูลแบบลิงก์ลิสต์ก็ยังสามารถนำไปพัฒนา
โครงสร้างข้อมูลแบบสแต็กและคิว

                              รูปที่ 3.2 โครงสร้างข้อมูลแบบสแต็กและคิว

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

ข้อมูล (Data)
         ในส่วนของข้อมูลจะมีการจัดเก็บสารสนเทศที่สามารถนำไปใช้ในการประมวลผลตามที่ต้อง
การต่อไป

ลิงค์ (Link)
          ในส่วนของลิสต์นั้น จะใช้สำหรับเชื่อมโยงไปยังข้อมูลโดยเริ่มต้นจากเฮดพอยน์เตอร์ที่ชี้ไป
ยังตำแหน่งโหนดแรกของลิสต์ จากนั้นลิงก์ในแต่ละโหนดก็จะเชื่อมโยงไปยังโหนดตัวถัดไปเรื่อยๆ
ส่วนชื่อของลิสต์จะเป็นชื่อเดียวกันกับชื่อตัวแปรพอยน์เตอร์โดยลิงก์ลิสต์อย่างง่ายที่จะกล่าวถึงต่อ
ไปนี้คือ ซิงเกิลลิงก์ลิสต์ (Single-Linked List) ซึ่งจะมีเพียงลิงก์เดียวที่ใช้เชื่อมโยงไปยังโหนด
ตัวถัดไป

ตัวอย่างการแทนลิงก์ลิสต์ในหน่วยความจำ

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

3.3 อัลกอริทึมของลิงก์ลิสต์ (Linked List Algorithm)

                ในที่นี้จะมีฟังก์ชันการดำเนินงานบนลิงก์ลิสต์ 10 ฟังก์ชันด้วยกัน ซึ่งประกอบด้วยฟังก์ชัน
CreateList, Insert Node, Delete Node, Search List, Retrieve Node, Empty List,
Full List, ListCount, Traverse List และ Destory List ซึ่งถือว่าเพียงพอต่อการนำไปใช้เพื่อ
แก้ไขปัญหาต่างๆ อย่างไรก็ตาม หากแอปพลิเคชันบางตัวจำเป็นต้องมีการใช้ฟังก์ชันอื่นๆ เพิ่ม
เติมนอกเหนือจากฟังก์ชันทั้ง 10 ที่กล่าวมา ก็สามารถดำเนินการสร้างเพิ่มเติมได้อีก โดยแต่ละ
ฟังก์ชันจะมีการกำหนดชื่อเรียกของตัวเองพร้อมรายละเอียดอย่างย่อ รวมถึงพารามิเตอร์ที่เรียก
ใช้ ซึ่งแต่ละอัลกอริทึมสามารถอธิบายรายละเอียดได้ดังต่อไปนี้

1.การสร้างลิสต์ (Create List)

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

2.การแทรกโหนด (Insert Node) 

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

1.จัดสรรหน่วยความจำสำหรับโหนดใหม่พร้อมกับข้อมูล
2.กำหนดตัวชี้ให้กับลิงก์ฟิลด์ของโหนดใหม่
3.นำตัวชี้ที่อยู่ก่อนหน้าโหนดใหม่ชี้มายังโหนดใหม่

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

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

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

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

(a) Before add

                  

                                                                       (b) After add

รูปที่ 3.4 แสดงการแทรกโหนดเมื่อลิสต์ภายในว่าง

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

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

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

                                                                     (a) Before add

                   

                                                           (b) After add

                     รูปที่ 3.5 แสดงการแทรกโหนดไว้ที่ตำแหน่งแรกของลิสต์

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

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

                                                   (a) Before add

                   

                                                       (b) After add

รูปที่ 3.6 แสดงแทรกโหนดที่กึ่งกลางของลิสต์

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

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

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

a) Before add

            

(b) After add

รูปที่ 3.7  การแทรกโหนดไว้ที่ส่วนท้ายของลิสต์

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

3.การลบโหนด (Delete Node)

                  อัลกอริทึมการลบโหนดออกจากลิสต์นอกจากจะนำโหนดที่ถูกลบส่งคืนแก่หน่วยความ
จำระบบเพื่อจะได้นำไปใช้งานอื่นต่อไปแล้ว ยังต้องมีการปรับเปลี่ยนตัวชี้ใหม่ด้วย สำหรับขั้นตอน
แรกของการลบโหนด จะต้องค้นหาตำแหน่งของโหนดที่ต้องลบ (pLoc) ภายในลิสต์ให้พบก่อน เมื่อ
พบตำแหน่งโหนดที่ต้องการลบภายในลิสต์แล้ว จะทำให้ทราบตำแหน่งแอดเดรสของ Predecessor
(pPre) ซึ่งก็คือโหนดที่อยู่ก่อนหน้าโหนดที่ต้องการลบนั่นเอง หลังจากนั้นก็จะกำหนดลิงก์ฟิลด์ของ
โหนด Predecessorชี้ไปยังโหนด Successor ซึ่งเป็นโหนดที่อยู่ด้านหลังโหนดที่ถูกลบ จากนั้น
ก็จะนำพื้นที่หน่วยความจำที่เก็บโหนดที่ถูกลบไปนั้นส่งคืนแก่ระบบเพื่อนำไปใช้งานอื่นต่อไป

3.1การลบโหนดที่ตำแหน่งแรก  (Delete First Node)

                  เมื่อรู้ตำแหน่งแรกแล้ว (pLoc) ต่อมาก็ให้ทำการรีเซตเฮดพอยน์เตอร์เพื่อชี้ไปยังโหนด
Successor ที่อยู่ถัดไปจากโหนดแรกที่ต้องการลบ จากนั้นก็จะนำโหนดที่ถูกลบส่งคืนแก่ระบบ และ
เนื่องจากในที่เป็นการลบโหนดแรกออกจากลิสต์ ตัวโหนด Predecessor (pPre) ที่อยู่ก่อนหน้านั้น
จึงไม่มีดังนั้นโหนด pPre จึงถูกกำหนดค่าให้เป็น null ซึ่งก็หมายถึงเป็นการลบโหนดที่ตำแหน่งแรก
นั่นเอง

3.2 การลบโหนดโดยทั่วไป  (General Delete Case)

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

                                          (a) Before delete

      

                                               (b) After delete

รูปที่ 3.8 การลบโหนดออกจากลิสต์โดยทั่วไป

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

3.4 การค้นหาข้อมูลภายในลิสต์ (Search List)

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

การแทรกโหนด  ที่จำเป็นต้องรู้ตำแหน่งตัว Predecessorหรือโหนดก่อนหน้าของโหนดที่ต้อง
การจะแทรกก่อน

การลบโหนดออกจากลิสต์  ขั้นแรกต้องค้นหาโหนดที่ต้องการลบให้พบก่อน แล้วจึงค่อย กำหนด
ให้โหนด Predecessor ชี้ไปยังตำแหน่งโหนด Successor จากนั้นจึงปลดโหนดที่ลบไปนั้นคืน
แก่ระบบ

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

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

ลิสต์ว่าง (Empty List) เป็นฟังก์ชันที่ใช้ตรวจสอบว่าภายในลิสต์ว่างหรือไม่ ซึ่งเป็นโมดูลแบบ
ง่ายที่รีเทิร์นค่าตรรกะ ณ ขณะนั้นกลับไป เช่น รีเทิร์นค่าตรรกะเป็นจริงกลับไปเมื่อลิสต์ว่างหรือใน
ทางตรงกันข้ามก็จะรีเทิร์นค่าตรรกะเท็จกลับไป เป็นต้น

ลิสต์เต็ม (Full List) เป็นฟังก์ชันที่ใช้ตรวจสอบว่าภายในลิสต์นั้นเต็มหรือไม่ ซึ่งก็จัดเป็นโมดูล
แบบง่ายเช่นกันด้วยการรีเทิร์นค่าตรรกะในขณะนั้นกลับไป อย่างไรก็ตาม ฟังก์ชันนี้อาจไม่จำเป็น
ต้องใช้ก็ได้โดยเฉพาะในภาษา C เนื่องจากลิงก์ลิสต์ใช้หน่วยความจำแบบไดนามิก

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

แต่ละอิลิเมนต์แทน

3.5 การท่องเข้าไปในลิสต์ (Traverse List)

                  อัลกอริทึมการท่องเข้าไปในลิสต์ จะเริ่มต้นที่โหนดแรกและสแกนไปทีละโหนดจนกระ
ทั่งสิ้นสุดที่โหนดสุดท้าย ตรรกะของการท่องเข้าไปในลิสต์นั้น สามารถใช้อัลกอริทึมเพื่อใช้งานได้
อย่างหลากหลาย เช่น

1. การเปลี่ยนแปลงค่าในแต่ละโหนด
2. การพิมพ์ข้อมูลภายในลิสต์
3. การคำนวณหาผลรวมของฟิลด์ภายในลิสต์
4. การคำนวณหาค่าเฉลี่ย

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

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

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

    

รูปที่ 3.9 แสดงการท่องเข้าไปในลิสต์ (List Traversal)

การยกเลิกการใช้งานลิสต์ (Destroy List)

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

 ลิงก์ลิสต์ชนิดอื่นๆ (Others Linked Lists)
ความรู้เกี่ยวกับลิงก์ลิสต์ที่กล่าวมาในข้างต้นเป็นซิงเกิลลิงก์ลิสต์ (Single-Linked List) เนื่องจาก
บรรจุเพียงลิงก์เดียวที่ชี้ไปยังโหนดถัดไปเพียงโหนดเดียว ดังนั้นจึงทำให้ลิงก์ลิสต์ประเภทนี้มีข้อจำ
กัดคือไม่สามารถท่องเข้าไปยังลิงก์ลิสต์ในลักษณะจากหลังไปหน้าได้ การเข้าไปดำเนินการใดๆภาย
ในลิสต์จึงต้องเริ่มต้นจากโหนดแรกไปยังโหนดสุดท้าย และไม่สามารถเดินแบบย้อนกลับรายละเอียด
พื้นฐานเกี่ยวกับลิงก์ลิสต์ชนิดอื่นๆ ซึ่งมีความซับซ้อนมากกว่าซิงเกิลลิงก์ลิสต์ โดยในที่นี้ คือลิงก์ลิสต์
ประเภทต่อไปนี้

1. เซอร์คูลาร์ลิงก์ลิสต์ (Circular-Linked List)
2. ดับเบิลลิงก์ลิสต์ (Double-Linked List)

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

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

รูปที่ 3.10 Circular – linked List

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

                 ดับเบิลลิงก์ลิสต์จัดเป็นลิงก์ลิสต์ประเภทหนึ่งที่มีความสามารถสูงทีเดียว กล่าวคือ ดับเบิล
ลิงก์ลิสต์ในแต่ละโหนดจะประกอบไปด้วยพอยน์เตอร์อยู่ 2 ตัว โดยตัวแรกจะใช้สำหรับชี้ไปยังตัวถัดไป
(Successor) และอีกตัวหนึ่งจะชี้ไปยังตัวก่อนหน้า (Predecessor)ภายในโครงสร้างเฮดโหนดหรือ
โหนดส่วนหัวจะประกอบไปด้วยข้อมูลอยู่ 3 ฟิลด์คือ ตัวนับ (count) ตำแหน่งเฮดพอยน์เตอร์ และ
พอยน์เตอร์ฟิลด์ rearโดยถึงแม้ว่าฟิลด์ rear อาจไม่จำเป็นต่อการใช้งานสำหรับดับเบิลลิงก์ลิสต์ก็ตาม
แต่อาจจำเป็นต้องนำมาใช้งานในบางครั้ง โดยเฉพาะการแทรกและการค้นหา ซึ่งจะทำให้เกิดประ
สิทธิภาพยิ่งขึ้น

รูปที่ 3.11 ดับเบิลลิงก์ลิสต์ (Double-Linked List)

                 แต่ละโหนดของดับเบิลลิงก์ลิสต์จะบรรจุตัวชี้หรือพอยน์เตอร์อยู่สองตัวคือ Backward
Pointer ที่ชี้ไปยังข้างหลัง ซึ่งก็คือตัวก่อนหน้า (Perdecessor) ในขณะที่ Forward Pointer
จะชี้ไปยังข้างหน้า ซึ่ง ก็คือตัวถัดไป (Successor) โดยทั้งสองจะใช้อักษรย่อแทนว่า B และ F