บทที่ 3
linked-list
โครงสร้างข้อมูล link list
จากการทำงานของโครงสร้างข้อมูลอาร์เรย์ (Array Structure) ,
โครงสร้างข้อมูลสแตก (Stack Structure) และโครงสร้างข้อมูลคิว (Queue Structure) มีลักษณะการจัดเก็บข้อมูลและการเข้าถึงข้อมูลในโครงสร้างแบบลำดับเป็นพื้นที่ต่อเนื่องกัน
การใช้งานของโครงสร้างถูกจำกัดไว้ไม่สามารถทำการปรับเปลี่ยนหรือแก้ไขขนาดของโครงสร้างได้
หรือหากต้องการปรับเปลี่ยนโครงสร้างใหม่ จะทำให้เสียเวลาในการประมวลผล
ซึ่งในการใช้งานโปรแกรมพื้นที่หน่วยความจำ (Memory) เป็นสิ่งจำเป็นมาก
การแก้ไขปัญหาดังกล่าว โดยใช้โครงสร้างข้อมูลแบบอื่น ๆ
เป็นสิ่งจำเป็นที่ต้องพิจารณาและยากมาก
•
เป็นการจัดเก็บชุดข้อมูลเชื่อมโยงต่อเนื่องกันไปตามลำดับ
โครงสร้างข้อมูลแบบลิงค์ลิสต์จะประกอบไปด้วยส่วนที่เรียกว่า สมาชิก
( Node) ส่วน เก็บข้อมูล (Data) และตำแหน่งของสมาชิกตัวถัดไป
(Link)
List
•
สร้างลิสต์แบบง่ายมี 2 วิธี
1)
Array
2)
2) Link List
แนะนำ Linked List
Array
0 1 2 3 4
Data Next
 |
