krukanchana - การลบโหนด (Delete Node)

3. การลบโหนด (Delete Node)

อัลกอริทึมการลบโหนดออกจากลิสต์นอกจากจะนำโหนดที่ถูกลบส่งคืนแก่หน่วยความจำระบบเพื่อจะได้นำไปใช้งานอื่นต่อไปแล้ว ยังต้องมีการปรับเปลี่ยนตัวชี้ใหม่ด้วย สำหรับขั้นตอนแรกของการลบโหนด จะต้องค้นหาตำแหน่งของโหนดที่ต้องลบ (pLoc) ภายในลิสต์ให้พบก่อน เมื่อพบตำแหน่งโหนดที่ต้องการลบภายในลิสต์แล้ว จะทำให้ทราบตำแหน่งแอดเดรสของ Predecessor (pPre) ซึ่งก็คือโหนดที่อยู่ก่อนหน้าโหนดที่ต้องการลบนั่นเอง หลังจากนั้นก็จะกำหนดลิงก์ฟิลด์ของโหนด Predecessorชี้ไปยังโหนด Successor ซึ่งเป็นโหนดที่อยู่ด้านหลังโหนดที่ถูกลบ จากนั้นก็จะนำพื้นที่หน่วยความจำที่เก็บโหนดที่ถูกลบไปนั้นส่งคืนแก่ระบบเพื่อนำไปใช้งานอื่นต่อไป

3.1 การลบโหนดที่ตำแหน่งแรก (Delete First Node)

เมื่อรู้ตำแหน่งแรกแล้ว (pLoc) ต่อมาก็ให้ทำการรีเซตเฮดพอยน์เตอร์เพื่อชี้ไปยังโหนดSuccessor ที่อยู่ถัดไปจากโหนดแรกที่ต้องการลบ จากนั้นก็จะนำโหนดที่ถูกลบส่งคืนแก่ระบบ และเนื่องจากในที่เป็นการลบโหนดแรกออกจากลิสต์ ตัวโหนด Predecessor (pPre) ที่อยู่ก่อนหน้านั้น จึงไม่มีดังนั้นโหนด pPre จึงถูกกำหนดค่าให้เป็น null ซึ่งก็หมายถึงเป็นการลบโหนดที่ตำแหน่งแรกนั่นเอง

(a) Before delete

3.2 การลบโหนดโดยทั่วไป (General Delete Case)

การลบโหนดออกจากลิสต์ในกรณีทั่วไป ซึ่งประกอบด้วยการลบโหนดที่อยู่กึ่งกลางภายในลิสต์ และการลบโหนดที่ท้ายลิสต์ ทั้งสองกรณีต่างก็สามารถใช้ตรรกะเดียวกันในการใช้งานในการลบโหนดลบโหนดออกจากลิสต์ ไม่ว่าจะเป็นโหนดที่อยู่กึ่งกลางลิสต์หรือที่ท้ายลิสต์ก็ตามขั้นตอนแรกจำเป็นต้องรู้ตำแหน่งโหนดที่ลบเสียก่อน จากนั้นก็กำหนดตัวชี้ของโหนด Predecessor ให้ชี้ไปยังโหนดSuccessor ที่อยู่ถัดจากโหนดในตำแหน่ง pLoc หรือโหนดที่ต้องการลบนั่นเองโดยแสดงขั้นตอนการกระทำได้ดังรูป

ส่วนกรณีการลบโหนดที่ท้ายลิสต์ออกเมื่อโหนดท้ายลิสต์ได้ถูกลบออกไปแล้วค่าของ null pointer จะถูกย้ายไปเก็บไว้ในตำแหน่งฟิลด์ของโหนด Predecessor ดังนั้นโหนดที่เคยอยู่ก่อนหน้าก็จะกลายเป็นโหนดในลำดับสุดท้าย ส่วนโหนดท้ายลิสต์ที่ถูกลบไปก็จะส่งคืนกลับไปยังระบบ

Page updated

Report abuse