โครงสร้างข้อมูลลิงค์ลิสต์ (Linked List)

Report
1
โครงสร้ างข้ อมูลแบบลิงค์ ลสิ ต์
Linked List
2
โครงสร้ างข้ อมูลลิงค์ ลิสต์ (Linked List)
จากการทางานของโครงสร้ างข้ อมูลอาร์ เรย์ (Array Structure) ,
โครงสร้ างข้ อมูลสแตก (Stack Structure) และโครงสร้ างข้ อมูลคิว (Queue
Structure) มีลกั ษณะการจัดเก็บข้ อมูลและการเข้ าถึงข้ อมูลในโครงสร้ างแบบ
ลาดับเป็ นพื ้นที่ตอ่ เนื่องกัน การใช้ งานของโครงสร้ างถูกจากัดไว้ ไม่สามารถทา
การปรับเปลี่ยนหรื อแก้ ไขขนาดของโครงสร้ างได้ หรื อหากต้ องการปรับเปลี่ยน
โครงสร้ างใหม่ จะทาให้ เสียเวลาในการประมวลผล ซึง่ ในการใช้ งานโปรแกรม
พื ้นที่หน่วยความจา (Memory) เป็ นสิ่งจาเป็ นมาก การแก้ ไขปั ญหาดังกล่าว
โดยใช้ โครงสร้ างข้ อมูลแบบอื่น ๆ เป็ นสิ่งจาเป็ นที่ต้องพิจารณาและยากมาก
3
โครงสร้ างข้ อมูลลิงค์ ลิสต์ (Linked List)

