Linked-List
Linked-List
Linked-List
หมายถึง จากการทำงานของโครงสร้างข้อมูลอาร์เรย์ (Array Structure) , โครงสร้างข้อมูลสแตก (Stack Structure) และโครงสร้างข้อมูลคิว
(Queue Structure) มีลักษณะการจัดเก็บข้อมูลและการเข้าถึงข้อมูลในโครงสร้างแบบลำดับเป็นพื้นที่ต่อเนื่องกัน การใช้งานของโครงสร้างถูกจำกัดไว้ไม่สามารถทำการปรับเปลี่ยนหรือแก้ไขขนาดของโครงสร้างได้
หรือหากต้องการปรับเปลี่ยนโครงสร้างใหม่ จะทำให้เสียเวลาในการประมวลผล
ปัญหาของตัวแปร
- ตัวแปรแบบ Array มีการจองเนื้อที่ที่อยู่ติดกันตามจำนวนที่ต้องการไว้ก่อน เช่น ถ้าต้องการจัดเก็บข้อมูลจำนวน 10,000 ค่า แต่ละค่าใช้เนื้อที่ 2 byte เนื้อที่ทั้งหมดที่ถูกจองจะเป็น 20,000 byte ซึ่งบางครั้งอาจจะไม่มีเนื้อที่ว่างที่อยู่ติดกันเพียงพอสำหรับเก็บข้อมูล 20,000 byte ทำให้โปรแกรมไม่สามารถทำงานได้
- บางกรณีจองเนื้อที่ไว้สำหรับเก็บข้อมูล 10,000 ค่า เนื่องจากไม่ทราบจำนวนข้อมูลที่ต้องการเก็บ แต่เมื่อใช้งานจริง เก็บข้อมูลเพียง 2,000 ค่า ทำให้เหลือเนื้อที่ที่ยังไม่ได้ใช้ แต่ไม่สามารถนำไปใช้งานอื่นได้
- กรณีจองเนื้อที่ไว้สำหรับเก็บข้อมูล 10,000 ค่า แต่การใช้งานจริงมีข้อมูลที่ต้องเก็บมากกว่า 10,000 ค่า ก็ไม่สามารถเก็บข้อมูลส่วนที่เหลือได้ เนื่องจากจองไว้แค่ไหน ก็ใช้ได้แค่นั้น
คุณสมบัติของลิงค์
- ลิงค์ลิสต์จะใช้เฮดพอยน์เตอร์ (pHead)เป็นตัวชี้ไปยังโหนดแรกของลิสต์ ในขณะที่พอยน์เตอร์หรือลิงค์ของแต่ละโหนดก็จะเชื่อมโยงลิงค์ไปยังโหนดตัวถัดไปโดยโหนดตัวสุดท้ายที่ไม่มีลิงค์ให้เชื่อมต่อจะถูกกำหนดค่าให้เป็น null
- ไม่จำเป็นต้องระบุจำนวนของข้อมูลที่จัดเก็บ เนื่องจากสามารถขอหน่วยความจำใหม่ได้ เมื่อต้องการจัดเก็บข้อมูลเพิ่ม จำทำให้ไม่ต้องระบุจำนวนข้อมูลที่จะจัดเก็บไว้ตั้งแต่ตอนกำหนดตัวแปร
- ขนาดของหน่วยความจำที่ใช้เท่ากับข้อมูลที่จัดเก็บ คือ หน่วยความจำที่ใช้งานจะพอดีกับข้อมูลเพราะไม่ได้ระบุขนาดไว้ก่อนจำทำให้ไม่มีหน่วยความจำที่จองไว้เหลือเหมือนการใช้อาร์เรย์
- กรณีที่เฮดพอยน์เตอร์ไม่มีตัวชี้หรือไม่มีสมาชิก เฮดพอยน์เตอร์จะถูกกำหนดค่าเป็น null
ข้อดีของลิงค์ลิสต์
- เป็นโครงสร้างที่ง่ายต่อการเพิ่มหรือลบข้อมูล
- ไม่จำเป็นต้องขยับอิลิเมนต์ของลิสต์ไปข้างหน้าเพื่อให้เกิดพื้นที่ว่าง ในกรณีที่มีการลบอิลิเมนต์ตรงส่วนหน้าหรือส่วนกลางของลิสต์เช่นเดียวกับอาร์เรย์
- ใช้พื้นที่หน่วยความจำได้เต็มประสิทธิภาพ เนื่องจากหากข้อมูลภายในลิสต์มีน้อยก็ใช้น้อย
ลักษณะของการเก็บข้อมูลและเชื่อมโยงโหนดอื่น ๆ
ของลิงค์ลิสต์
เริ่มจากจุดเริ่มต้นของโครงสร้าง
(Start
Pointer) ซึ่งเป็นตัวแปรที่ทำหน้าที่เก็บตำแหน่งของข้อมูลที่อยู่โหนดแรกในโครงสร้างชี้ไปยังโครงสร้างข้อมูลชุดถัดไป
และในโครงสร้างชุดดังกล่าวนี้ก็มี Pointer ชี้ไปยังโครงสร้างข้อมูลอื่น
ๆ ต่อไปในลักษณะเดียว ส่วน Pointer ในโหนดสุดท้ายจะเก็บค่า NULL
(ค่าว่าง)
บางครั้งแทนตำแหน่งสุดท้ายในโครงสร้างด้วยสัญลักษณ์ทางไฟฟ้า เรียกว่า ground
symbol เป็นการแสดงตำแหน่งสุดท้ายในโครงสร้าง
Storage Pool
Storage
Pool หรือ Free List
หมายถึง
เนื้อที่ว่างในหน่วยความจำ
มีลักษณะเป็นโหนดเก็บอยู่ในโครงสร้างข้อมูลลิงค์ลิสต์ หรืออาจเรียกได้ว่าเป็น Free Stack ลักษณะการดำเนินการเหมือนกับโครงสร้างข้อมูลสแต็ก เมื่อมีการเพิ่มสมาชิกใหม่ในโครงสร้างข้อมูลลิงค์ลิสต์จะนำโหนดว่าง
1 โหนดออกมาจาก Free List (เป็นโหนดแรกใน
Free List) จากนั้นใส่ข้อมูลลงไปในส่วนของ Data Field
หลังจากนั้น
นำโหนดดังกล่าวเชื่อมโยงเข้าไปไว้ในโครงสร้างข้อมูลที่ต้องการ
และหากมีการลบสมาชิกตัวใดตัวหนึ่งออกจากโครงสร้างจะต้องนำโหนดที่ถูกลบนี้ใส่คืนใน Free
List ไว้เป็นโหนดแรกใน Free List เสมอ
การเข้าถึงข้อมูลภายใน
การเข้าถึงข้อมูลภายในโครงสร้างลิงค์ลิสต์
จะต้องอาศัยพอยน์เตอร์เป็นตัวเข้าไปในโครงสร้าง สมมติให้พอยน์เตอร์ดังกล่าว คือ PTR และทำหน้าที่ชี้ตำแหน่งแอดเดรสของโหนดในโครงสร้าง
เมื่อต้องการไปยังโหนดถัดไปก็ให้ทำการเลื่อนตำแหน่งของพอยน์เตอร์ โดยตำแหน่งของโหนดถัดไปได้จากส่วนของ LINK ในโหนดปัจจุบัน
การเพิ่มข้อมูลในโครงสร้างข้อมูลลิงค์ลิสต์ มี 3
ลักษณะ คือ
1.
การเพิ่มข้อมูลที่จุดเริ่มต้นของโครงสร้าง
2.
การเพิ่มข้อมูลต่อจากโหนดที่กำหนด
3.
การเพิ่มข้อมูลที่จุดสุดท้ายของโครงสร้าง
การเพิ่มข้อมูลที่จุดเริ่มต้นของโครงสร้าง
เป็นการเพิ่มโหนดของข้อมูลไปยังตำแหน่งแรกของโครงสร้างลิงค์ลิสต์
โดยการเปลี่ยนค่าเริ่มต้นให้ชี้ไปยังตำแหน่งของโหนดใหม่ (NEW
Node) ที่สร้างขึ้น และให้ Pointer
ของโหนดใหม่ชี้ไปยังตำแหน่งเริ่มต้นเดิมแทน
ขั้นตอนการเพิ่มข้อมูลที่ตำแหน่งเริ่มต้นของโครงสร้าง
1.
ตรวจสอบ OVERFLOW ถ้าโหนดใหม่มีค่าเป็น
NULL แสดงว่า OVERFLOW
2.
กำหนด PTR ให้ชี้ไปที่โหนดของ
FREE LIST
3.ใส่ข้อมูลใหม่ลงไปในโหนดใหม่
4.ให้โหนดใหม่ชี้ไปยังโหนดเริ่มต้นเดิมและเปลี่ยนตำแหน่งเริ่มต้นให้ชี้ไปยังโหนดใหม่
การเพิ่มข้อมูลเป็นโหนดสุดท้ายของโครงสร้าง
เป็นการนำโหนดข้อมูลใหม่มาต่อยังตำแหน่งท้ายสุดของโครงสร้าง
(Pointer ของโหนดสุดท้ายมีค่าเป็น NULL) โดยการกำหนดให้ Pointer
ของโหนดข้อมูลสุดท้าย ชี้ไปยังโหนดใหม่ และให้
Pointer ของ
โหนดใหม่มีค่าเป็น NULL แทน
ขั้นตอนการเพิ่มข้อมูลเป็นโหนดสุดท้ายของโครงสร้าง
1.
ตรวจสอบ OVERFLOW ถ้าโหนดใหม่มีค่าเป็น
NULL แสดงว่า OVERFLOW
2.
กำหนด PTR (ที่อยู่ตำแหน่งสุดท้าย)
ให้ชี้ไปที่โหนดของ FREE
LIST
3.
ใส่ข้อมูลใหม่ลงไปในโหนดใหม่
4.
กำหนด PTR ของโหนดใหม่มีค่าเป็นน
NULL
การเพิ่มข้อมูลต่อจากโหนดที่กำหนด
เป็นการแทรกโหนดข้อมูลใหม่เข้าไประหว่างโหนดข้อมูล
2 โหนด
โดยการเปลี่ยน Pionter ที่ชี้โหนดเก่าให้ชี้ไปยังตำแหน่งของโหนดใหม่
และ ให้ Poinnter ของโหนดใหม่ขี้ไปยังตำแหน่งเดิมแทน
ขั้นตอนการเพิ่มข้อมูลที่ตำแหน่งโหนดที่กำหนดของโครงสร้าง
1.
ตรวจสอบ OVERFLOW ถ้าโหนดใหม่มีค่าเป็น
NULL แสดงว่า OVERFLOW
2.
กำหนด PTR ให้ชี้ไปที่โหนดของ
FREE LIST
3.
ใส่ข้อมูลใหม่ลงไปในโหนดใหม่
4.
กำหนดค่าให้โหนดแรก ถ้า PTR
= NULL ให้กำหนดโหนดใหม่เป็นจุดเริ่มต้น ถ้า PTR
<> NULL ให้นำโหนดใหม่มาต่อ
(PTR ชี้ไปที่โหนดใหม่)
การลบข้อมูลจากโครงสร้าง
การลบข้อมูลจากโครงสร้าง
หมายถึง การดึงเอาโหนดที่ต้องการลบออกจากลิงค์ลิสต์ชุดเดิม ดังนั้น การเปลี่ยนแปลงที่เกิดขึ้นคือ การเปลี่ยนค่าพอยน์เตอร์และเมื่อทำการลบข้อมูลออกจากโครงสร้างแล้วจะต้องคืนโหนดที่ถูกลบให้กับ
Storage Pool เพื่อที่จะได้สามารถนำหน่วยความจำส่วนนั้นไปใช้งานต่อไป
การลบข้อมูลออกจากโครงสร้างลิงค์ลิสต์
เกิดขึ้นได้หลายลักษณะสรุปได้ดังนี้
1.
การลบโหนดแรก
2.
การลบโหนดที่อยู่หลังโหนดที่กำหนด
3.
การลบโหนดสุดท้าย
ขั้นตอนการลบโหนดมีดังนี้
1.
เก็บค่าตำแหน่งและค่าของ Pointer ของโหนดที่ต้องการล
2.
กำหนดค่าของ Pointer ของโหนดที่ต้องการลบ
ไปยังโหนดก่อนหน้านั้น
3.
กำหนดตำแหน่งของโหนดที่ต้องการลบคืนกลับไปยัง Storage Pool
ประเภทของโครงสร้างข้อมูลลิงค์ลิสต์
โครงสร้างข้อมูลลิงค์ลิสต์ แบ่งเป็น
2 กลุ่มใหญ่ ๆ ได้แก่
1.
โครงสร้างข้อมูลลิงค์ลิสต์เดี่ยว (Singly
Linked List : SLL)
2.
โครงสร้างข้อมูลลิงค์ลิสต์คู่ (Doubly
Linked List : DLL)
โครงสร้างข้อมูลลิงค์ลิสต์คู่ (Doubly Linked
List)
โครงสร้างข้อมูลลิงค์ลิสต์คู่ (Doubly Linked
List) เป็นโครงสร้างที่แต่ละโหนดข้อมูลสามารถชี้ตำแหน่งโหนดข้อมูลถัดไปได้
2 ทิศทาง
(มีพอยน์เตอร์ชี้ตำแหน่งอยู่สองทิศทาง) โดยมีพอยน์เตอร์อยู่ 2
ตัว คือ พอยน์เตอร์ LLINK ทำหน้าที่ชี้ไปยังโหนดด้านซ้ายของโหนดข้อมูลนั้น
ๆ และ พอยน์เตอร์ RLINK ทำหน้าที่ชี้ไปยังโหนดด้านขวาของโหนดข้อมูลนั้น
ๆ
ความคิดเห็น
แสดงความคิดเห็น