3.3 อัลกอริทึมของลิงก์ลิสต์ (Linked List Algorithm)
Embedded Files
ในที่นี้จะมีฟังก์ชันการดำเนินงานบนลิงก์ลิสต์ 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 รูปแบบด้วยกันคือ
(a) Before add
(b) After add
รูปที่ 3.4 แสดงการแทรกโหนดเมื่อลิสต์ภายในว่าง
2.1 การแทรกโหนดในลิสต์ว่าง (Insert into Empty List)
กรณีนี้เป็นการแทรกโหนดเพิ่มเข้าไปในลิสต์ในขณะที่ลิสต์ว่างเปล่าหรือไม่มีข้อมูลใดๆ อยู่นั่นหมายถึงเป็นการแทรกสมาชิกตัวแรกเข้าไป ซึ่งขณะนั้นเฮดพอยน์เตอร์จะมีค่าเป็น null เนื่องจากเป็นลิสต์ว่าง หลังจากนั้นมีลิสต์ใหม่ที่ต้องการแทรกเพิ่มเข้ามา (pNew)
(a) Before add
(b) After add
รูปที่ 3.5 แสดงการแทรกโหนดไว้ที่ตำแหน่งแรกของลิสต์
2.2 การแทรกโหนดที่ตำแหน่งแรก (Insert at Beginning)
เป็นการแทรกโหนดเข้าไปไว้ในตำแหน่งโหนดแรก ซึ่งทำให้โหนดที่เคยอยู่ลำดับแรก เดิมต้องมาต่อท้ายโหนดใหม่ที่แทรกเข้าไป ขั้นตอนแรกของการแทรกข้อมูลที่โหนดแรกของลิสต์จะต้องทราบถึงตัวชี้ของตัว Predecessor ก่อน ซึ่งหากไม่มี หรือมีค่าเป็น nullก็หมายความว่าเป็นการแทรกโหนดแรกในลิสต์ว่างเปล่า
การแทรกโหนดที่ลำดับแรกจะมีวิธีการคือ ให้นำตัวชี้ของโหนดใหม่ชี้ไปยังโหนดแรกของ ลิสต์หลังจากนั้นก็ทำการกำหนดเฮดพอยน์เตอร์ชี้ไปยังโหนดใหม่ ซึ่งเราจะรู้ตำแหน่งแอดเดรสของโหนดใหม่อยู่แล้วหลังจากที่ได้สร้างขึ้นมา
(a) Before add
(b) After add
รูปที่ 3.6 แสดงแทรกโหนดที่กึ่งกลางของลิสต์
2.3 การแทรกโหนดที่กึ่งกลางของลิสต์ (Insert in Middle)
การเพิ่มโหนดในส่วนกลางของลิสต์หรือการแทรกระหว่างโหนด ในขั้นตอนแรก ต้องรู้ตำแหน่งโหนดก่อนหน้าเสียก่อน ซึ่งก็คือตัว Predecessor (pPre) ความสำคัญของโหนด Predecessor ก็คือจะมีลิงก์ที่ใช้เชื่อมโยงไปยังโหนดถัดไปในการแทรกโหนดระหว่างสองโหนด ตัวชี้หรือลิงก์ฟิลด์ของโหนดใหม่จะชี้ไปยังโหนด Successor ในขณะที่ตัวชี้ pPre ก็จะชี้ไปยังโหนดใหม่
(a) Before add
(b) After add
รูปที่ 3.7 การแทรกโหนดไว้ที่ส่วนท้ายของลิสต์
2.4 การแทรกโหนดที่ท้ายลิสต์ (Insert at End)
เมื่อมีการเพิ่มโหนดที่ส่วนท้ายของลิสต์ เราต้องการเพียงแค่ตัวชี้ของ Predecessor เพื่อชี้ไปยังโหนดใหม่เท่านั้น ซึ่งในที่นี้จะไม่มีโหนด Successor เนื่องจากเป็นการแทรกที่ท้ายลิสต์ ดังนั้นลิงก์ฟิลด์ของโหนดใหม่จึงถูกกำหนดให้เป็นค่า null
อย่างไรก็ตาม ก็ยังมีตรรกะพิเศษในอีกรูปแบบหนึ่งเพื่อใช้กับอัลกอริทึมการแทรกโหนดที่ท้ายลิสต์ ซึ่งจัดเป็นข้อดีข้อหนึ่งของโครงสร้างลิงก์ลิสต์ โดยเราทราบอยู่แล้วว่าโหนดสุดท้ายของลิสต์จะมีตัวชี้ที่เชื่อมโยงไปที่ null นั่นหมายถึงโหนดสุดท้ายที่ไม่มีโหนดตัวถัดไปแล้วนั่นเองแต่ถ้าหากเรามีความต้องการใช้พอยน์เตอร์มากกว่าที่จะใช้ค่าคงที่ของ null เป็นตัวกำหนด
จากรายละเอียดการแทรกโหนดเข้าไปในลิสต์ในรูปแบบต่างๆไม่ว่าจะเป็นการแทรกโหนดในขณะที่ลิสต์ว่าง การแทรกโหนดที่ตำแหน่งแรกของลิสต์ กึ่งกลางหรือท้ายลิสต์ก็ตามและต่อไปนี้ขอกล่าวถึงอัลกอลิทึมที่ใช้สำหรับการแทรกโหนดเข้าไปในลิสต์ โดยจะมีพอยน์เตอร์ชี้ไปยังลิสต์ตัว Predecessor และข้อมูลที่ต้องการแทรก ซึ่งจะต้องมีการจัดสรรหน่วยความจำสำหรับโหนดใหม่และทำการปรับเปลี่ยนพอยน์เตอร์เชื่อมโยงที่เหมาะสมต่อไป เมื่ออัลกอริทึมนี้ทำงานจนสัมฤทธิ์ผลจะรีเทิร์นค่าตรรกะเป็นจริงเมื่อแทรกโหนดใหม่ ซึ่งก็คือข้อผิดพลาดในสถานะ Overflow นั่นเอง
ที่มา : https://www.youtube.com/watch?v=JOPb7Xhtt-w&t=161s
Page updated
Report abuse