เป็ นการจัดเก็บชุดข้ อมูลเชื่อมโยงต่อเนื่องกันไปตามลาดับ โครงสร้ าง
ข้ อมูลแบบลิงค์ลสิ ต์จะประกอบไปด้ วยส่วนที่เรี ยกว่า สมาชิก ( Node)
ส่วน เก็บข้อมูล (Data) และตาแหน่งของสมาชิกตัวถัดไป (Link)
อาร์ เรย์ (Array)
ลิงค์ ลิสต์ (Linked
List)
4
โครงสร้ างข้ อมูลลิงค์ ลิสต์ (Linked List)
ลักษณะของลิงค์ ลิสต์
1. เป็ นโครงสร้ างข้ อมูลชนิดไม่ เป็ นเชิงเส้ น (Non Linear Structure)
คือ จัดเก็บข้ อมูลในหน่วยความจาแบบไม่ตอ่ เนื่องกัน การเขียนโปรแกรม
จะใช้ พอยเตอร์ (Pointer)
2. ไม่ จาเป็ นต้ องระบุจานวนของข้ อมูลที่จัดเก็บ เนื่องจากสามารถขอ
หน่วยความจาใหม่ได้ เมื่อต้ องการจัดเก็บข้ อมูลเพิ่ม จาทาให้ ไม่ต้องระบุ
จานวนข้ อมูลที่จะจัดเก็บไว้ ตงแต่
ั ้ ตอนกาหนดตัวแปร
3. ขนาดของหน่ วยความจาที่ใช้ เท่ ากับข้ อมูลที่จัดเก็บ คือ
หน่วยความจาที่ใช้ งานจะพอดีกบั ข้ อมูลเพราะไม่ได้ ระบุขนาดไว้ ก่อนจา
ทาให้ ไม่มีหน่วยความจาที่จองไว้ เหลือเหมือนการใช้ อารื เรย์
4. ต้ องมีพอยเตอร์ ชีโ้ หนดแรก หากไม่มีพอยเอตร์ ทีจาตาแหน่งที่อยูข่ อง
โหนดแรกแล้ วก็จะไม่สามารถเข้ าถึงข้ อมูลที่จดั เก็บในโหนดต่างๆ ได้
5
โครงสร้ างข้ อมูลลิงค์ ลิสต์ (Linked List)
ข้ อดีของลิงค์ ลิสต์
• เป็ นโครงสร้ างที่ง่ายต่อการเพิ่มหรื อลบข้ อมูล
• ไม่จาเป็ นต้ องขยับอิลเิ มนต์ของลิสต์ไปข้ างหน้ าเพื่อให้ เกิดพื ้นที่วา่ ง ในกรณีที่
มีการลบอิลเิ มนต์ตรงส่วนหน้ าหรื อส่วนกลางของลิสต์เช่นเดียวกับอาร์ เรย์
• ใช้ พื ้นที่หน่วยความจาได้ เต็มประสิทธิภาพ เนื่องจากหากข้ อมูลภายในลิสต์มี
น้ อยก็ใช้ น้อย ซึง่ ผิดกับอาร์ เรย์ที่ต้องสูญเสียพื ้นที่ไปในทันที ถึงแม้ จะไม่มี
ข้ อมูลภายในลิสต์ก็ตาม
6
โครงสร้ างข้ อมูลลิงค์ ลิสต์ (Linked List)
จากแนวความคิดที่จะนาตัวชี ้ (Pointer) มาใช้ ตาแหน่งโครงสร้ าง
ข้ อมูลซึง่ จะทาให้ ไม่ต้องคอยกังวลในเรื่ องของการกาหนดขนาดโครงสร้ าง ทา
ให้ คอมพิวเตอร์ สามารถใช้ งานพื ้นที่หน่วยความจาได้ เต็มประสิทธิภาพ
ตัวชี้ (Pointer) บางครั้ งเรี ยก ลิงค์ (Link) หรื อ ตัวอ้ างอิง
(Reference) คือ การกาหนดตัวแปร (Variable) เพื่อเก็บตาแหน่ งของตัว
แปรอื่นๆ หรื อโครงสร้ างข้ อมูลอื่น ๆ ที่ใช้ อยู่ในโปรแกรม
7
โครงสร้ างข้ อมูลลิงค์ ลิสต์ (Linked List)
โครงสร้ างข้ อมูลลิงค์ลิสต์เป็ นโครงสร้ างข้ อมูลแบบรายการเชิงเส้ นที่
มีลกั ษณะการดาเนินการเพิ่มข้ อมูล (Insertion) หรื อลบข้ อมูล (Deletion)
ออกจากโครงสร้ าง สามารถกระทาที่ข้อมูลตรงตาแหน่ งใด ๆ ใน
โครงสร้ างก็ได้ ดังนัน้ ลักษณะของโครงสร้ างจึงมีความยืดหยุ่น (Flexible)
กว่าและไม่ มีขีดจากัดด้ านความจุของข้ อมูลในโครงสร้ าง แต่ขนตอนการ
ั้
ดาเนินงานกับโครงสร้ างลิงค์ลิสต์นี ้มีความยุง่ ยากและซับซ้ อนมากกว่า
8
โครงสร้ างข้ อมูลลิงค์ ลิสต์ (Linked List)
การแทนโครงสร้ างข้ อมูลลิงค์ ลสิ ต์
โครงสร้ างข้ อมูลลิงค์ลิสต์ (Linked List) ประกอบด้ วยส่วนสาคัญ 2
ส่วนรวมเป็ นโครงสร้ างเรี ยกว่า โหนด (Node) คือ
1 .Data Link ทาหน้ าที่เก็บข้ อมูล
2. Link Field ทาหน้ าที่เก็บตาแหน่งที่อยูข่ องโครงสร้ างสมาชิกตัว
ถัดไป
ลักษณะของโหนด
DATA
ส่ วนที่เก็บข้ อมูล
LINK
ส่ วนที่เก็บตาแหน่ งที่อยู่
ของโหนดถัดไป
9
โครงสร้ างข้ อมูลลิงค์ ลิสต์ (Linked List)
ลักษณะของการเก็บข้ อมูลและเชื่อมโยงโหนดอื่น ๆ ของลิงค์ลสิ ต์
เริ่มจากจุดเริ่มต้ นของโครงสร้ าง (Start Pointer) ซึง่ เป็ นตัวแปรที่ทาหน้ าที่เก็บ
ตาแหน่งของข้ อมูลที่อยู่โหนดแรกในโครงสร้ างชี ้ไปยังโครงสร้ างข้ อมูลชุดถัดไป
และในโครงสร้ างชุดดังกล่าวนี ้ก็มี Pointer ชี ้ไปยังโครงสร้ างข้ อมูลอื่น ๆ ต่อไป
ในลักษณะเดียว ส่วน Pointer ในโหนดสุดท้ ายจะเก็บค่า NULL (ค่าว่าง)
บางครัง้ แทนตาแหน่งสุดท้ายในโครงสร้างด้วยสัญลักษณ์ทางไฟฟ้า เรี ยกว่า
ground symbol เป็ นการแสดงตาแหน่งสุดท้ ายในโครงสร้ าง หรื อ
โครงสร้ างข้ อมูลลิงค์ ลิสต์ (Linked List)
การเชื่อมโยงของโครงสร้ างลิงค์ ลิสต์ (A linked list)
1
0
โครงสร้ างข้ อมูลลิงค์ ลิสต์ (Linked List)
การแทนลิงค์ ลิสต์ ในพืน้ ที่
หน่ วยความจาแบบหนึ่ง
1
1
12
โครงสร้ างข้ อมูลลิงค์ ลิสต์ (Linked List)
การเข้ าถึงข้ อมูลภายในโครงสร้ างลิงค์ ลสิ ต์
การเข้ าถึงข้ อมูลภายในโครงสร้ างลิงค์ลิสต์ จะต้ องอาศัยพอยน์เตอร์
เป็ นตัวเข้ าไปในโครงสร้ าง สมมติให้ พอยน์เตอร์ ดงั กล่าว คือ PTR และทาหน้ า
ที่ชี ้ตาแหน่งแอดเดรสของโหนดในโครงสร้ าง เมื่อต้ องการไปยังโหนดถัดไปก็ให้
ทาการเลื่อนตาแหน่งของพอยน์เตอร์ โดยตาแหน่งของโหนดถัดไปได้ จากส่วน
ของ LINK ในโหนดปั จจุบนั
13
โครงสร้ างข้ อมูลลิงค์ ลิสต์ (Linked List)
PTR
แสดงการเปลี่ยนพอยน์ เตอร์ เพื่อไปยังโหนดถัดไป ( PTR = LINK[PTR] )
14
โครงสร้ างข้ อมูลลิงค์ ลิสต์ (Linked List)
ขัน้ ตอนการเข้ าถึงข้ อมูลในโครงสร้ าง
การเข้ าถึงในโครงสร้ างเรี ยกว่า การทา Traversing มีขนตอนดั
ั้
งต่อไปนี ้
กาหนดให้ DATA เป็ นโครงสร้ างข้ อมูลลิงค์ลิสต์ และพอยน์เตอร์ PTR
ทาหน้ าที่ชี ้โหนดที่กาลังดาเนินการ Process อยูใ่ นขณะนัน้ (Current Node)
1. กาหนดค่าเริ่มต้ นให้ กบั พอยน์เตอร์ PTR.
2. การวนรอบดาเนินการ Process ข้ อมูล
3. Apply Process to DATA [PTR]
4. เปลี่ยนค่าพอยน์เตอร์ PTR ให้ ชี ้โหนดถัดไป
5. เสร็จสิ ้นขันตอน
้
15
โครงสร้ างข้ อมูลลิงค์ ลิสต์ (Linked List)
Start
Set PTR = Start
PTR = NULL
Yes
Stop
No
Apply Process to DATA[PTR]
Set PTR = LINK[PTR]
16
โครงสร้ างข้ อมูลลิงค์ ลิสต์ (Linked List)
การสร้ างโหนดและกาหนดโครงสร้ าง
การสร้ างโหนด คือ การเตรี ยมโครงสร้ างระเบียนสาหรับจัดเก็บ
ข้ อมูล เมื่อกาหนดโครงสร้ างของโหนดแล้ วก็สามารถกาหนดพอยน์เตอร์ และ
เขียนส่วนของโปรแกรมแสดงการประกาศโครงสร้ าง ดังนี ้
struct node
{
int num ;
struck node *Link ;
} *Start, *Ptr ;
เมื่อ *Start คือ พอยน์เตอร์ ที่ทาหน้ าที่ชี ้ตาแหน่งของโหนดแรกในโครงสร้ าง
*Ptr คือ พอยน์เตอร์ ที่ทาหน้ าที่ชี ้ตาแหน่งของโหนดปั จจุบนั
17
โครงสร้ างข้ อมูลลิงค์ ลิสต์ (Linked List)
Storage Pool
Storage Pool หรื อ Free List หมายถึง เนื ้อที่วา่ งในหน่วยความจา
มีลกั ษณะเป็ นโหนดเก็บอยูใ่ นโครงสร้ างข้ อมูลลิงค์ลสิ ต์ หรื ออาจเรี ยกได้ วา่
เป็ น Free Stack ลักษณะการดาเนินการเหมือนกับโครงสร้ างข้ อมูลสแต็ก
เมื่อมีการเพิ่มสมาชิกใหม่ในโครงสร้ างข้ อมูลลิงค์ลิสต์จะนาโหนด
ว่าง 1 โหนดออกมาจาก Free List (เป็ นโหนดแรกใน Free List) จากนันใส่
้
ข้ อมูลลงไปในส่วนของ Data Field หลังจากนัน้ นาโหนดดังกล่าวเชื่อมโยงเข้ า
ไปไว้ ในโครงสร้ างข้ อมูลที่ต้องการ และหากมีการลบสมาชิกตัวใดตัวหนึง่ ออก
จากโครงสร้ างจะต้ องนาโหนดที่ถกู ลบนี ้ใส่คืนใน Free List ไว้ เป็ นโหนดแรกใน
Free List เสมอ
18
โครงสร้ างข้ อมูลลิงค์ ลิสต์ (Linked List)
START
DATA LIST
p
AVAIL
q
FREE LIST
P
P
แสดงโครงสร้ างลิงค์ ลิสต์ ของ Free Storage List
Charter 4
โครงสร้ างข้ อมูลลิงค์ ลิสต์ (Linked List)
Step (a) : NEW Avail
AVAIL
…..
NULL
…..
NULL
…..
NULL
NEW
Step (B) : Avail Link(Avail)
NEW
AVAIL
Step (C) : NEW NULL
NEW
AVAIL
ขัน้ ตอนการขอ New Node (Get Node)
1
9
20
โครงสร้ างข้ อมูลลิงค์ ลิสต์ (Linked List)
การเพิ่มข้ อมูลในโครงสร้ าง
เมื่อกาหนดโครงสร้ างข้ อมูลเรี ยบร้ อยแล้ ว ก็สามารถทาการเพิ่ม
ข้ อมูลในโครงสร้ างได้ โดยการขอโหนดว่างจาก free list และนามา
เชื่อมโยงกับรายการข้ อมูลที่มีอยูเ่ ดิมในโครงสร้ างตรงตาแหน่งที่ต้องการ
การเพิ่มข้ อมูลในโครงสร้ างข้ อมูลลิงค์ลิสต์ อาจเกิดในลักษณะที่
ต่างกัน ซึง่ สรุปได้ เป็ น 3 ลักษณะ คือ
1. การเพิ่มข้ อมูลที่จดุ เริ่มต้ นของโครงสร้ าง
2. การเพิ่มข้ อมูลต่อจากโหนดที่กาหนด
3. การเพิ่มข้ อมูลที่จดุ สุดท้ ายของโครงสร้ าง
21
โครงสร้ างข้ อมูลลิงค์ ลิสต์ (Linked List)
การเพิ่มข้ อมูลที่จุดเริ่มต้ นของโครงสร้ าง
เป็ นการเพิ่มโหนดของข้ อมูลไปยังตาแหน่งแรกของโครงสร้ างลิงค์
ลิสต์ โดยการเปลี่ยนค่าเริ่มต้ นให้ ชี ้ไปยังตาแหน่งของโหนดใหม่ (NEW Node)
ที่สร้ างขึ ้น และให้ Pointer ของโหนดใหม่ชี ้ไปยังตาแหน่งเริ่มต้ นเดิมแทน
22
โครงสร้ างข้ อมูลลิงค์ ลิสต์ (Linked List)
START
…..
NEW
NEW คือ โหนดว่ างที่ได้ จาก Storage Pool
แสดงการเพิ่มข้ อมูลที่จุดเริ่มต้ นของโครงสร้ าง
23
โครงสร้ างข้ อมูลลิงค์ ลิสต์ (Linked List)
ขัน้ ตอนการเพิ่มข้ อมูลที่ตาแหน่ งเริ่มต้ นของโครงสร้ าง
1. ตรวจสอบ OVERFLOW ถ้ าโหนดใหม่มีคา่ เป็ น NULL แสดงว่า
OVERFLOW
2. กาหนด PTR ให้ ชี ้ไปที่โหนดของ FREE LIST
3.ใส่ข้อมูลใหม่ลงไปในโหนดใหม่
4.ให้ โหนดใหม่ชี ้ไปยังโหนดเริ่มต้ นเดิมและเปลี่ยนตาแหน่งเริ่มต้ นให้
ชี ้ไปยังโหนดใหม่
24
โครงสร้ างข้ อมูลลิงค์ ลิสต์ (Linked List)
การเพิ่มข้ อมูลต่ อจากโหนดที่กาหนด
เป็ นการแทรกโหนดข้ อมูลใหม่เข้ าไประหว่างโหนดข้ อมูล 2 โหนด
โดยการเปลี่ยน Pionter ที่ชี ้โหนดเก่าให้ ชี ้ไปยังตาแหน่งของโหนดใหม่ และ ให้
Poinnter ของโหนดใหม่ขี ้ไปยังตาแหน่งเดิมแทน
25
โครงสร้ างข้ อมูลลิงค์ ลิสต์ (Linked List)
Start
NEW
p
q
แสดงการเพิ่มข้ อมูลต่ อจากโหนดที่กาหนด
26
โครงสร้ างข้ อมูลลิงค์ ลิสต์ (Linked List)
ขัน้ ตอนการเพิ่มข้ อมูลที่ตาแหน่ งโหนดที่กาหนดของโครงสร้ าง
1. ตรวจสอบ OVERFLOW ถ้ าโหนดใหม่มีคา่ เป็ น NULL แสดงว่า
OVERFLOW
2. กาหนด PTR ให้ ชี ้ไปที่โหนดของ FREE LIST
3. ใส่ข้อมูลใหม่ลงไปในโหนดใหม่
4. กาหนดค่าให้ โหนดแรก ถ้ า PTR = NULL ให้ กาหนดโหนดใหม่เป็ น
จุดเริ่มต้ น ถ้ า PTR <> NULL ให้ นาโหนดใหม่มาต่อ (PTR ชี ้ไปที่โหนดใหม่)
27
โครงสร้ างข้ อมูลลิงค์ ลิสต์ (Linked List)
การเพิ่มข้ อมูลเป็ นโหนดสุดท้ ายของโครงสร้ าง
เป็ นการนาโหนดข้ อมูลใหม่มาต่อยังตาแหน่งท้ ายสุดของโครงสร้ าง
(Pointer ของโหนดสุดท้ ายมีคา่ เป็ น NULL) โดยการกาหนดให้ Pointer ของ
โหนดข้ อมูลสุดท้ าย ชี ้ไปยังโหนดใหม่ และให้ Pointer ของ โหนดใหม่มีคา่ เป็ น
NULL แทน
28
โครงสร้ างข้ อมูลลิงค์ ลิสต์ (Linked List)
Start
NEW
NULL
p
q
แสดงขัน้ ตอนการเพิ่มข้ อมูลเป็ นโหนดสุดท้ ายของโครงสร้ าง
29
โครงสร้ างข้ อมูลลิงค์ ลิสต์ (Linked List)
ขัน้ ตอนการเพิ่มข้ อมูลเป็ นโหนดสุดท้ ายของโครงสร้ าง
1. ตรวจสอบ OVERFLOW ถ้ าโหนดใหม่มีคา่ เป็ น NULL แสดงว่า
OVERFLOW
2. กาหนด PTR (ที่อยูต่ าแหน่งสุดท้ าย) ให้ ชี ้ไปที่โหนดของ FREE
LIST
3. ใส่ข้อมูลใหม่ลงไปในโหนดใหม่
4. กาหนด PTR ของโหนดใหม่มีคา่ เป็ นน NULL
โครงสร้ างข้ อมูลลิงค์ ลิสต์ (Linked List)
3
0
การลบข้ อมูลจากโครงสร้ าง
การลบข้ อมูลจากโครงสร้ าง หมายถึง การดึงเอาโหนดที่ต้องการลบ
ออกจากลิงค์ลิสต์ชดุ เดิม ดังนัน้ การเปลี่ยนแปลงที่เกิดขึ ้นคือ การเปลี่ยนค่า
พอยน์เตอร์ และเมื่อทาการลบข้ อมูลออกจากโครงสร้ างแล้ วจะต้ องคืนโหนดที่
ถูกลบให้ กบั Storage Pool เพื่อที่จะได้ สามารถนาหน่วยความจาส่วนนันไปใช้
้
งานต่อไป
การลบข้ อมูลออกจากโครงสร้ างลิงค์ลิสต์ เกิดขึ ้นได้ หลายลักษณะ
สรุปได้ ดงั นี ้
1. การลบโหนดแรก
2. การลบโหนดที่อยูห่ ลังโหนดที่กาหนด
3. การลบโหนดสุดท้ าย
31
โครงสร้ างข้ อมูลลิงค์ ลิสต์ (Linked List)
Start
แสดงการลบโหนดออกจากโครงสร้ างข้ อมูลลิงค์ ลสิ ต์
p
Start
x
q
x
q
ก) ก่ อนลบข้ อมูล
p
ข) หลังการลบข้ อมูล
32
โครงสร้ างข้ อมูลลิงค์ ลิสต์ (Linked List)
Start
p
x
q
Avail
แสดงการลบโหนดและส่ งโหนดคืนกลับ Storage Pool
33
โครงสร้ างข้ อมูลลิงค์ ลิสต์ (Linked List)
ขัน้ ตอนการลบโหนดมีดังนี ้
1. เก็บค่าตาแหน่งและค่าของ Pointer ของโหนดที่ต้องการล
2. กาหนดค่าของ Pointer ของโหนดที่ต้องการลบ ไปยังโหนดก่อน
หน้ านัน้
3. กาหนดตาแหน่งของโหนดที่ต้องการลบคืนกลับไปยัง Storage
Pool
34
โครงสร้ างข้ อมูลลิงค์ ลิสต์ (Linked List)
ประเภทของโครงสร้ างข้ อมูลลิงค์ ลสิ ต์
โครงสร้ างข้ อมูลลิงค์ลิสต์ แบ่งเป็ น 2 กลุม่ ใหญ่ ๆ ได้ แก่
1. โครงสร้ างข้ อมูลลิงค์ลิสต์เดี่ยว (Singly Linked List : SLL)
2. โครงสร้ างข้ อมูลลิงค์ลิสต์คู่ (Doubly Linked List : DLL)
35
โครงสร้ างข้ อมูลลิงค์ ลิสต์ (Linked List)
โครงสร้ างข้ อมูลลิงค์ ลสิ ต์ เดี่ยว (SLL)
แบ่งออกเป็ น 2 ประเภท
1. โครงสร้ างข้ อมูลลิงค์ลิสต์แบบ Ordinary Singly Linked List คือ
โครงสร้ างข้ อมูลลิงค์ลิสต์ที่มีลกั ษณะเหมือนกับโครงสร้ างข้ อมูลลิงค์ลิสต์ที่
กล่าวมาแล้ วตังแต่
้ ต้น
2. โครงสร้ างข้ อมูลลิงค์ลิสต์แบบ Circular Singly Linked List
(CLL) มีลกั ษณะคล้ ายกับแบบ SLL ทัว่ ไป เพียงแต่พอยน์เตอร์ สามารถชี ้
กลับมายังตาแหน่งเริ่มต้ นของโครงสร้ างได้ โดยใช้ พอยน์เตอร์ ของโหนด
สุดท้ ายในโครงสร้ างชี ้ไปยังโหนดแรก ทาให้ โครงสร้ างข้ อมูลมีลกั ษณะเป็ น
วงกลม
36
โครงสร้ างข้ อมูลลิงค์ ลิสต์ (Linked List)
START
…..
แสดงลักษณะของ Circular Singly Linked List
HEAD
แสดงลักษณะของ Empty Circular Singly Linked List
37
โครงสร้ างข้ อมูลลิงค์ ลิสต์ (Linked List)
โครงสร้ างข้ อมูลลิงค์ ลสิ ต์ ค่ ู (Doubly Linked List)
โครงสร้ างข้ อมูลลิงค์ลิสต์คู่ (Doubly Linked List) เป็ นโครงสร้ างที่
แต่ละโหนดข้ อมูลสามารถชี ้ตาแหน่งโหนดข้ อมูลถัดไปได้ 2 ทิศทาง (มีพอยน์
เตอร์ ชี ้ตาแหน่งอยูส่ องทิศทาง) โดยมีพอยน์เตอร์ อยู่ 2 ตัว คือ พอยน์เตอร์
LLINK ทาหน้ าที่ชี ้ไปยังโหนดด้ านซ้ ายของโหนดข้ อมูลนัน้ ๆ และ พอยน์เตอร์
RLINK ทาหน้ าที่ชี ้ไปยังโหนดด้ านขวาของโหนดข้ อมูลนัน้ ๆ
LLINK
DATA
RLINK
38
โครงสร้ างข้ อมูลลิงค์ ลิสต์ (Linked List)
การใช้ งานของโหนดข้ อมูลแบบลิงค์ลิสต์คู่ คือ พอยน์เตอร์ LLINK
จะชี ้ไปยังโหนดด้ านซ้ ายของโหนดข้ อมูลนัน้ ๆ โดยพอย์เตอร์ ที่โหนดข้ อมูล
สุดท้ ายทางด้ านซ้ าย (LLINK ตัวสุดท้ าย) จะมีคา่ เป็ น NULL และ พอยน์เตอร์
RLINK ทาหน้ าที่ชี ้ไปยังโหนดด้ านขวาของโหนดข้ อมูลนัน้ ๆ โดยพอย์เตอร์ ที่
โหนดข้ อมูลสุดท้ ายทางด้ านขวา (RLINK ตัวสุดท้ าย) จะมีคา่ เป็ น NULL
เช่นกัน
LLINK
DATA
RLINK
LLINK
DATA
RLINK
LLINK
DATA
ลักษณะการทางานของโครงสร้ างลิงค์ ลสิ ต์ ค่ ู (Doubly Linked List)
RLINK
39
โครงสร้ างข้ อมูลลิงค์ ลิสต์ (Linked List)
ชนิดของโครงสร้ างข้ อมูลลิงค์ลิสต์แบบ Doubly Linked List
แบ่งออกเป็ น 2 แบบ คือ
1. โครงสร้ างข้ อมูลลิงค์ลิสต์แบบ Ordinary Doubly Linked
List(ODLL)
2. โครงสร้ างข้ อมูลลิงค์ลิสต์แบบ Circularly Doubly Linked List
(CDLL)
40
โครงสร้ างข้ อมูลลิงค์ ลิสต์ (Linked List)
โครงสร้ างข้ อมูลลิงค์ ลสิ ต์ แบบ Ordinary DLL
โครงสร้ างข้ อมูลลิงค์ลิสต์แบบ Ordinary DLL คือ ลักษณะของ
โครงสร้ างลิงค์ลิสต์ที่สว่ นของพอยน์เตอร์ ที่ link ทางซ้ าย (LLINK) ของโหนด
ซ้ ายมือสุดและพอยน์เตอร์ ที่ link ทางด้ านขวาสุดของโครงสร้ าง (RLINK) มี
ค่าเป็ น NULL ทังคู
้ ่ เพื่อแสดงว่าเป็ นโหนดสุดท้ ายของโครงสร้ างที่ปลายทัง้
สองด้ าน
LLINK DATA
NULL
HEAD
RLINK
LLINK DATA
RLINK
LLINK DATA
RLINK
NULL
41
โครงสร้ างข้ อมูลลิงค์ ลิสต์ (Linked List)
p
q
n
แสดงการเพิ่มโหนดข้ อมูลเข้ าสู่โครงสร้ าง Ordinary DLL
42
โครงสร้ างข้ อมูลลิงค์ ลิสต์ (Linked List)
ขันตอนการเพิ
้
่มโหนดข้ อมูลมีดงั นี ้
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
43
โครงสร้ างข้ อมูลลิงค์ ลิสต์ (Linked List)
ขันตอนการลบโหนดมี
้
ดงั นี ้
1. ตรวจสอบว่ามีข้อมูลหรื อไม่ (ถ้ าโหนด r และ l มีคา่ เป็ น start
แสดงว่าไม่มีข้อมูล)
2. ถ้ ามีข้อมูล ให้ กาหนดพอยน์เตอร์ ของ p และ q
p -> r = d -> r
q -> l = d -> l
3. คืนโหนดที่ลบให้ กบั ระบบ
44
โครงสร้ างข้ อมูลลิงค์ ลิสต์ (Linked List)
โครงสร้ างข้ อมูลลิงค์ ลสิ ต์ แบบ Circularly DLL
โครงสร้ างข้ อมูลลิงค์ลิสต์แบบ Circularly DLL คือ ลักษณะของ
Doubly linked list ที่มี Link ทางซ้ าย (LLINK) ของโหนดซ้ ายมือสุดเก็บ
ตาแหน่งที่อยูข่ องโหนดที่อยูท่ างขวามือสุดและ Link ทางด้ านขวา (RLINK)
ของโหนดขวามือสุดก็จะเก็บตาแหน่งที่อยูข่ องโหนดที่อยูท่ างซ้ ายมือสุด
45
โครงสร้ างข้ อมูลลิงค์ ลิสต์ (Linked List)
LLINK
DATA
RLINK
LLINK
DATA
RLINK
LLINK
NULL
Start
แสดงโครงสร้ างข้ อมูลลิงค์ ลสิ ต์ แบบ Circularly DLL
DATA
RLINK

similar documents