ลิงค์ลิสต์
ลิงค์ ลิสต์ (Linked
List)
ลิงค์ลิสต์
เป็นการจัดเก็บชุดข้อมูลเชื่อมโยงต่อเนื่องกันไปตามลำดับซึ่งอาจอยู่ใน
ลักษณะแบบเชิงเส้น (Linear) หรือไม่เป็นเส้นตรง (nonlinear) ก็ได้
ซึ่งในลิสต์จะประกอบไปด้วยโหนด (node)
ในหนึ่งโหนดจะประกอบด้วยส่วนของข้อมูลที่ต้องการจัดเก็บ เรียกว่าส่วน
Info และส่วนที่เป็นพอยน์เตอร์ที่ชี้ไปยังโหนดถัดไป (Link)
หากไม่มีโหนดถัดไป จะเก็บค่า Null ใช้สัญลักษณ์ ^
ลักษณะ
และคุณสมบัติของลิงค์ลิสต์
1.
ลิงค์
ลิสต์เป็นการนำข้อมูลแต่ละโหนดมาจัดเรียงต่อกันเป็นลิสต์ที่มีการเชื่องโยง
กัน
2.
ภายในแต่ละโหนดแบ่งส่วนประกอบ ได้เป็น 2 ฟิวด์ นั่นคือ
ส่วนของข้อมูลและแอดเดรสของโหนดถัดไป
3.
ลิงค์
ลิสต์เป็นการนำข้อมูลแต่ละโหนดมาจัดเรียงกันเป็นลิสต์ โดยสิ่งที่เป็นตำ
กำหนดลำดับก็คือ ฟิลด์แอดเดรสของแต่ละโหนด
4.
การ
เข้าถึงลิงค์ลิสต์เริ่มต้นจะต้องมีพอยต์เตอร์ชี้ไปยังโหนดแรกของลิงค์ลิสต์
เสมอ
5.
ฟิลด์ แอดเดรสของโหนดสุดท้ายจะต้องกำหนดให้เป็น null
ซึ่งเป็นการกำหนดให้จบลิงค์ลิสต์
โดยไม่มีการชี้ไปยังตำแหน่งอื่นใดอีก
6.
ลิงค์ ลิสต์ที่ไม่มีโหนดอยู่ภายในจะเรียกว่า ลิสต์ว่าง (empty
list)
Dynamic Linked List
·
การ ใช้เนื้อที่หน่วยความจำแบบยืดหยุ่น
ไม่ต้องจองเนื้อที่ใช้เนื้อที่เท่าที่ต้องการใช้
·
ใช้ pointer ในการบอกตำแหน่งของข้อมูลตัวต่อไป
Static Linked List
·
สำหรับ บางภาษาไม่มีข้อมูลชนิด pointer เช่น โคบอล ฟอร์แทรน เป็นต้น
จึงต้องใช้ข้อมูลแบบแถวลำดับ (Array)
ในการแทนที่ลิงค์ลิสต์ในหน่วยความจำ
ลักษณะ ของ Linked
List
·
สมาชิก แต่ละตัวจะเรียกว่าโหนด (Node) ประกอบด้วยสมาชิก 2 ส่วน
คือ
1.
ส่วน ของข้อมูล (data)
2.
ส่วน ที่เป็นตำแหน่งที่อยู่ของโหนดตัวต่อไป (Next Address) ใน Linked
List หรืออาจเรียกว่า Pointer
·
เป็น
การนำข้อมูลแต่ละโหนดมาเรียงต่อกันเป็นลิสต์ที่มีการเชื่อมโยงกัน
ประเภท ของ Linked
List
ลิงค์ลิสต์เดี่ยว (Singly Linked
List)
·
ประ กอบด้วยฟิลด์แอดเดรส 1 ฟิลด์ สำหรับชี้ไปยังโหนดถัดไป
·
การ ดำเนินการกับลิสต์จะเริ่มต้นจากโหนดเริ่มต้นไปยังโหนดสุดท้าย
ย้อนกลับไม่ได้
ลิงค์ลิสต์คู่ (Doubly Linked
List)
·
แต่ ละโหนดมีฟิลด์แอดเดรส 2 ฟิลด์
สำหรับชี้ไปยังโหนดถัดไปและชี้ไปยังโหนดก่อนหน้า
·
การ ดำเนินการกับลิสต์สามารถเดินไปข้างหน้าและย้อนกลับได้
การ ดำเนินการกับ Linked
List
การเพิ่มโหนดในลิงค์ลิสต์
1.
การ เพิ่มข้อมูลที่จุดเริ่มต้นของโครงสร้าง
คำสั่งที่ใช้ในการเพิ่มโหนดใหม่ไว้ต้นลิสต์คือ addnode
2.
การ ค้นหาโหนดที่ต้องการในลิสต์
คำสั่งที่ใช้สำหรับการค้นหาโหนดคือ Searchnode
(ชื่อลิสต์,ข้อมูลที่ต้องการค้นหา) เช่น Search(chlist,B); หมายถึง
ให้ค้นหาข้อมูล B ในลิสต์ชื่อ Chlist
3.
การ แทรกโหนดในลิงค์ลิสต์
คำสั่งที่ใช้ในการแทรกโหนดใหม่ไว้ในลิสต์ คือ insafter
(ชื่อลิสต์,ข้อมูลในตำแหน่งที่จะเพิ่มข้อมูลตัวใหม่ต่อท้าย,ข้อมูลที่จะ
เพิ่ม)
4.
การ ลบโหนดออกจากลิสต์ คำสั่งที่ใช้ Delnode
(ชื่อลิสต์,ข้อมูลที่ต้องการลบ); เช่น Delnode
(Numlist,50);
5.
การท่อง ลิสต์ (Display Node) คำสั่งที่ใช้คือ
displaynode(ชื่อลิสต์); เช่น displaynode(Numlist);
หมายถึงให้แสดงข้อมูลในลิสต์ชื่อ Numlist
น่าจะมีการยกตัวอย่างของโครงสร้างลิงลิสต์