Linklist

ลิงค์ลิสต์ linklist

1. รูปแบบของลิงค์ลิสต์

เป็นการจัดเก็บชุดข้อมูลเชื่อมโยงต่อเนื่องกันไปตามลำดับ โครงสร้างข้อมูลแบบลิงค์ลิสต์จะประกอบไปด้วย

ส่วนที่เรียกว่า สมาชิก ( Node) ส่วน เก็บข้อมูล (Data) และตำแหน่งของสมาชิกตัวถัดไป (Link)

•ลิงค์ลิสต์จะใช้เฮดพอยน์เตอร์ (pHead)เป็นตัวชี้ไปยังโหนดแรกของลิสต์ ในขณะที่พอยน์เตอร์หรือลิงค์ของแต่ละโหนดก็จะเชื่อมโยงลิงค์ไปยังโหนดตัวถัดไปโดยโหนดตัวสุดท้ายที่ไม่มีลิงค์ให้เชื่อมต่อจะถูกกำหนดค่าให้เป็น null ซึ่งในที่นี้ใช้สัญลักษณ์   X    แทน

•โหนดของข้อข้อมูลจะประกอบไปด้วย Data และ Link โดย

–Data คือข้อมูลหรือสารสนเทศที่สามารถนำไปใช้ประโยชน์

–Link คือตัวชี้หรือพอยน์เตอร์ที่ใช้สำหรับเชื่อมโยงไปยังโหนดถัดไป

•ไม่มีความสัมพันธ์ทางการภาพระหว่างโหนด

กรณีที่เฮดพอยน์เตอร์ไม่มีตัวชี้หรือไม่มีสมาชิก เฮดพอยน์เตอร์จะถูกกำหนดค่าเป็น null ซึ่งหมายถึงลิสต์ว่างนั่นเอง

2. ข้อดีของลิงค์ลิสต์
•เป็นโครงสร้างที่ง่ายต่อการเพิ่มหรือลบข้อมูล
•ไม่จำเป็นต้องขยับอิลิเมนต์ของลิสต์ไปข้างหน้าเพื่อให้เกิดพื้นที่ว่าง ในกรณีที่มีการลบอิลิ
เมนต์ตรงส่วนหน้าหรือส่วนกลางของลิสต์เช่นเดียวกับอาร์เรย์
•ใช้พื้นที่หน่วยความจำได้เต็มประสิทธิภาพ เนื่องจากหากข้อมูลภายในลิสต์มีน้อยก็ใช้น้อย
 ซึ่งผิดกับอาร์เรย์ที่ต้องสูญเสียพื้นที่ไปในทันที ถึงแม้จะไม่มีข้อมูลภายในลิสต์ก็ตาม

3.การเพิ่มข้อมูลในโครงสร้าง

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

      การเพิ่มข้อมูลในโครงสร้างข้อมูลลิงค์ลิสต์ อาจเกิดในลักษณะที่ต่างกัน ซึ่งสรุปได้เป็น 3 ลักษณะ  คือ

  1. การเพิ่มข้อมูลที่จุดเริ่มต้นของโครงสร้าง
     เป็นการเพิ่มโหนดของข้อมูลไปยังตำแหน่งแรกของโครงสร้างลิงค์ลิสต์ โดยการเปลี่ยนค่าเริ่มต้นให้ชี้ไปยังตำแหน่งของโหนดใหม่ (NEW Node) ที่สร้างขึ้น และให้ Pointer ของโหนดใหม่ชี้ไปยังตำแหน่งเริ่มต้นเดิมแทน

  2. การเพิ่มข้อมูลต่อจากโหนดที่กำหนด
       เป็นการแทรกโหนดข้อมูลใหม่เข้าไประหว่างโหนดข้อมูล 2 โหนด โดยการเปลี่ยน Pionter ที่ชี้โหนดเก่าให้ชี้ไปยังตำแหน่งของโหนดใหม่ และ ให้ Poinnter ของโหนดใหม่ขี้ไปยังตำแหน่งเดิมแทน

  3. การเพิ่มข้อมูลที่จุดสุดท้ายของโครงสร้าง

       เป็นการนำโหนดข้อมูลใหม่มาต่อยังตำแหน่งท้ายสุดของโครงสร้าง (Pointer ของโหนดสุดท้ายมีค่าเป็น  NULL)  โดยการกำหนดให้ Pointer ของโหนดข้อมูลสุดท้าย ชี้ไปยังโหนดใหม่ และให้ Pointer ของ โหนดใหม่มีค่าเป็น NULL แทน

4. การลบข้อมูลจากโครงสร้าง

       การลบข้อมูลจากโครงสร้าง หมายถึง การดึงเอาโหนดที่ต้องการลบออกจากลิงค์ลิสต์ชุดเดิม   ดังนั้น การเปลี่ยนแปลงที่เกิดขึ้นคือ  การเปลี่ยนค่าพอยน์เตอร์และเมื่อทำการลบข้อมูลออกจากโครงสร้างแล้วจะต้องคืนโหนดที่ถูกลบให้กับ Storage Pool เพื่อที่จะได้สามารถนำหน่วยความจำส่วนนั้นไปใช้งานต่อไป

       การลบข้อมูลออกจากโครงสร้างลิงค์ลิสต์ เกิดขึ้นได้หลายลักษณะสรุปได้ดังนี้

  1. การลบโหนดแรก

  2. การลบโหนดที่อยู่หลังโหนดที่กำหนด

  3. การลบโหนดสุดท้าย

4.1 ขั้นตอนกานลบโหนดมีดังนี้

  1. เก็บค่าตำแหน่งและค่าของ Pointer ของโหนดที่ต้องการล

  2. กำหนดค่าของ Pointer ของโหนดที่ต้องการลบ ไปยังโหนดก่อนหน้านั้น

  3. กำหนดตำแหน่งของโหนดที่ต้องการลบคืนกลับไปยัง Storage Pool