โครงสร้างข้อมูล Linklist
จากการทำงานของโครงสร้างข้อมูลอาร์เรย์ (Array Structure) , โครงสร้างข้อมูลสแตก
(Stack Structure) และโครงสร้างข้อมูลคิว (Queue Structure) มีลักษณะการจัดเก็บข้อมูลและการเข้าถึงข้อมูลในโครงสร้างแบบลำดับเป็นพื้นที่ต่อเนื่องกัน
การใช้งานของโครงสร้างถูกจำกัดไว้ไม่สามารถทำการปรับเปลี่ยนหรือแก้ไขขนาดของโครงสร้างได้หรือหากต้องการปรับเปลี่ยนโครงสร้างใหม่ จะทำให้เสียเวลาในการประมวลผล
ซึ่งในการใช้งานโปรแกรมพื้นที่หน่วยความจำ (Memory) เป็นสิ่งจำเป็นมาก
การแก้ไขปัญหาดังกล่าว โดยใช้โครงสร้างข้อมูลแบบอื่น ๆ
เป็นสิ่งจำเป็นที่ต้องพิจารณาและยากมาก
โครงสร้างข้อมูลแบบลิงค์ลิสต์จะประกอบไปด้วยส่วนที่เรียกว่า สมาชิก ( Node) ส่วน
เก็บข้อมูล (Data) และตำแหน่งของสมาชิกตัวถัดไป (Link)
คุณสมบัติของลิงค์ลิสต์
ลิงค์ลิสต์จะใช้เฮดพอยน์เตอร์
(pHead)เป็นตัวชี้ไปยังโหนดแรกของลิสต์
ในขณะที่พอยน์เตอร์หรือลิงค์ของแต่ละโหนดก็จะเชื่อมโยงลิงค์ไปยังโหนดตัวถัดไปโดยโหนดตัวสุดท้ายที่ไม่มีลิงค์ให้เชื่อมต่อจะถูกกำหนดค่าให้เป็น null ซึ่งในที่นี้ใช้สัญลักษณ์ แทน
• โหนดของข้อข้อมูลจะประกอบไปด้วย Data และ Link โดย
- Data คือข้อมูลหรือสารสนเทศที่สามารถนำไปใช้ประโยชน์
- Link คือตัวชี้หรือพอยน์เตอร์ที่ใช้สำหรับเชื่อมโยงไปยังโหนดถัดไป
• ไม่มีความสัมพันธ์ทางการภาพระหว่างโหนด
• ข้อมูลที่จัดเก็บภายในหน่วยความจำไม่จำเป็นต้องอยู่ติดกัน
• ไม่จำเป็นต้องระบุจำนวนของข้อมูลที่จัดเก็บ
เนื่องจากสามารถขอหน่วยความจำใหม่ได้ เมื่อต้องการจัดเก็บข้อมูลเพิ่ม
จำทำให้ไม่ต้องระบุจำนวนข้อมูลที่จะจัดเก็บไว้ตั้งแต่ตอนกำหนดตัวแปร
• ขนาดของหน่วยความจำที่ใช้เท่ากับข้อมูลที่จัดเก็บ
คือ หน่วยความจำที่ใช้งานจะพอดีกับข้อมูลเพราะไม่ได้ระบุขนาดไว้ก่อนจำทำให้ไม่มีหน่วยความจำที่จองไว้เหลือเหมือนการใช้อาร์เรย์
• กรณีที่เฮดพอยน์เตอร์ไม่มีตัวชี้หรือไม่มีสมาชิก
เฮดพอยน์เตอร์จะถูกกำหนดค่าเป็น null ซึ่งหมายถึงลิสต์ว่างนั่นเอง
ไม่มีความสัมพันธ์ทางการภาพระหว่างโหนด
โครงสร้างข้อมูลแบบลิงค์ลิสต์ประกอบด้วยโหนดต่างๆต่อกันโดยแต่ละโหนดมีส่วนที่สำคัญ
2 ส่วนคือ ส่วนที่เก็บข้อมูล (Data) และ ส่วนที่เก็บตัวชี้ (Pointer)
ข้อดีของลิงค์ลิสต์
1. เป็นโครงสร้างที่ง่ายต่อการเพิ่มหรือลบข้อมูล
2. ไม่จำเป็นต้องขยับอิลิเมนต์ของลิสต์ไปข้างหน้าเพื่อให้เกิดพื้นที่ว่าง
ในกรณีที่มีการลบอิลิเมนต์ตรงส่วนหน้าหรือส่วนกลางของลิสต์เช่นเดียวกับอาร์เรย์
3. ใช้พื้นที่หน่วยความจำได้เต็มประสิทธิภาพ
เนื่องจากหากข้อมูลภายในลิสต์มีน้อยก็ใช้น้อย
ซึ่งผิดกับอาร์เรย์ที่ต้องสูญเสียพื้นที่ไปในทันที
ถึงแม้จะไม่มีข้อมูลภายในลิสต์ก็ตาม
การเข้าถึงข้อมูลภายในโครงสร้างลิงค์ลิสต์
การเข้าถึงข้อมูลภายในโครงสร้างลิงค์ลิสต์
จะต้องอาศัยพอยน์เตอร์เป็นตัวเข้าไปในโครงสร้าง สมมติให้พอยน์เตอร์ดังกล่าว คือ PTR
และทำหน้าที่ชี้ตำแหน่งแอดเดรสของโหนดในโครงสร้าง เมื่อต้องการไปยังโหนดถัดไปก็ให้ทำการเลื่อนตำแหน่งของพอยน์เตอร์ โดยตำแหน่งของโหนดถัดไปได้จากส่วนของ LINK ในโหนดปัจจุบัน
การเข้าถึงในโครงสร้างเรียกว่า การทำ Traversing มีขั้นตอนดังต่อไปนี้
กำหนดให้ DATA เป็นโครงสร้างข้อมูลลิงค์ลิสต์ และพอยน์เตอร์
PTR ทำหน้าที่ชี้โหนดที่กำลังดำเนินการ
Process อยู่ในขณะนั้น (Current Node)
1. กำหนดค่าเริ่มต้นให้กับพอยน์เตอร์ PTR.
2. การวนรอบดำเนินการ Process ข้อมูล
3. Apply Process to DATA [PTR]
4. เปลี่ยนค่าพอยน์เตอร์ PTR ให้ชี้โหนดถัดไป
5. เสร็จสิ้นขั้นตอน
การเพิ่มข้อมูลในโครงสร้าง
เมื่อกำหนดโครงสร้างข้อมูลเรียบร้อยแล้ว
ก็สามารถทำการเพิ่มข้อมูลในโครงสร้างได้โดยการขอโหนดว่างจากfreelistและนำมาเชื่อมโยงกับรายการข้อมูลที่มีอยู่เดิมในโครงสร้างตรงตำแหน่งที่ต้องการ
การเพิ่มข้อมูลในโครงสร้างข้อมูลลิงค์ลิสต์
อาจเกิดในลักษณะที่ต่างกัน ซึ่งสรุปได้เป็น 3 ลักษณะ คือ
1. การเพิ่มข้อมูลที่จุดเริ่มต้นของโครงสร้าง
2.
การเพิ่มข้อมูลต่อจากโหนดที่กำหนด
3.
การเพิ่มข้อมูลที่จุดสุดท้ายของโครงสร้าง
การลบข้อมูลจากโครงสร้าง
การลบข้อมูลจากโครงสร้าง
หมายถึง การดึงเอาโหนดที่ต้องการลบออกจากลิงค์ลิสต์ชุดเดิม ดังนั้นการเปลี่ยนแปลงที่เกิดขึ้นคือ การเปลี่ยนค่าพอยน์เตอร์และเมื่อทำการลบข้อมูลออกจากโครงสร้างแล้วจะต้องคืนโหนดที่ถูกลบให้กับ Storage Pool เพื่อที่จะได้สามารถนำหน่วยความจำส่วนนั้นไปใช้งานต่อไป
การลบข้อมูลออกจากโครงสร้างลิงค์ลิสต์
เกิดขึ้นได้หลายลักษณะสรุปได้ดังนี้
1.
การลบโหนดแรก
2.
การลบโหนดที่อยู่หลังโหนดที่กำหนด
3.
การลบโหนดสุดท้าย
ขั้นตอนการลบโหนดมีดังนี้
1.
เก็บค่าตำแหน่งและค่าของ Pointer ของโหนดที่ต้องการล
2.
กำหนดค่าของ Pointer ของโหนดที่ต้องการลบ ไปยังโหนดก่อนหน้านั้น
3.
กำหนดตำแหน่งของโหนดที่ต้องการลบคืนกลับไปยัง Storage Pool
ไม่มีความคิดเห็น:
แสดงความคิดเห็น