DTS 04-15-07-2552

สรุปเนื้อหาบทเรียน "Data Structure"
เรื่อง Linked List

Linked List

ลิงค์ลิสต์เป็นการจัดเก็บชุดข้อมูลเชื่อมโยงต่อเนื่องกันไปตามลำดับ

ซึ่งอาจอยู่ในลักษณะแบบเชิงเส้นตรง (linear) หรือ ไม่เป็นเส้นตรง (nonlinear) ก็ได้

ซึ่งในลิสต์จะประกอบไปด้วยข้อมูลที่เรียกว่าโหนด (node)

ในหนึ่งโหนดจะประกอบด้วยส่วนของข้อมูลที่ต้องการจัดเก็บ

เรียกว่าส่วน Info และส่วนที่เป็นพอยน์เตอร์ที่ชี้ไปยังโหนดถัดไป (Link)

หรือชี้ไปยังโหนดอื่นๆที่อยู่ในลิสต์ หากไม่มีโหนดที่อยู่ถัดไป

ส่วนที่เป็นพอยน์เตอร์หรือ Link จะเก็บค่า NULL หรือสัญลักษณ์ ^

โครงสร้างข้อมูลแบบลิงค์ลิสต์จะแบ่งเป็น 2 ส่วน คือ
1. Head Structure จะประกอบไปด้วย 3 ส่วน

ได้แก่ จำนวนโหนดในลิสต์ (Count)

พอยเตอร์ที่ชี้ไปยัง โหนดที่เข้าถึง (Pos)

และพอยเตอร์ที่ชี้ไปยังโหนดข้อมูล แรกของลิสต์ (Head)

2. Data Node Structure จะประกอบไปด้วยข้อมูล
(Data) และพอยเตอร์ที่ชี้ไปยังข้อมูลตัวถัดไป

การสร้าง Linked list
วิธีสร้าง Linked list คือการนำข้อมูลที่จะจัดเก็บเข้า Linked list

เพิ่มตรงโหนดตำแหน่งสุดท้ายของลิสต์ ฉะนั้นจึงต้องมี External พอยน์เตอร์

ที่คอยชี้โหนดสุดท้ายของลิสต์ ในที่นี้ใช้ L (Last)

ตัวอย่างการสร้าง Linked list จากลิสต์ L = 21 , 5 , 14

เริ่มจากการให้ H ชี้ทิ่โหนดตำแหน่งแรก และ L ชี้ทิ่โหนดตำแหน่งสุดท้าย

เพิ่มข้อมูล 5 เข้าไปใน list , L ชี้ไปยังโหนดที่เก็บข้อมูล

เพิ่มข้อมูล 14 เข้าไปใน list , L ชี้ไปยังโหนดที่เก็บ

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

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

tmp.element = 12;

tmp.next = current.next;