บทที่ 4 Linked Lists (ลิงก์ลิสต์)

บทที่ 4 Linked Lists (ลิงก์ลิสต์) แนวคิดพื้นฐานเกี่ยวกับลิสต์แบบเชิงเส้น (Linear List Concepts)       คุณสมบัติเรียงลำดับของข้อมูลภายในลิสต์ที่มีลักษณะเป็นลำดับต่อเนื่อง โดยสมาชิกหรืออิลิเมนต์แต่ละตัวจะเชื่อมโยงกับอิลิเมนต์ตัวถัดไปในลักษณะเป็นรายการต่อเนื่องกันไป ลิสต์แบบเชิงเส้นแบ่งออกเป็น 2 ประเภท ดังนี้ คือ ลิสต์แบบทั่วไป (General List) สามารถแทรกหรือลบรายการลิสต์ ณ ตำแหน่งใดๆ ก็ได้โดยปราศจากข้อจำกัดในด้านของการดำเนินงานภายในลิสต์ แบ่งเป็น ลิสต์แบบสุ่ม (Random List) และลิสต์แบบเรียงลำดับ (Order List) ลิสต์แบบมีข้อจำกัด (Restricted List) ไม่ว่าจะเป็นการเพิ่มหรือลบข้อมูลออกจากลิสต์จะต้องกระทำที่จุดปลายด้านใดด้านหนึ่งของลิสต์เท่านั้น อาจอยู่ในรูปแบบของลิสต์ชนิด FIFO หรือลิสต์ชนิด LIFO ก็ได้ การดำเนินงานพื้นฐานของลิสต์ (Basic Operations)       ประกอบด้วย Insertion คือการแทรก สามารถแทรกแบบสุ่ม หรือแบบเรียงก็ได้ แต่จะมุ่งเน้นเกี่ยวกับลิสต์แบบเรียงลำดับเป็นสำคัญ โดยจะใช้คีย์เป็นตัวระบุข้อมูลที่มีการแทรกข้อมูลเข้าไประหว่างลิสต์ Delete คือการลบ จะต้องทำการค้นหาตำแหน่งข้อมูลที่ต้องการลบก่อน เมื่อพบตำแหน่งที่ต้องการลบแล้ว จึงนำสมาชิกตำแหน่งนั้นออกจากลิสต์ Retrieval คือการอ่าน ขั้นแรกจะต้องค้นหาตำแหน่งข้อมูลที่ต้องการลบให้พบเสียก่อน จากนั้นก็ทำการอ่านหรือดึงข้อมูลออกมาใช้งาน โดยการดำเนินการดังกล่าวไม่ได้มีการเปลี่ยนแปลงข้อมูลภายในลิสต์แต่อย่างใด Traversal คือการท่องเข้าไปในลิสต์ จะทำการเดินท่องเข้าไปยังแต่ละอิลิเมนต์ตามลำดับภายในลิสต์ ซึ่งมักใช้อัลกอริทึมแบบลูปในการท่องเข้าไปในลิสต์มากกว่าที่จะดำเนินการด้วยวิธีค้นหา แนวคิดของลิงก์ลิสต์ (Linked List Concepts)       อิลิเมนต์แต่ละตัวภายในลิงก์ลิสต์จะมีการบรรจุแอดเดรสเพื่อชี้ไปยังตำแหน่งโหนดตัวถัดไป ซึ่งแต่ละโหนดจะบรรจุส่วนสำคัญอยู่ 2 ส่วนด้วยกัน คือ Data (ข้อมูล) มีการจัดเก็บสารสนเทศที่สามารถนำไปใช้ประโยชน์ เพื่อไปใช้ประมวลผลตามที่ต้องการ Link (ลิงก์) ใช้สำหรับเชื่อมโยงไปยังข้อมูล โดยเริ่มจากเฮดพอยน์เตอร์ที่ชี้ไปยังตำแหน่งโหนดแรกของลิสต์ ลิงก์ในแต่ละโหนดจะเชื่อมโยงไปยังโหนดตัวถัดไปเรื่อยๆ ส่วนชื่อของลิสต์จะเป็นชื่อเดียวกันกับชื่อตัวแปรพอยน์เตอร์ โครงสร้างข้อมูลแบบลิงก์ลิสต์ (Linked List Data Structure)       ประกอบด้วย โครงสร้างโหนดส่วนหัว (Head Node Structure) จะมีเพียงหนึ่งพอยน์เตอร์ที่ชี้ไปยังลิสต์ คือ “เฮดพอยน์เตอร์” เกิดขึ้นหลังจากที่ได้ Create List ขึ้นมา โครงสร้างโหนดข้อมูล (Data Node Structure) ข้อมูลของลิสต์ขึ้นอยู่กับการนำไปประยุกต์ใช้ สรุป คุณสมบัติของลิงก์ลิสต์ ลิงก์ลิสต์จะใช้เฮดพอยน์เตอร์เป็นตัวชี้ไปยังโหนดแรกของลิสต์ ในขณะที่พอยน์เตอร์หรือลิงก์ของแต่ละโหนดก็จะเชื่องโยงลิงก์ไปยังโหนดตัวถัดไป โดยโหนดตัวสุดท้ายที่ไม่มีลิงก์ให้เชื่อมต่อจะถูกกำหนดค่าให้เป็น null โหนดข้อมูลจะประกอบด้วย Data และ Link ไม่มีความสัมพันธ์ทางกายภาพระหว่างโหนด ข้อมูลที่จัดเก็บภายในหน่วยความจำไม่จำเป็นต้องอยู่ติดกัน กรณีที่เฮดพอยน์เตอร์ไม่มีตัวชี้หรือไม่มีสมาชิก จะถูกกำหนดค่าเป็น null ซึ่งหมายถึงลิสต์ว่างนั่นเอง ข้อดีของลิงก์ลิสต์ เป็นโครงสร้างที่ง่ายต่อการเพิ่มหรือลบข้อมูล ไม่จำเป็นต้องขยับอิลิเมนต์ของลิสต์ไปข้างหน้าเพื่อเกิดพื้นที่ว่าง ใช้พื้นที่หน่วยความจำได้เต็มประสิทธิภาพ   อัลกอริทึมของลิงก์ลิสต์ (Linked List Algorithm) การสร้างลิสต์ (Create List) เป็นการกำหนดโครงสร้างโหนดส่วนหัว และกำหนดค่าเริ่มต้นให้กับ Metadata สำหรับลิสต์ การแทรกโหนด (Insert Node) เป็นฟังก์ชันที่ใช้สำหรับแทรกโหนดเข้าไปในลิสต์ ทำได้ 4 แบบ คือ การแทรกโหนดในลิสต์ว่าง การแทรกโหนดที่ตำแหน่งแรก การแทรกโหนดในส่วนกลางของลิสต์  การแทรกโหนดที่ท้ายลิสต์ การลบโหนด (Delete Node) โหนดทีถูกลบส่งคืนแก่หน่วยความจำระบบเพื่อจะได้นำไปใช้งานอื่นต่อไปแล้ว ยังต้องมีการปรับเปลี่ยนตัวชี้ใหม่ด้วย แบ่งเป็น การลบโหนดที่ตำแหน่งแรก (Delete First Node) การลบโหนดโดยทั่วไป (General Delete Case) การค้นหาข้อมูลภายในลิสต์ (Search List) เป็นฟังก์ชันที่ใช้สำหรับค้นหาข้อมูลภายในลิสต์ การดึงข้อมูลจากโหนดออกมาใช้งาน (Retrieve Node) เริ่มด้วยการค้นหาโหนดจากตำแหน่งข้อมูลภายในลิสต์ หากพบข้อมูลที่ต้องการ ก็จะทำการเคลื่อนย้ายข้อมูลไปยังเอาต์พุตในส่วนของโมดูลที่เรียกใช้งาน ลิสต์ว่าง (Empty List) เป็นฟังก์ชันที่ใช้ตรวจสอบว่าภายในลิสต์ว่างหรือไม่ ลิสต์เต็ม (Full List) เป็นฟังก์ชันที่ใช้ตรวจสอบว่าภายในลิสต์เต็มหรือไม่ จำนวนสมาชิกในลิสต์ (List Count) ภายในโมดูลจะมีเพียงประโยคคำสั่งเดียวเท่านั้น เป็นฟังก์ชันที่มีความสำคัญ การท่องเข้าไปในลิสต์ (Traverse List) จะเริ่มที่โหนดแรกและสแกนไปทีละโหนดจนกระทั่งสิ้นสุดที่โหนดสุดท้าย การยกเลิกการใช้งานลิสต์ (Destroy List) จะดำเนินการลบโหนดทุกโหนดที่ยังคงอยู่ภายในลิสต์ออกไปทั้งหมด และส่งคืนแก่หน่วยความจำระบบเพื่อนำไปใช้งานอื่นต่อไป ลิงก์ลิสต์ชนิดอื่นๆ เซอร์คูลาร์ลิงก์ลิสต์ (Circular-Linked List) จะใช้ลิงก์ของโหนดสุดท้ายเชื่อมโยงไปยังโหนดแรกของลิสต์ ดับเบิลลิงก์ลิสต์ (Double-Linked List) ในแต่ละโหนดจะประกอบไปด้วยพอยน์เตอร์อยู่  2 ตัว โดยตัวแรกจะใช้สำหรับชี้ไปยังตัวถัดไป และอีกตัวหนึ่งจะชี้ไปยังตัวก่อนหน้า **********จบแล้วจ่ะ**********