บทที่3 โครงสร้างข้อมูลแบบลิงค์ลิสต์
Linked List
โครงสร้างข้อมูลลิงค์ลิสต์ (Linked List)
จากการทำงานของโครงสร้างข้อมูลอาร์เรย์ (Array Structure) , โครงสร้างข้อมูลสแตก (Stack Structure) และโครงสร้างข้อมูลคิว (Queue Structure) มีลักษณะการจัดเก็บข้อมูลและการเข้าถึงข้อมูลในโครงสร้างแบบลำดับเป็นพื้นที่ต่อเนื่องกัน การใช้งานของโครงสร้างถูกจำกัดไว้ไม่สามารถทำการปรับเปลี่ยนหรือแก้ไขขนาดของโครงสร้างได้ หรือหากต้องการปรับเปลี่ยนโครงสร้างใหม่ จะทำให้เสียเวลาในการประมวลผล ซึ่งในการใช้งานโปรแกรมพื้นที่หน่วยความจำ (Memory) เป็นสิ่งจำเป็นมาก การแก้ไขปัญหาดังกล่าว โดยใช้โครงสร้างข้อมูลแบบอื่น ๆ เป็นสิ่งจำเป็นที่ต้องพิจารณาและยากมาก เป็นการจัดเก็บชุดข้อมูลเชื่อมโยงต่อเนื่องกันไปตามลำดับ โครงสร้างข้อมูลแบบลิงค์ลิสต์จะประกอบไปด้วยส่วนที่เรียกว่า สมาชิก
( Node) ส่วน เก็บข้อมูล (Data) และตำแหน่งของสมาชิกตัวถัดไป (Link)
ลักษณะของลิงค์ลิสต์
1.เป็นโครงสร้างข้อมูลชนิดไม่เป็นเชิงเส้น (Non Linear Structure) คือ จัดเก็บข้อมูลในหน่วยความจำแบบไม่ต่อเนื่องกัน การเขียนโปรแกรมจะใช้พอยเตอร์ (Pointer)
2.ไม่จำเป็นต้องระบุจำนวนของข้อมูลที่จัดเก็บ เนื่องจากสามารถขอหน่วยความจำใหม่ได้ เมื่อต้องการจัดเก็บข้อมูลเพิ่ม จำทำให้ไม่ต้องระบุจำนวนข้อมูลที่จะจัดเก็บไว้ตั้งแต่ตอนกำหนดตัวแปร
3.ขนาดของหน่วยความจำที่ใช้เท่ากับข้อมูลที่จัดเก็บ คือ หน่วยความจำที่ใช้งานจะพอดีกับข้อมูลเพราะไม่ได้ระบุขนาดไว้ก่อนจำทำให้ไม่มีหน่วยความจำที่จองไว้เหลือเหมือนการใช้อารืเรย์
4.ต้องมีพอยเตอร์ชี้โหนดแรก หากไม่มีพอยเอตร์ทีจำตำแหน่งที่อยู่ของโหนดแรกแล้วก็จะไม่สามารถเข้าถึงข้อมูลที่จัดเก็บในโหนดต่างๆ ได้
ข้อดีของลิงค์ลิสต์
•เป็นโครงสร้างที่ง่ายต่อการเพิ่มหรือลบข้อมูล•ไม่จำเป็นต้องขยับอิลิเมนต์ของลิสต์ไปข้างหน้าเพื่อให้เกิดพื้นที่ว่าง ในกรณี ที่มีการลบอิลิเมนต์ตรงส่วนหน้าหรือส่วนกลางของลิสต์เช่นเดียวกับอาร์เรย์
•ใช้พื้นที่หน่วยความจำได้เต็มประสิทธิภาพ เนื่องจากหากข้อมูลภายในลิสต์มี น้อยก็ใช้น้อย ซึ่งผิดกับอาร์เรย์ที่ต้องสูญเสียพื้นที่ไปในทันที ถึงแม้จะไม่มีข้อมูลภายในลิสต์ก็ตาม
การแทนโครงสร้างข้อมูลลิงค์ลิสต์
โครงสร้างข้อมูลลิงค์ลิสต์ (Linked List) ประกอบด้วยส่วนสำคัญ 2 ส่วนรวมเป็นโครงสร้างเรียกว่า โหนด (Node) คือ
1.Data Link ทำหน้าที่เก็บข้อมูล
2. Link Field ทำหน้าที่เก็บตำแหน่งที่อยู่ของโครงสร้างสมาชิกตัวถัดไป
ลักษณะของการเก็บข้อมูลและเชื่อมโยงโหนดอื่น ๆ
ลักษณะของการเก็บข้อมูลและเชื่อมโยงโหนดอื่น ๆ ของลิงค์ลิสต์ เริ่มจากจุดเริ่มต้นของโครงสร้าง (Start Pointer) ซึ่งเป็นตัวแปรที่ทำหน้าที่เก็บตำแหน่งของข้อมูลที่อยู่โหนดแรกในโครงสร้างชี้ไปยังโครงสร้างข้อมูลชุดถัดไป และในโครงสร้างชุดดังกล่าวนี้ก็มี Pointer ชี้ไปยังโครงสร้างข้อมูลอื่น ๆ ต่อไปในลักษณะเดียว ส่วน Pointer ในโหนดสุดท้ายจะเก็บค่า NULL (ค่าว่าง) บางครั้งแทนตำแหน่งสุดท้ายในโครงสร้างด้วยสัญลักษณ์ทางไฟฟ้า เรียกว่า ground symbol เป็นการแสดงตำแหน่งสุดท้ายในโครงสร้าง หรือ
การเข้าถึงข้อมูลภายในโครงสร้างลิงค์ลิสต์
การเข้าถึงข้อมูลภายในโครงสร้างลิงค์ลิสต์ จะต้องอาศัยพอยน์เตอร์
เป็นตัวเข้าไปในโครงสร้าง สมมติให้พอยน์เตอร์ดังกล่าว คือ PTR และทำหน้า
ที่ชี้ตำแหน่งแอดเดรสของโหนดในโครงสร้าง เมื่อต้องการไปยังโหนดถัดไปก็ให้
ทำการเลื่อนตำแหน่งของพอยน์เตอร์ โดยตำแหน่งของโหนดถัดไปได้จากส่วน
ของ LINK ในโหนดปัจจุบัน
ขั้นตอนการเข้าถึงข้อมูลในโครงสร้าง
การเข้าถึงในโครงสร้างเรียกว่า การทำ Traversing มีขั้นตอนดังต่อไปนี้
กำหนดให้ DATA เป็นโครงสร้างข้อมูลลิงค์ลิสต์ และพอยน์เตอร์ PTR
ทำหน้าที่ชี้โหนดที่กำลังดำเนินการ Process อยู่ในขณะนั้น (Current Node)
1. กำหนดค่าเริ่มต้นให้กับพอยน์เตอร์ PTR.
2. การวนรอบดำเนินการ Process ข้อมูล
3. Apply Process to DATA [PTR]
4. เปลี่ยนค่าพอยน์เตอร์ PTR ให้ชี้โหนดถัดไป
5. เสร็จสิ้นขั้นตอน
Storage Pool
Storage Pool หรือ Free List หมายถึง เนื้อที่ว่างในหน่วยความจำ มีลักษณะเป็นโหนดเก็บอยู่ในโครงสร้างข้อมูลลิงค์ลิสต์ หรืออาจเรียกได้ว่าเป็น Free Stack ลักษณะการดำเนินการเหมือนกับโครงสร้างข้อมูลสแต็ก เมื่อมีการเพิ่มสมาชิกใหม่ในโครงสร้างข้อมูลลิงค์ลิสต์จะนำโหนดว่าง 1 โหนดออกมาจาก Free List (เป็นโหนดแรกใน Free List) จากนั้นใส่ข้อมูลลงไปในส่วนของ Data Field หลังจากนั้น นำโหนดดังกล่าวเชื่อมโยงเข้าไปไว้ในโครงสร้างข้อมูลที่ต้องการ และหากมีการลบสมาชิกตัวใดตัวหนึ่งออกจากโครงสร้างจะต้องนำโหนดที่ถูกลบนี้ใส่คืนใน Free List ไว้เป็นโหนดแรกใน Free List เสมอ
การเพิ่มข้อมูลในโครงสร้าง
เมื่อกำหนดโครงสร้างข้อมูลเรียบร้อยแล้ว ก็สามารถทำการเพิ่มข้อมูลในโครงสร้างได้ โดยการขอโหนดว่างจาก 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 ชี้ไปที่โหนดใหม่)
การเพิ่มข้อมูลเป็นโหนดสุดท้ายของโครงสร้าง
เป็นการนำโหนดข้อมูลใหม่มาต่อยังตำแหน่งท้ายสุดของโครงสร้าง (Pointer ของโหนดสุดท้าย มีค่าเป็น NULL) โดยการกำหนดให้ Pointer ของโหนดข้อมูลสุดท้าย ชี้ไปยังโหนดใหม่ และให้ Pointer ของ โหนดใหม่มีค่าเป็น NULL แทน
การลบข้อมูลจากโครงสร้าง
การลบข้อมูลจากโครงสร้าง หมายถึง การดึงเอาโหนดที่ต้องการลบออกจากลิงค์ลิสต์ชุดเดิม ดังนั้น การเปลี่ยนแปลงที่เกิดขึ้นคือ การเปลี่ยนค่าพอยน์เตอร์และเมื่อทำการลบข้อมูลออกจากโครงสร้างแล้วจะต้องคืนโหนดที่ถูกลบให้กับ Storage Pool เพื่อที่จะได้สามารถนำหน่วยความจำส่วนนั้นไปใช้งานต่อไป
การลบข้อมูลออกจากโครงสร้างลิงค์ลิสต์ เกิดขึ้นได้หลายลักษณะสรุปได้ดังนี้
1. การลบโหนดแรก
2. การลบโหนดที่อยู่หลังโหนดที่กำหนด
3. การลบโหนดสุดท้าย
ขั้นตอนการลบโหนดมีดังนี้
1. เก็บค่าตำแหน่งและค่าของ Pointer ของโหนดที่ต้องการลบ
2. กำหนดค่าของ Pointer ของโหนดที่ต้องการลบ ไปยังโหนดก่อนหน้านั้น
3. กำหนดตำแหน่งของโหนดที่ต้องการลบคืนกลับไปยัง Storage Pool
โครงสร้างข้อมูลลิงค์ลิสต์เดี่ยว (SLL)
แบ่งออกเป็น 2 ประเภท
1. โครงสร้างข้อมูลลิงค์ลิสต์แบบ Ordinary Singly Linked List คือ โครงสร้างข้อมูลลิงค์ลิสต์ที่มี ลักษณะเหมือนกับโครงสร้างข้อมูลลิงค์ลิสต์ที่กล่าวมาแล้วตั้งแต่ต้น
2. โครงสร้างข้อมูลลิงค์ลิสต์แบบ Circular Singly Linked List (CLL) มีลักษณะคล้ายกับแบบ SLL ทั่วไป เพียงแต่พอยน์เตอร์สามารถชี้กลับมายังตำแหน่งเริ่มต้นของโครงสร้างได้ โดยใช้พอยน์ เตอร์ของโหนดสุดท้ายในโครงสร้างชี้ไปยังโหนดแรก ทำให้โครงสร้างข้อมูลมีลักษณะเป็นวงกลม
โครงสร้างข้อมูลลิงค์ลิสต์คู่ (Doubly Linked List)
โครงสร้างข้อมูลลิงค์ลิสต์คู่ (Doubly Linked List) เป็นโครงสร้างที่แต่ละโหนดข้อมูลสามารถชี้ตำแหน่งโหนดข้อมูลถัดไปได้ 2 ทิศทาง (มีพอยน์เตอร์ชี้ตำแหน่งอยู่สองทิศทาง) โดยมีพอยน์เตอร์อยู่ 2 ตัว คือ พอยน์เตอร์ LLINK ทำหน้าที่ชี้ไปยังโหนดด้านซ้ายของโหนดข้อมูลนั้น ๆ และ พอยน์เตอร์ RLINK ทำหน้าที่ชี้ไปยังโหนดด้านขวาของโหนดข้อมูลนั้น ๆ
การใช้งานของโหนดข้อมูลแบบลิงค์ลิสต์คู่ คือ พอยน์เตอร์ LLINK จะชี้ไปยังโหนดด้านซ้ายของโหนดข้อมูลนั้น ๆ โดยพอย์เตอร์ที่โหนดข้อมูลสุดท้ายทางด้านซ้าย (LLINK ตัวสุดท้าย) จะมีค่าเป็น NULL และ พอยน์เตอร์ RLINK ทำหน้าที่ชี้ไปยังโหนดด้านขวาของโหนดข้อมูลนั้น ๆ โดยพอย์เตอร์ที่โหนดข้อมูลสุดท้ายทางด้านขวา (RLINK ตัวสุดท้าย) จะมีค่าเป็น NULL เช่นกัน
ไม่มีความคิดเห็น:
แสดงความคิดเห็น