วันจันทร์ที่ 10 เมษายน พ.ศ. 2560
บทที่ 3: Linked-List
โครงสร้างข้อมูล link
- เป็นการจัดเก็บชุดข้อมูลเชื่อมโยงต่อเนื่องกันไปตามลำดับ โครงสร้างข้อมูลแบบลิงค์ลิสต์จะประกอบไปด้วยส่วนที่เรียกว่า สมาชิก ( Node) ส่วน เก็บข้อมูล (Data) และตำแหน่งของสมาชิกตัวถัดไป(Link)
คุณสมบัติของลิงค์
ลิงค์ลิสต์จะใช้เฮดพอยน์เตอร์
(pHead)เป็นตัวชี้ไปยังโหนดแรกของลิสต์
ในขณะที่พอยน์เตอร์หรือลิงค์ของแต่ละโหนดก็จะเชื่อมโยงลิงค์ไปยังโหนดตัวถัดไปโดยโหนดตัวสุดท้ายที่ไม่มีลิงค์ให้เชื่อมต่อจะถูกกำหนดค่าให้เป็น null
ซึ่งในที่นี้ใช้สัญลักษณ์ แทน
•โหนดของข้อข้อมูลจะประกอบไปด้วย Data และ Link โดย
–Data คือข้อมูลหรือสารสนเทศที่สามารถนำไปใช้ประโยชน์–Link คือตัวชี้หรือพอยน์เตอร์ที่ใช้สำหรับเชื่อมโยงไปยังโหนดถัดไป
•โหนดของข้อข้อมูลจะประกอบไปด้วย Data และ Link โดย
–Data คือข้อมูลหรือสารสนเทศที่สามารถนำไปใช้ประโยชน์–Link คือตัวชี้หรือพอยน์เตอร์ที่ใช้สำหรับเชื่อมโยงไปยังโหนดถัดไป
• ไม่มีความสัมพันธ์ทางการข้อมูลที่จัดเก็บภายในหน่วยความจำไม่จำเป็นต้องอยู่ติดกัน
- ไม่จำเป็นต้องระบุจำนวนของข้อมูลที่จัดเก็บ เนื่องจากสามารถขอหน่วยความจำใหม่ได้ เมื่อต้องการจัดเก็บข้อมูลเพิ่ม จำทำให้ไม่ต้องระบุจำนวนข้อมูลที่จะจัดเก็บไว้ตั้งแต่ตอนกำหนดตัวแปร
- ขนาดของหน่วยความจำที่ใช้เท่ากับข้อมูลที่จัดเก็บ คือ หน่วยความจำที่ใช้งานจะพอดีกับข้อมูลเพราะไม่ได้ระบุขนาดไว้ก่อนจำทำให้ไม่มีหน่วยความจำที่จองไว้เหลือเหมือนการใช้อาร์เรย์
- กรณีที่เฮดพอยน์เตอร์ไม่มีตัวชี้หรือไม่มีสมาชิก เฮดพอยน์เตอร์จะถูกกำหนดค่าเป็น null ซึ่งหมายถึงลิสต์ว่างนั่นเองภาพระหว่างโหนด
ข้อดีของลิงค์ลิสต์
•เป็นโครงสร้างที่ง่ายต่อการเพิ่มหรือลบข้อมูล
•ไม่จำเป็นต้องขยับอิลิเมนต์ของลิสต์ไปข้างหน้าเพื่อให้เกิดพื้นที่ว่าง ในกรณีที่มีการลบอิลิเมนต์ตรงส่วนหน้าหรือส่วนกลางของลิสต์เช่นเดียวกับอาร์เรย์
•ใช้พื้นที่หน่วยความจำได้เต็มประสิทธิภาพ
เนื่องจากหากข้อมูลภายในลิสต์มีน้อยก็ใช้น้อย
ซึ่งผิดกับอาร์เรย์ที่ต้องสูญเสียพื้นที่ไปในทันที
ถึงแม้จะไม่มีข้อมูลภายในลิสต์ก็ตาม
การเข้าถึงข้อมูลภายใน
การเข้าถึงข้อมูลภายในโครงสร้างลิงค์ลิสต์
จะต้องอาศัยพอยน์เตอร์เป็นตัวเข้าไปในโครงสร้าง
สมมติให้พอยน์เตอร์ดังกล่าว คือ PTR และทำหน้าที่ชี้ตำแหน่งแอดเดรสของโหนดในโครงสร้าง
เมื่อต้องการไปยังโหนดถัดไปก็ให้ทำการเลื่อนตำแหน่งของพอยน์เตอร์ โดยตำแหน่งของโหนดถัดไปได้จากส่วนของ LINK ในโหนดปัจจุบัน
การเข้าถึงในโครงสร้างเรียกว่า การทำ Traversing มีขั้นตอนดังต่อไปนี้
กำหนดให้ DATA เป็นโครงสร้างข้อมูลลิงค์ลิสต์ และพอยน์เตอร์ PTR
ทำหน้าที่ชี้โหนดที่กำลังดำเนินการ Process
อยู่ในขณะนั้น (Current Node)
1. กำหนดค่าเริ่มต้นให้กับพอยน์เตอร์ PTR.
2. การวนรอบดำเนินการ Process ข้อมูล
3. Apply Process to DATA [PTR]
4. เปลี่ยนค่าพอยน์เตอร์ PTR ให้ชี้โหนดถัดไป
5. เสร็จสิ้นขั้นตอน
ขั้นตอนการเพิ่มข้อมูลที่ตำแหน่งเริ่มต้นของโครงสร้าง
1. ตรวจสอบ OVERFLOW ถ้าโหนดใหม่มีค่าเป็น NULL แสดงว่า OVERFLOW
2. กำหนด PTR ให้ชี้ไปที่โหนดของ FREE LIST
3.ใส่ข้อมูลใหม่ลงไปในโหนดใหม่
4.ให้โหนดใหม่ชี้ไปยังโหนดเริ่มต้นเดิมและเปลี่ยนตำแหน่งเริ่มต้นให้ชี้ไปยังโหนดใหม่
ขั้นตอนการเพิ่มข้อมูลเป็นโหนดสุดท้ายของโครงสร้าง
1. ตรวจสอบ OVERFLOW ถ้าโหนดใหม่มีค่าเป็น NULL แสดงว่า OVERFLOW
2. กำหนด PTR (ที่อยู่ตำแหน่งสุดท้าย)
ให้ชี้ไปที่โหนดของ FREE LIST
3. ใส่ข้อมูลใหม่ลงไปในโหนดใหม่
4. กำหนด PTR ของโหนดใหม่มีค่าเป็นน NULL
การลบข้อมูลจากโครงสร้าง
การลบข้อมูลจากโครงสร้าง
หมายถึง การดึงเอาโหนดที่ต้องการลบออกจากลิงค์ลิสต์ชุดเดิม ดังนั้น การเปลี่ยนแปลงที่เกิดขึ้นคือ การเปลี่ยนค่าพอยน์เตอร์และเมื่อทำการลบข้อมูลออกจากโครงสร้างแล้วจะต้องคืนโหนดที่ถูกลบให้กับ Storage Pool
เพื่อที่จะได้สามารถนำหน่วยความจำส่วนนั้นไปใช้งานต่อไป
การลบข้อมูลออกจากโครงสร้างลิงค์ลิสต์
เกิดขึ้นได้หลายลักษณะสรุปได้ดังนี้
1. การลบโหนดแรก
2. การลบโหนดที่อยู่หลังโหนดที่กำหนด
3. การลบโหนดสุดท้าย
ขั้นตอนการลบโหนด
1. เก็บค่าตำแหน่งและค่าของ Pointer ของโหนดที่ต้องการล
2. กำหนดค่าของ Pointer ของโหนดที่ต้องการลบ ไปยังโหนดก่อนหน้านั้น
3. กำหนดตำแหน่งของโหนดที่ต้องการลบคืนกลับไปยัง Storage Pool
โครงสร้างข้อมูลลิงค์ลิสต์คู่ (Doubly Linked List)
โครงสร้างข้อมูลลิงค์ลิสต์คู่ (Doubly Linked List) เป็นโครงสร้างที่แต่ละโหนดข้อมูลสามารถชี้ตำแหน่งโหนดข้อมูลถัดไปได้ 2 ทิศทาง (มีพอยน์เตอร์ชี้ตำแหน่งอยู่สองทิศทาง) โดยมีพอยน์เตอร์อยู่ 2 ตัว คือ พอยน์เตอร์ LLINK ทำหน้าที่ชี้ไปยังโหนดด้านซ้ายของโหนดข้อมูลนั้น ๆ และ พอยน์เตอร์ RLINK ทำหน้าที่ชี้ไปยังโหนดด้านขวาของโหนดข้อมูลนั้น
ขั้นตอนการเพิ่มโหนดข้อมูล
1.
ตรวจสอบว่า โหนด n เป็นโหนดว่างหรือไม่ (ถ้าโหนด n มีค่าเป็น NULL แสดงว่าเป็นโหนดว่าง)
2.
ถ้าโหนด n ไม่เป็นโหนดว่าง ให้กำหนดพอยน์เตอร์ของ n
n
-> r = p -> r
n
-> l = q -> l
3. กำหนดพอยน์เตอร์
p -> r ให้เป็นตำแหน่งของโหนด n
4. กำหนดพอยน์เตอร์
q -> l ให้เป็นตำแหน่งของโหนด n
5. ใส่ข้อมูลลงไปในโหนด n
ขั้นตอนการลบโหนด
1. ตรวจสอบว่ามีข้อมูลหรือไม่ (ถ้าโหนด r และ l มีค่าเป็น start แสดงว่าไม่มีข้อมูล)
2. ถ้ามีข้อมูล ให้กำหนดพอยน์เตอร์ของ p และ q
p
-> r = d -> r
q
-> l = d -> l
3. คืนโหนดที่ลบให้กับระบบ
