ลิงค์ลิสต์ (Linked List) เป็นโครงสร้างข้อมูลที่ถูกประยุกต์ใช้ในการคำนวณและประมวลผลต่างๆมากมาย การเก็บข้อมูลลิงค์ลิสต์จะเป็นแบบลำดับเช่นเดียวกันกับสแตคและคิว เพียงแต่งลำดับในข้อมูลในลิงค์ลิสต์อาจจะตรงหรือไม่ตรงกับลำดับของข้อมุลที่เก็บไว้บนพื้นที่เก็บข้อมูลก็ได้
ข้อมูล (Data)
ในส่วนของข้อมูลจะมีการจัดเก็บสารสนเทศที่สามารถนำไปใช้ในการประมวลผลตามที่ต้อง
การต่อไป
ลิงค์ (Link)
ในส่วนของลิสต์นั้น จะใช้สำหรับเชื่อมโยงไปยังข้อมูลโดยเริ่มต้นจากเฮดพอยน์เตอร์ที่ชี้ไป
ยังตำแหน่งโหนดแรกของลิสต์ จากนั้นลิงก์ในแต่ละโหนดก็จะเชื่อมโยงไปยังโหนดตัวถัดไปเรื่อยๆ
ส่วนชื่อของลิสต์จะเป็นชื่อเดียวกันกับชื่อตัวแปรพอยน์เตอร์โดยลิงก์ลิสต์อย่างง่ายที่จะกล่าวถึงต่อ
ไปนี้คือ ซิงเกิลลิงก์ลิสต์ (Single-Linked List) ซึ่งจะมีเพียงลิงก์เดียวที่ใช้เชื่อมโยงไปยังโหนด
ตัวถัดไป
โครงสร้างข้อมูลแบบลิงก์ลิสต์ (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 ซึ่งหมาย ถึงลิสต์ว่านั่นเองลิงก์ลิสต์จัดเป็นโครงสร้างข้อมูลที่ดีโครงสร้างหนึ่ง
เพราะว่าเป็นโครงสร้างที่ ง่ายต่อการเพิ่มและลบข้อมูลไม่ว่าจะกระทำที่ส่วนหน้า
ส่วน หลัง หรือส่วนกลางของข้อมูล
การสร้างลิสต์ (Create List)
ฟังก์ชัน Create List เป็นการกำหนดโครงสร้างโหนดส่วนหัวและกำหนดค่าเริ่มต้น
ให้ กับ metadata สำหรับลิสต์โดยในที่นี้จะมี metadata อยู่ 2 ตัวด้วยกัน แต่ก็อาจขยาย
เพิ่มเติมได้
การแทรกโหนด (Insert Node)
เป็นฟังก์ชันที่ใช้สำหรับแทรกโหนดเพิ่มเข้าไปในลิสต์ ณ ขณะนี้ต้องการเพียงว่า โหนด
ก่อนหน้า (Predecessor) ของโหนดใหม่ที่จะแทรกนั้นคือโหนดใดเมื่อได้รับการแจ้งว่าโหนด
ก่อนหน้าคือโหนดใดแล้ว ก็จะทำการแทรกข้อมูลเพิ่มตามขั้นตอนต่อไปนี้
1.จัดสรรหน่วยความจำสำหรับโหนดใหม่พร้อมกับข้อมูล
2.กำหนดตัวชี้ให้กับลิงก์ฟิลด์ของโหนดใหม่
3.นำตัวชี้ที่อยู่ก่อนหน้าโหนดใหม่ชี้มายังโหนดใหม่
จาก 3 ขั้นตอนของการแทรกโหนดเข้าไปยังลิสต์ข้างต้น เป็นเพียงการนำเสนอขั้น
ตอน ในรูปแบบอย่างง่ายเพื่อให้เกิดความเข้าใจในเบื้องต้นเท่านั้น แต่ความเป็นจริงยังมีรายละเอียด
อีกหลายอย่าง
ในการแทรกโหนดเข้าไปในลิสต์นั้น ขั้นตอนแรกจำเป็นต้องรู้ตำแหน่งที่อยู่ของโหนด
ก่อนหน้าโหนดใหม่ที่ต้องการจะแทรกเสียก่อน ซึ่งโหนดนี้จะระบุตัวชี้ที่เป็นไปได้ทั้ง 2 สถานะด้วย
กันคือ อาจเป็นแอดเดรสของโหนดถัดไป หรือเป็นค่า null ก็ได้ การที่จำเป็นต้องรู้ตำแหน่งโหนด
ก่อนหน้าก็เพราะว่าโหนดนี้จะมีลิงก์ที่ใช้สำหรับเชื่อมโยงไปยังโหนดถัดไป ซึ่งลิงก์ดังกล่าวนี้จะนำ
มาแทนตำแหน่งลิงก์ของโหนดใหม่เพื่อชี้ไปยังโหนดข้างหลัง (Successor) ที่อยู่ถัดจากโหนด
ใหม่นั่นเอง แต่กรณีดังกล่าวเป็นการประยุกต์ใช้กับการแทรกระหว่างโหนดภายในลิสต์ แต่ถ้าเป็น
กรณีลิงก์ของโหนดก่อนหน้ามีค่าเป็นnull นั่นหมายความว่าเป็นการแทรกโหนดที่ท้ายลิสต์ในการ
แทรกโหนดเพิ่มเข้าไปในลิสต์สามารถกระทำได้ 4 รูปแบบด้วยกันคือ
1. การแทรกโหนดในลิสต์ว่าง (Insert into Empty List)
กรณีนี้เป็นการแทรกโหนดเพิ่มเข้าไปในลิสต์ในขณะที่ลิสต์ว่างเปล่าหรือไม่มีข้อมูล
ใดๆ อยู่นั่นหมายถึงเป็นการแทรกสมาชิกตัวแรกเข้าไป ซึ่งขณะนั้นเฮดพอยน์เตอร์จะมีค่าเป็น
null เนื่องจากเป็นลิสต์ว่าง หลังจากนั้นมีลิสต์ใหม่ที่ต้องการแทรกเพิ่มเข้ามา (pNew)
(a) Before add
(b) After add
รูป แสดงการแทรกโหนดเมื่อลิสต์ภายในว่าง
2 การแทรกโหนดที่ตำแหน่งแรก (Insert at Beginning)
เป็นการแทรกโหนดเข้าไปไว้ในตำแหน่งโหนดแรก ซึ่งทำให้โหนดที่เคยอยู่ลำดับแรก
เดิมต้องมาต่อท้ายโหนดใหม่ที่แทรกเข้าไป ขั้นตอนแรกของการแทรกข้อมูลที่โหนดแรกของลิสต์
จะต้องทราบถึงตัวชี้ของตัว Predecessor ก่อน ซึ่งหากไม่มี หรือมีค่าเป็น nullก็หมายความว่า
เป็นการแทรกโหนดแรกในลิสต์ว่างเปล่า
การแทรกโหนดที่ลำดับแรกจะมีวิธีการคือ ให้นำตัวชี้ของโหนดใหม่ชี้ไปยังโหนดแรก
ของ ลิสต์หลังจากนั้นก็ทำการกำหนดเฮดพอยน์เตอร์ชี้ไปยังโหนดใหม่ ซึ่งเราจะรู้ตำแหน่งแอด
เดรสของโหนดใหม่อยู่แล้วหลังจากที่ได้สร้างขึ้นมา
(a) Before add
(b) After add
รูป แสดงการแทรกโหนดไว้ที่ตำแหน่งแรกของลิสต์
3 การแทรกโหนดที่กึ่งกลางของลิสต์ (Insert in Middle)
การเพิ่มโหนดในส่วนกลางของลิสต์หรือการแทรกระหว่างโหนด ในขั้นตอนแรก ต้องรู้ตำ
แหน่งโหนดก่อนหน้าเสียก่อน ซึ่งก็คือตัว Predecessor (pPre) ความสำคัญของโหนด
Predecessor ก็คือจะมีลิงก์ที่ใช้เชื่อมโยงไปยังโหนดถัดไป
ในการแทรกโหนดระหว่างสองโหนด ตัวชี้หรือลิงก์ฟิลด์ของโหนดใหม่จะชี้ไปยังโหนด
Successor ในขณะที่ตัวชี้ pPre ก็จะชี้ไปยังโหนดใหม่
(a) Before add
(b) After add
รูป แสดงแทรกโหนดที่กึ่งกลางของลิสต์
4 การแทรกโหนดที่ท้ายลิสต์ (Insert at End)
เมื่อมีการเพิ่มโหนดที่ส่วนท้ายของลิสต์ เราต้องการเพียงแค่ตัวชี้ของ Predecessor
เพื่อชี้ไปยังโหนดใหม่เท่านั้น ซึ่งในที่นี้จะไม่มีโหนด Successor เนื่องจากเป็นการแทรกที่ท้าย
ลิสต์ดังนั้นลิงก์ฟิลด์ของโหนดใหม่จึงถูกกำหนดให้เป็นค่า null
อย่างไรก็ตาม ก็ยังมีตรรกะพิเศษในอีกรูปแบบหนึ่งเพื่อใช้กับอัลกอริทึมการแทรกโหนด
ที่ท้ายลิสต์ ซึ่งจัดเป็นข้อดีข้อหนึ่งของโครงสร้างลิงก์ลิสต์ โดยเราทราบอยู่แล้วว่าโหนดสุดท้ายของ
ลิสต์จะมีตัวชี้ที่เชื่อมโยงไปที่ null นั่นหมายถึงโหนดสุดท้ายที่ไม่มีโหนดตัวถัดไปแล้วนั่นเองแต่ถ้า
หากเรามีความต้องการใช้พอยน์เตอร์มากกว่าที่จะใช้ค่าคงที่ของ null เป็นตัวกำหนด
a) Before add
(b) After add
รูป การแทรกโหนดไว้ที่ส่วนท้ายของลิสต์
จากรายละเอียดการแทรกโหนดเข้าไปในลิสต์ในรูปแบบต่างๆไม่ว่าจะเป็นการแทรก
โหนดในขณะที่ลิสต์ว่าง การแทรกโหนดที่ตำแหน่งแรกของลิสต์ กึ่งกลางหรือท้ายลิสต์ก็ตามและ
ต่อ ไปนี้ขอกล่าวถึงอัลกอลิทึมที่ใช้สำหรับการแทรกโหนดเข้าไปในลิสต์ โดยจะมีพอยน์เตอร์ชี้ไป
ยัง ลิสต์ตัว Predecessor และข้อมูลที่ต้องการแทรก ซึ่งจะต้องมีการจัดสรรหน่วยความจำสำหรับ
โหนดใหม่ และทำการปรับเปลี่ยนพอยน์เตอร์เชื่อมโยงที่เหมาะสมต่อไป เมื่ออัลกอริทึมนี้ทำงานจน
สัมฤทธิ์ผล จะรีเทิร์นค่าตรรกะเป็นจริงเมื่อแทรกโหนดใหม่ ซึ่งก็คือข้อผิดพลาดในสถานะ
Overflow นั่นเอง
การลบโหนด (Delete Node)
อัลกอริทึมการลบโหนดออกจากลิสต์นอกจากจะนำโหนดที่ถูกลบส่งคืนแก่หน่วยความ
จำระบบเพื่อจะได้นำไปใช้งานอื่นต่อไปแล้ว ยังต้องมีการปรับเปลี่ยนตัวชี้ใหม่ด้วย สำหรับขั้นตอน
แรกของการลบโหนด จะต้องค้นหาตำแหน่งของโหนดที่ต้องลบ (pLoc) ภายในลิสต์ให้พบก่อน
เมื่อพบตำแหน่งโหนดที่ต้องการลบภายในลิสต์แล้ว จะทำให้ทราบตำแหน่งแอดเดรสของ
Predecessor(pPre) ซึ่งก็คือโหนดที่อยู่ก่อนหน้าโหนดที่ต้องการลบนั่นเอง หลังจากนั้นก็จะ
กำหนดลิงก์ฟิลด์ของโหนด Predecessorชี้ไปยังโหนด Successor ซึ่งเป็นโหนดที่อยู่ด้านหลัง
โหนดที่ถูกลบ จากนั้นก็จะนำพื้นที่หน่วยความจำที่เก็บโหนดที่ถูกลบไปนั้นส่งคืนแก่ระบบเพื่อนำ
ไป ใช้งานอื่นต่อไป
1.การลบโหนดที่ตำแหน่งแรก (Delete First Node)
เมื่อรู้ตำแหน่งแรกแล้ว (pLoc) ต่อมาก็ให้ทำการรีเซตเฮดพอยน์เตอร์เพื่อชี้ไปยัง
โหนดSuccessor ที่อยู่ถัดไปจากโหนดแรกที่ต้องการลบ จากนั้นก็จะนำโหนดที่ถูกลบส่งคืนแก่
ระบบ และเนื่องจากในที่เป็นการลบโหนดแรกออกจากลิสต์ ตัวโหนด Predecessor (pPre) ที่อยู่
ก่อนหน้านั้นจึงไม่มีดังนั้นโหนด pPre จึงถูกกำหนดค่าให้เป็น null ซึ่งก็หมายถึงเป็นการลบโหนด
ที่ตำแหน่งแรกนั่นเอง
2 การลบโหนดโดยทั่วไป (General Delete Case)
การลบโหนดออกจากลิสต์ในกรณีทั่วไป ซึ่งประกอบด้วยการลบโหนดที่อยู่กึ่งกลางภาย
ในลิสต์ และการลบโหนดที่ท้ายลิสต์ ทั้งสองกรณีต่างก็สามารถใช้ตรรกะเดียวกันในการใช้งานใน
การลบโหนดลบโหนดออกจากลิสต์ ไม่ว่าจะเป็นโหนดที่อยู่กึ่งกลางลิสต์หรือที่ท้ายลิสต์ก็ตามขั้น
ตอน แรกจำเป็นต้องรู้ตำแหน่งโหนดที่ลบเสียก่อน จากนั้นก็กำหนดตัวชี้ของโหนด Predecessor
ให้ชี้ไปยังโหนดSuccessor ที่อยู่ถัดจากโหนดในตำแหน่ง pLoc หรือโหนดที่ต้องการลบนั่นเอง
โดยแสดงขั้นตอนการกระทำได้ดังรูป
(a) Before delete
(b) After delete
รูป การลบโหนดออกจากลิสต์โดยทั่วไป
ส่วนกรณีการลบโหนดที่ท้ายลิสต์ออกเมื่อโหนดท้ายลิสต์ได้ถูกลบออกไปแล้ว
ค่าของ null pointer จะถูกย้ายไปเก็บไว้ในตำแหน่งฟิลด์ของโหนด Predecessorดังนั้น
โหนดที่เคยอยู่ก่อนหน้าก็จะกลายเป็นโหนดในลำดับสุดท้าย ส่วนโหนดท้ายลิสต์ที่ถูกลบไป
ก็จะส่งคืนกลับไปยังระบบ
การค้นหาข้อมูลภายในลิสต์ (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 ภายในโมดูลจะมีเพียง
ประโยคคำสั่งเดียวเท่านั้น แต่ก็เป็นฟังก์ชันที่มีความสำคัญทีเดียว เพราะว่าจะแจ้งจำนวนสมาชิก
หรือจำนวนอิลิเมนต์ที่มีอยู่ในขณะนั้นให้กับโมดูลที่เรียก แทนที่จะต้องท่องเข้าไปในลิสต์เพื่อนับ
สมาชิกแต่ละอิลิเมนต์แทน
