Linked list
ลิงค์ ลิสต์เป็นการจัดเก็บชุดข้อมูลเชื่อมโยงต่อเนื่องกันไปตามลำดับ ซึ่งอาจอยู่ในลักษณะแบบเชิงเส้นตรง (linear) หรือ ไม่เป็นเส้นตรง (nonlinear) ก็ได้ ซึ่งในลิสต์จะประกอบไปด้วยข้อมูลที่เรียกว่าโหนด (node) ในหนึ่งโหนดจะประกอบด้วยส่วนของข้อมูลที่ต้องการจัดเก็บ เรียกว่าส่วน Info และส่วนที่เป็นพอยน์เตอร์ที่ชี้ไปยังโหนดถัดไป (Link) หรือชี้ไปยังโหนดอื่นๆที่อยู่ในลิสต์ หากไม่มีโหนดที่อยู่ถัดไป ส่วนที่เป็นพอยน์เตอร์หรือ Link จะเก็บค่า NULL หรือ NILL ใช้สัญลักษณ์ ^
โหนด (Node)

โครง สร้างแบบ Linked list แบ่งได้หลายแบบตามวิธีการชี้ไปยังโหนดต่างๆ เช่น Singly Linked list , Doubly Linked list , Multi-Linked list


Singly Linked list จะประกอบด้วยโหนดที่มีพอยน์เตอร์ชี้ไปในทิศทางเดียว คือชี้ไปยังโหนดถัดไป

จาก รูปหากทราบถึงโหนดแรกของ Linked list จะสามารถเข้าถึงข้อมูลทั้งหมดใน Linked list ได้ เนื่องจากแต่ละโหนดจะมีพอยน์เตอร์ที่ชี้ไปยังโหนดถัดไป ดังนั้น Linked list ต้องมี external พอยน์เตอร์ที่ชี้ไปยังโหนดแรกของ Linked list จากรูปใช้พอยน์เตอร์ H (Head)


 Linked list ประกอบไปด้วย node ซึ่งมีข้อมูลของแต่ละ node อยู่ประกอบไปด้วย ข้อมูลและตัวที่บ่งชี้ถึงโหนดต่อไป หากเป็นโหนดสุดท้ายจะมีค่าเป็น null ในภาษา java เราสามารถอ้างถึง reference ได้โดย object จึงสามารถที่จะสร้าง linked list ได้เช่นกันเหมือนกับภาษา C หรืออื่นๆเปรียบเสมือนกับ element เป็นตัวเก็บข้อมูล และ next ทำหน้าที่ในการชี้ถึงโหนดอื่น ๆ ต่อไป

การสร้าง Linked List


 วิธี สร้าง Linked list คือการนำข้อมูลที่จะจัดเก็บเข้า Linked list เพิ่มตรงโหนดตำแหน่งสุดท้ายของลิสต์ ฉะนั้นจึงต้องมี External พอยน์เตอร์ที่คอยชี้โหนดสุดท้ายของลิสต์ ในที่นี้ใช้ L (Last)
 ตัวอย่างการสร้าง Linked list จากลิสต์ L = 21 , 5 , 14
เริ่มจากการให้ H ชี้ทิ่โหนดตำแหน่งแรก และ L ชี้ทิ่โหนดตำแหน่งสุดท้าย
เพิ่มข้อมูล 5 เข้าไปใน list , L ชี้ไปยังโหนดที่เก็บข้อมูล 5
เพิ่มข้อมูล 14 เข้าไปใน list , L ชี้ไปยังโหนดที่เก็บข้อมูล 14



 การเพิ่มและลบข้อมูลใน Linked list


การเพิ่มข้อมูลที่ต้น list

จากรูป จะเพิ่ม NODE(tmp) ลงใน linked list โดยมีขั้นตอนคือ

tmp = new ListNode();
tmp.element = 12;
tmp.next = current.next;

การเพิ่มข้อมูลโดยแทรกลงในลิสต์

การเพิ่มข้อมูลจะทำการแทรกโหนด NEW หลังโหนด P
ตัวอย่าง ทำการเพิ่มข้อมูลโหนด 16 ระหว่างโหนด 21 และ 5

จากรูปมีขั้นตอนดังนี้
tmp = new ListNode();
tmp.element = 16;
tmp.next = current.next;
current.next = tmp;


การลบข้อมูลใน Linked list
การลบข้อมูลที่ต้น list

เนื่อง จากขั้นตอนของการลบข้อมูลที่ header นั้นจะมีปัญหาที่ยุ่งยากกว่าเมื่อ design ด้วย oop(java) เราสามารถที่จะแก้ปัญหานี้ได้โดยการใส่ header node ที่ว่าง ๆ ไว้ข้างหน้าของ linked list เพื่อที่จะทำหน้าที่เป็นชี้ว่าเป็นหัวโหนดโดยที่ไม่ต้องมี pointer คอยชี้ที่ header และเมื่อเราต้องการที่จะเปลี่ยนแปลงข้อมูลใด ๆ บนหัวสามารถที่จะทำได้โดยการแทรก node เข้าไปดังตัวอย่างของการแทรกข้อมูลข้างล่าง


การแทรกข้อมูลลงในโหนดที่ต้องการ

จากรูปมีขั้นตอนดังนี้
tmp.next = tmp.next.next;

0 ความคิดเห็น:

แสดงความคิดเห็น