Node
ปัญหาของตัวแปรแบบ Array
- ตัวแปรแบบ
Array มีการจองเนื้อที่ที่อยู่ติดกันตามจำนวนที่ต้องการไว้ก่อน
เช่น ถ้าต้องการจัดเก็บข้อมูลจำนวน 10,000 ค่า
แต่ละค่าใช้เนื้อที่ 2 byte เนื้อที่ทั้งหมดที่ถูกจองจะเป็น 20,000
byte ซึ่งบางครั้งอาจจะไม่มีเนื้อที่ว่างที่อยู่ติดกันเพียงพอสำหรับเก็บข้อมูล
20,000 byte ทำให้โปรแกรมไม่สามารถทำงานได้
- บางกรณีจองเนื้อที่ไว้สำหรับเก็บข้อมูล
10,000 ค่า
เนื่องจากไม่ทราบจำนวนข้อมูลที่ต้องการเก็บ แต่เมื่อใช้งานจริง
เก็บข้อมูลเพียง 2,000 ค่า ทำให้เหลือเนื้อที่ที่ยังไม่ได้ใช้ แต่ไม่สามารถนำไปใช้งานอื่นได้
- กรณีจองเนื้อที่ไว้สำหรับเก็บข้อมูล
10,000 ค่า
แต่การใช้งานจริงมีข้อมูลที่ต้องเก็บมากกว่า 10,000 ค่า
ก็ไม่สามารถเก็บข้อมูลส่วนที่เหลือได้ เนื่องจากจองไว้แค่ไหน ก็ใช้ได้แค่นั้น
คุณสมบัติของลิงค์
•
ลิงค์ลิสต์จะใช้เฮดพอยน์เตอร์ (pHead)เป็นตัวชี้ไปยังโหนดแรกของลิสต์
ในขณะที่พอยน์เตอร์หรือลิงค์ของแต่ละโหนดก็จะเชื่อมโยงลิงค์ไปยังโหนดตัวถัดไปโดยโหนดตัวสุดท้ายที่ไม่มีลิงค์ให้เชื่อมต่อจะถูกกำหนดค่าให้เป็น
null
ซึ่งในที่นี้ใช้สัญลักษณ์
แทน
•
โหนดของข้อข้อมูลจะประกอบไปด้วย Data และ Link
โดย
–
Data คือข้อมูลหรือสารสนเทศที่สามารถนำไปใช้ประโยชน์
–
Link
คือตัวชี้หรือพอยน์เตอร์ที่ใช้สำหรับเชื่อมโยงไปยังโหนดถัดไป
•
ไม่มีความสัมพันธ์ทางการภาพระหว่างโหนด
•
ข้อมูลที่จัดเก็บภายในหน่วยความจำไม่จำเป็นต้องอยู่ติดกัน
•
ไม่จำเป็นต้องระบุจำนวนของข้อมูลที่จัดเก็บ
เนื่องจากสามารถขอหน่วยความจำใหม่ได้ เมื่อต้องการจัดเก็บข้อมูลเพิ่ม
จำทำให้ไม่ต้องระบุจำนวนข้อมูลที่จะจัดเก็บไว้ตั้งแต่ตอนกำหนดตัวแปร
•
ขนาดของหน่วยความจำที่ใช้เท่ากับข้อมูลที่จัดเก็บ
คือ หน่วยความจำที่ใช้งานจะพอดีกับข้อมูลเพราะไม่ได้ระบุขนาดไว้ก่อนจำทำให้ไม่มีหน่วยความจำที่จองไว้เหลือเหมือนการใช้อาร์เรย์
•
กรณีที่เฮดพอยน์เตอร์ไม่มีตัวชี้หรือไม่มีสมาชิก
เฮดพอยน์เตอร์จะถูกกำหนดค่าเป็น null ซึ่งหมายถึงลิสต์ว่างนั่นเอง
ไม่มีความสัมพันธ์ทางการภาพระหว่างโหนด
โครงสร้างข้อมูลแบบลิงค์ลิสต์ประกอบด้วยโหนดต่างๆต่อกันโดยแต่ละโหนดมีส่วนที่สำคัญ
2 ส่วนคือ ส่วนที่เก็บข้อมูล (Data) และ ส่วนที่เก็บตัวชี้ (Pointer)
data pointer 25 |
x
|
data pointer 
Andaman
|
45.5
|
38.7
|
5
|
ข้อดีของลิงค์ลิสต์
• เป็นโครงสร้างที่ง่ายต่อการเพิ่มหรือลบข้อมูล
• ไม่จำเป็นต้องขยับอิลิเมนต์ของลิสต์ไปข้างหน้าเพื่อให้เกิดพื้นที่ว่าง
ในกรณีที่มีการลบอิลิเมนต์ตรงส่วนหน้าหรือส่วนกลางของลิสต์เช่นเดียวกับอาร์เรย์
• ใช้พื้นที่หน่วยความจำได้เต็มประสิทธิภาพ
เนื่องจากหากข้อมูลภายในลิสต์มีน้อยก็ใช้น้อย
ซึ่งผิดกับอาร์เรย์ที่ต้องสูญเสียพื้นที่ไปในทันที
ถึงแม้จะไม่มีข้อมูลภายในลิสต์ก็ตาม
• เป็นโครงสร้างที่ง่ายต่อการเพิ่มหรือลบข้อมูล
• ไม่จำเป็นต้องขยับอิลิเมนต์ของลิสต์ไปข้างหน้าเพื่อให้เกิดพื้นที่ว่าง
ในกรณีที่มีการลบอิลิเมนต์ตรงส่วนหน้าหรือส่วนกลางของลิสต์เช่นเดียวกับอาร์เรย์
• ใช้พื้นที่หน่วยความจำได้เต็มประสิทธิภาพ
เนื่องจากหากข้อมูลภายในลิสต์มีน้อยก็ใช้น้อย
ซึ่งผิดกับอาร์เรย์ที่ต้องสูญเสียพื้นที่ไปในทันที
ถึงแม้จะไม่มีข้อมูลภายในลิสต์ก็ตาม
• ตัวชี้ (Pointer)
บางครั้งเรียก ลิงค์ (Link) หรือ
ตัวอ้างอิง (Reference) คือ การกำหนดตัวแปร (Variable) เพื่อเก็บตำแหน่งของตัวแปรอื่นๆ
หรือโครงสร้างข้อมูลอื่น ๆ ที่ใช้อยู่ในโปรแกรม
พื้นฐานที่กำกับ linked-list
•
การท่องเข้าไปในลิงค์ลิสต์
•
การเพิ่มข้อมูลลงในลิงค์ลิสต์
•
การลบข้อมูลออกจากลิงค์ลิสต์
•
การทำให้ลิสต์ว่างเปล่า
ลักษณะของการเก็บข้อมูลและเชื่อมโยงโหนดอื่น
ๆ ของลิงค์ลิสต์ เริ่มจากจุดเริ่มต้นของโครงสร้าง (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 ในโหนดปัจจุบัน
การเข้าถึงในโครงสร้างเรียกว่า การทำ Traversing มีขั้นตอนดังต่อไปนี้
กำหนดให้
DATA เป็นโครงสร้างข้อมูลลิงค์ลิสต์ และพอยน์เตอร์ PTR
ทำหน้าที่ชี้โหนดที่กำลังดำเนินการ Process
อยู่ในขณะนั้น
(Current Node)
1. กำหนดค่าเริ่มต้นให้กับพอยน์เตอร์ PTR.
2. การวนรอบดำเนินการ Process
ข้อมูล
3.
Apply Process to DATA [PTR]
4. เปลี่ยนค่าพอยน์เตอร์ PTR ให้ชี้โหนดถัดไป
5. เสร็จสิ้นขั้นตอน
การเพิ่มข้อมูลในโครงสร้าง
เมื่อกำหนดโครงสร้างข้อมูลเรียบร้อยแล้ว
ก็สามารถทำการเพิ่มข้อมูลในโครงสร้างได้
โดยการขอโหนดว่างจาก free list
และนำมาเชื่อมโยงกับรายการข้อมูลที่มีอยู่เดิมในโครงสร้างตรงตำแหน่งที่ต้องการ
การเพิ่มข้อมูลในโครงสร้างข้อมูลลิงค์ลิสต์
อาจเกิดในลักษณะที่ต่างกัน ซึ่งสรุปได้เป็น 3 ลักษณะ คือ
1. การเพิ่มข้อมูลที่จุดเริ่มต้นของโครงสร้าง
2.
การเพิ่มข้อมูลต่อจากโหนดที่กำหนด
3. การเพิ่มข้อมูลที่จุดสุดท้ายของโครงสร้าง
•
การเพิ่มข้อมูลลงในลิงค์ลิสต์
–
เพิ่มที่ส่วนต้นของลิสต์
–
เพิ่มที่ส่วนท้ายของลิสต์
–
แทรกเข้าไปในลิสต์
•
การเพิ่มข้อมูลที่จุดเริ่มต้นของโครงสร้าง
เป็นการเพิ่มโหนดของข้อมูลไปยังตำแหน่งแรกของโครงสร้างลิงค์ลิสต์
โดยการเปลี่ยนค่าเริ่มต้นให้ชี้ไปยังตำแหน่งของโหนดใหม่ (NEW Node) ที่สร้างขึ้น และให้ Pointer ของโหนดใหม่ชี้ไปยังตำแหน่งเริ่มต้นเดิมแทน
•
ขั้นตอนการเพิ่มข้อมูลที่ตำแหน่งเริ่มต้นของโครงสร้าง
1.
ตรวจสอบ OVERFLOW ถ้าโหนดใหม่มีค่าเป็น NULL
แสดงว่า
OVERFLOW
2.
กำหนด
PTR ให้ชี้ไปที่โหนดของ FREE
LIST
3.ใส่ข้อมูลใหม่ลงไปในโหนดใหม่
4.ให้โหนดใหม่ชี้ไปยังโหนดเริ่มต้นเดิมและเปลี่ยนตำแหน่งเริ่มต้นให้ชี้ไปยังโหนดใหม่
•
การเพิ่มข้อมูลลงในลิงค์ลิสต์
–
แทรกเข้าไปในลิสต์
การเพิ่มข้อมูลต่อจากโหนดที่กำหนด
เป็นการแทรกโหนดข้อมูลใหม่เข้าไประหว่างโหนดข้อมูล
2 โหนด โดยการเปลี่ยน Pionter ที่ชี้โหนดเก่าให้ชี้ไปยังตำแหน่งของโหนดใหม่ และ
ให้ Poinnter ของโหนดใหม่ขี้ไปยังตำแหน่งเดิมแทน
•
ขันตอนการเพิ่มข้อมูลที่ตำแหน่งโหนดที่กำหนดของโครงสร้าง
1.
ตรวจสอบ
OVERFLOW ถ้าโหนดใหม่มีค่าเป็น NULL
แสดงว่า
OVERFLOW
2.
กำหนด
PTR ให้ชี้ไปที่โหนดของ FREE
LIST
3.
ใส่ข้อมูลใหม่ลงไปในโหนดใหม่
4.
กำหนดค่าให้โหนดแรก
ถ้า PTR = NULL ให้กำหนดโหนดใหม่เป็นจุดเริ่มต้น ถ้า PTR <> NULL ให้นำโหนดใหม่มาต่อ
(PTR ชี้ไปที่โหนดใหม่)
•
การเพิ่มข้อมูลลงในลิงค์ลิสต์
–
เพิ่มที่ส่วนท้ายของลิสต์
การเพิ่มข้อมูลต่อจากโหนดที่กำหนด
เป็นการแทรกโหนดข้อมูลใหม่เข้าไประหว่างโหนดข้อมูล
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 ทำหน้าที่ชี้ไปยังโหนดด้านขวาของโหนดข้อมูลนั้น ๆ
การใช้งานของโหนดข้อมูลแบบลิงค์ลิสต์คู่
คือ พอยน์เตอร์ LLINK จะชี้ไปยังโหนดด้านซ้ายของโหนดข้อมูลนั้น ๆ
โดยพอย์เตอร์ที่โหนดข้อมูลสุดท้ายทางด้านซ้าย (LLINK ตัวสุดท้าย)
จะมีค่าเป็น NULL และ พอยน์เตอร์ RLINK ทำหน้าที่ชี้ไปยังโหนดด้านขวาของโหนดข้อมูลนั้น
ๆ โดยพอย์เตอร์ที่โหนดข้อมูลสุดท้ายทางด้านขวา (RLINK ตัวสุดท้าย)
จะมีค่าเป็น NULL เช่นกัน
·
ชนิดของโครงสร้างข้อมูลลิงค์ลิสต์แบบ Doubly Linked List
แบ่งออกเป็น
2 แบบ คือ
1.
โครงสร้างข้อมูลลิงค์ลิสต์แบบ Ordinary Doubly
Linked List(ODLL)
2.
โครงสร้างข้อมูลลิงค์ลิสต์แบบ Circularly Doubly Linked List
(CDLL)
โครงสร้างข้อมูลลิงค์ลิสต์แบบ
Ordinary DLL คือ ลักษณะของโครงสร้างลิงค์ลิสต์ที่ส่วนของพอยน์เตอร์ที่ link ทางซ้าย (LLINK)
ของโหนดซ้ายมือสุดและพอยน์เตอร์ที่ link ทางด้านขวาสุดของโครงสร้าง (RLINK) มีค่าเป็น NULL ทั้งคู่
เพื่อแสดงว่าเป็นโหนดสุดท้ายของโครงสร้างที่ปลายทั้งสองด้าน
ขั้นตอนการเพิ่มโหนดข้อมูลมีดังนี้
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.
คืนโหนดที่ลบให้กับระบบ
โครงสร้างข้อมูลลิงค์ลิสต์แบบ
Circularly DLL คือ ลักษณะของ Doubly
linked list ที่มี Link ทางซ้าย (LLINK)
ของโหนดซ้ายมือสุดเก็บตำแหน่งที่อยู่ของโหนดที่อยู่ทางขวามือสุดและ Link ทางด้านขวา (RLINK)
ของโหนดขวามือสุดก็จะเก็บตำแหน่งที่อยู่ของโหนดที่อยู่ทางซ้ายมือสุด
ไม่มีความคิดเห็น:
แสดงความคิดเห็น