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

ลิงก์ลิสต์ เป็นโครงสร้างข้อมูลแบบไดนามิก โดยที่ขนาดของมันสามารถเปลี่ยนแปลงได้ โดยสมาชิกแต่ละตัวของลิงค์ลิสต์จะถูกเรียกว่าโหนด (Node) ประกอบด้วย 2 ส่วนคือ ส่วนของข้อมูล (Data) และส่วนที่เป็นตำแหน่งที่อยู่ของโหนดตัวต่อไปในลิงค์ลิสต์ (Next Address) หรืออาจเรียกว่า พอยเตอร์ (Pointer) ซึ่งทำให้เราสามารถกำหนดตำแหน่งของโหนดตัวต่อไปได้ด้วยคุณสมบัติเรียงลำดับของข้อมูลภายในลิสต์ที่มีลักษณะเป็นลำดับต่อเนื่อง ลิสต์แบบเชิงเส้น แบ่งออกเป็น 2 ประเภทด้วยกันคือ
1. ลิสต์แบบทั่วไป (General List) เราสามารถแทรกหรือลบรายการลิสต์ ณ ตำแหน่งใดๆก็ได้ แบ่งออกเป็น

-ลิสต์แบบสุ่ม ข้อมูลภายในลิสต์จะไม่เรียงลำดับ
-ลิสต์แบบเรียงลำดับ ข้อมูลภายในลิสต์จะถูกจัดเรียงอย่างเหมาะสมด้วยคีย์

2. ลิสต์แบบมีข้อจำกัด (Restricted List) การเพิ่มหรือลบข้อมูลออกจาลิสต์จะต้องกระทำที่จุดปลายด้านใดด้านหนึ่งของลิสต์เท่านั้น
การดำเนินงานพื้นฐานของลิสต์ (Basic Operations)
1. การแทรก (Insertion) สามารถแทรกได้แบบลำดับหรือแบบสุ่มก็ได้ จะใช้คีย์เป็นตัวระบุข้อมูล
2. การลบ (Deletion) จะต้องทำการค้นหาตำแหน่งข้อมูลที่ต้องการลบก่อน เมื่อพบตำแหน่งที่ต้องกาลบแล้วจึงนำสมาชิกตำแหน่งนั้นออกจากลิสต์
3. การอ่าน (Retrieval) ต้องค้นหาตำแหน่งข้อมูลที่ต้องการลบให้พบก่อน จากนั้นก็ทำการอ่านหรือดึงข้อมูลออกมาใช้งาน โดยการดำเนินงานดังกล่าวจะไม่มีการเปลี่ยนแลงข้อมูลภายในลิสต์แต่อย่างใด
4. การท่องเข้าไปในลิสต์ (Traversal) มักใช้อัลกอริทึมแบบลูปในการท่องเข้าไปในลิสต์มากกว่าที่จะดำเนินการด้วยวิธีค้นหา
แนวคิดของลิงก์ลิสต์ (Linked List Concepts)
     ข้อมูลภายในหน่วยความจำจะถูกเชื่อมโยงด้วยลิงก์หรือพอยเตอร์ ดังนั้นอิลิเมนต์แต่ละตัวภายในลิงก์ลิสต์จะมีการบรรจุอดเดรสเพื่อชี้ไปยังตำแหน่งโหนดตัวถัดไป ซึ่งแต่ละโหนดก็จะบรรจุส่วนสำคัญ 2 ส่วน คือ

-ข้อมูล (Data)
-ลิงก์ (Link)

