ลิงลิสต์ (Linked List)
ลิงค์ลิสต์ (Linked List) เป็นโครงสร้างข้อมูลที่ถูกประยุกต์ใช้ในการคำนวณและประมวลผลต่างๆมากมาย การเก็บข้อมูลลิงค์ลิสต์จะเป็นแบบลำดับเช่นเดียวกันกับสแตคและคิว เพียงแต่งลำดับในข้อมูลในลิงค์ลิสต์อาจจะตรงหรือไม่ตรงกับลำดับของข้อมุลที่เก็บไว้บนพื้นที่เก็บข้อมูลก็ได้
ในส่วนของข้อมูลจะมีการจัดเก็บสารสนเทศที่สามารถนำไปใช้ในการประมวลผลตามที่ต้อง
การต่อไป
ในส่วนของลิสต์นั้น จะใช้สำหรับเชื่อมโยงไปยังข้อมูลโดยเริ่มต้นจากเฮดพอยน์เตอร์ที่ชี้ไป
ยังตำแหน่งโหนดแรกของลิสต์ จากนั้นลิงก์ในแต่ละโหนดก็จะเชื่อมโยงไปยังโหนดตัวถัดไปเรื่อยๆ
ส่วนชื่อของลิสต์จะเป็นชื่อเดียวกันกับชื่อตัวแปรพอยน์เตอร์โดยลิงก์ลิสต์อย่างง่ายที่จะกล่าวถึงต่อ
ไปนี้คือ ซิงเกิลลิงก์ลิสต์ (Single-Linked List) ซึ่งจะมีเพียงลิงก์เดียวที่ใช้เชื่อมโยงไปยังโหนด
ตัวถัดไป
เอาไว้บอกว่าในลิสต์นี้มีจำนวนสมาชิกทั้งหมดเท่าไร ซึ่งสามารถเพิ่มหรือลดลงได้ หากมีการแข้ ไขข้อมูลในลิสต์
การสร้างลิสต์ (Create List)
เดรสของโหนดใหม่อยู่แล้วหลังจากที่ได้สร้างขึ้นมา
ข้อมูล (Data)
ในส่วนของข้อมูลจะมีการจัดเก็บสารสนเทศที่สามารถนำไปใช้ในการประมวลผลตามที่ต้อง
การต่อไป
ลิงค์ (Link)
ในส่วนของลิสต์นั้น จะใช้สำหรับเชื่อมโยงไปยังข้อมูลโดยเริ่มต้นจากเฮดพอยน์เตอร์ที่ชี้ไป
ยังตำแหน่งโหนดแรกของลิสต์ จากนั้นลิงก์ในแต่ละโหนดก็จะเชื่อมโยงไปยังโหนดตัวถัดไปเรื่อยๆ
ส่วนชื่อของลิสต์จะเป็นชื่อเดียวกันกับชื่อตัวแปรพอยน์เตอร์โดยลิงก์ลิสต์อย่างง่ายที่จะกล่าวถึงต่อ
ไปนี้คือ ซิงเกิลลิงก์ลิสต์ (Single-Linked List) ซึ่งจะมีเพียงลิงก์เดียวที่ใช้เชื่อมโยงไปยังโหนด
ตัวถัดไป
โครงสร้างข้อมูลแบบลิงก์ลิสต์ (Linked List Data Structure)
สำหรับโครงสร้างข้อมูลลิงก์ลิสต์ ประกอบด้วย
เตอร์ ภายใน โครงสร้างส่วนนี้จะมี Metadata ที่เอาไว้อธิบายข้อมูลภายในลิสต์ ภายในนี้คือฟิลด์ Count เพื่อโครงสร้างโหนดส่วนหัว (Head Node Structure)
ภายในโหนดส่วนหัวจะมีเพียงหนึ่งพอยน์เตอร์ที่จะชี้ไปยังลิสต์ คือ เฮดพอยน์
เอาไว้บอกว่าในลิสต์นี้มีจำนวนสมาชิกทั้งหมดเท่าไร ซึ่งสามารถเพิ่มหรือลดลงได้ หากมีการแข้ ไขข้อมูลในลิสต์
โครงสร้างโหนดข้อมูล (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 ภายในโมดูลจะมีเพียง
ประโยคคำสั่งเดียวเท่านั้น แต่ก็เป็นฟังก์ชันที่มีความสำคัญทีเดียว เพราะว่าจะแจ้งจำนวนสมาชิก
หรือจำนวนอิลิเมนต์ที่มีอยู่ในขณะนั้นให้กับโมดูลที่เรียก แทนที่จะต้องท่องเข้าไปในลิสต์เพื่อนับ
สมาชิกแต่ละอิลิเมนต์แทน
ไม่มีความคิดเห็น:
แสดงความคิดเห็น