โครงสร้างข้อมูลแบบลิงก์ลิสต์ (Linked List Data Structure)
1. โครงสร้างโหนดส่วนหัว (Head Node Structure) จะมีเพียงหนึ่งพอยเตอร์ที่ชี้ไปยังลิสต์ ซึ่งก็คือ “เฮดพอยน์เตอร์” โครงสร้างโหนดส่วนหัวนี้จะเกิดขึ้นหลังจากที่ได้ Create List ขึ้นมา
2. โครงสร้างโหนดข้อมูล (Data Node Structure) 
คุณสมบัติของลิงก์ลิสต์
1. ลิงก์ลิสต์จะใช้เฮดพอยน์เตอร์เป็นตัวชี้ไปยังโหนดแรกของลิสต์ ในขณะที่พอยน์เตอร์หรือลิงก์ของแต่ละโหนดก็จะเชื่องโยงลิงก์ไปยังโหนดตัวถัดไป โดยโหนดตัวสุดท้ายที่ไม่มีลิงก์ให้เชื่อมต่อจะถูกกำหนดค่าให้เป็น null
2. โหนดข้อมูลจะประกอบด้วย Data และ Link
3. ไม่มีความสัมพันธ์ทางกายภาพระหว่างโหนด
4. ข้อมูลที่จัดเก็บภายในหน่วยความจำไม่จำเป็นต้องอยู่ติดกัน
5. กรณีที่เฮดพอยน์เตอร์ไม่มีตัวชี้หรือไม่มีสมาชิก จะถูกกำหนดค่าเป็น null ซึ่งหมายถึงลิสต์ว่างนั่นเอง
ข้อดีของลิงก์ลิสต์
1. เป็นโครงสร้างที่ง่ายต่อการเพิ่มหรือลบข้อมูล
2. ไม่จำเป็นต้องขยับอิลิเมนต์ของลิสต์ไปข้างหน้าเพื่อเกิดพื้นที่ว่าง
3. ใช้พื้นที่หน่วยความจำได้เต็มประสิทธิภาพ
อัลกอริทึมของลิงก์ลิสต์ (Linked List Algorithm)
- การสร้างลิสต์ (Create List) เป็นการกำหนดโครงสร้างโหนดส่วนหัว และกำหนดค่าเริ่มต้นให้กับ Metadata สำหรับลิสต์
- การแทรกโหนด (Insert Node) เป็นฟังก์ชันที่ใช้สำหรับแทรกโหนดเข้าไปในลิสต์ ทำได้ 4 แบบ คือ
     1. การแทรกโหนดในลิสต์ว่าง เป็นการแทรกสมาชิกตัวแรกเข้าไป
     2. การแทรกโหนดที่ตำแหน่งแรก ทำให้โหนดที่เคยอยู่ลำดับแรกเดิมต้องมาต่อท้ายโหนดใหม่ที่แทรกเข้าไป
     3. การแทรกโหนดในส่วนกลางของลิสต์ ในการแทรกระหว่างสองโหนด ตัวชี้หรือลิงก์ฟิลด์ของโหนดใหม่จะชี้ไปยังโหนด Successor ในขณะที่ตัวชี้ pPre
ก็จะชี้ไปยังโหนดใหม่
     4. การแทรกโหนดที่ท้ายลิสต์ ลิงก์ฟิลของโหนดใหม่จะถูกกำหนดค่าให้เป็น null
- การลบโหนด (Delete Node) ขั้นตอนการลบโหนด 

1. ค้นหาตำแหน่งของโหนดที่ต้องการลบ (pLoc)

2. เมื่อพบตำแหน่งที่ต้องการลบแล้วจะทำให้ทราบตำแหน่งแอดแดรสของ pPre

3. กำหนดลิงก์ฟิลด์ของโหนด Predecessor ชี้ไปยังโหนด Successor ซึ่งเป็นโหนดที่อยู่ด้านหลังโหนดที่ถูกลบ

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

การลบโหนด แบ่งเป็น
1. การลบโหนดที่ตำแหน่งแรก (Delete First Node)
2. การลบโหนดโดยทั่วไป (General Delete Case)
- การค้นหาข้อมูลภายในลิสต์ (Search List) หลักการค้นหาข้อมูลภายในลิงก์ลิสต์จะใช้คีย์เป็นัตวค้นหา โดยจะมีคีย์ฟิลด์ที่ใช้สำหรับเปรียบเทียบกับข้อมูลที่ต้องการค้นหา
- การดึงข้อมูลจากโหนดออกมาใช้งาน (Retrieve Node) เริ่มด้วยการค้นหาโหนดจากตำแหน่งข้อมูลภายในลิสต์ หากพบข้อมูลที่ต้องการ ก็จะทำการเคลื่อนย้ายข้อมูลไปยังเอาต์พุตในส่วนของโมดูลที่เรียกใช้งาน และจะรีเทิร์นค่าตรรกะเป็นจริงกลับไป แต่ถ้าไม่พบจะรีเทิร์นค่าตรรกะเป็นเท็จกลับไป
· ลิสต์ว่าง (Empty List) 
· ลิสต์เต็ม (Full List) 
- จำนวนสมาชิกในลิสต์ (List Count) ภายในโมดูลจะมีเพียงประโยคคำสั่งเดียวเท่านั้น เป็นฟังก์ชันที่มีความสำคัญ
- การท่องเข้าไปในลิสต์ (Traverse List) จะเริ่มที่โหนดแรกและสแกนไปทีละโหนดจนกระทั่งสิ้นสุดที่โหนดสุดท้าย
- การยกเลิกการใช้งานลิสต์ (Destroy List) จะดำเนินการลบโหนดทุกโหนดที่ยังคงอยู่ภายในลิสต์ออกไปทั้งหมด และส่งคืนแก่หน่วยความจำระบบเพื่อนำไปใช้งานอื่นต่อไป

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