เรื่อง Linked List
ลิงค์ลิสต์เป็นการจัดเก็บชุดข้อมูลเชื่อมโยงต่อเนื่องกันไปตามลำดับ ซึ่งอาจอยู่ในลักษณะแบบเชิงเส้นตรง (linear) หรือ ไม่เป็นเส้นตรง (nonlinear) ก็ได้ ซึ่งในลิสต์จะประกอบไปด้วยข้อมูลที่เรียกว่าโหนด (node) ในหนึ่งโหนดจะประกอบด้วยส่วนของข้อมูลที่ต้องการจัดเก็บ เรียกว่าส่วน Info และส่วนที่เป็นพอยน์เตอร์ที่ชี้ไปยังโหนดถัดไป (Link) หรือชี้ไปยังโหนดอื่นๆที่อยู่ในลิสต์ หากไม่มีโหนดที่อยู่ถัดไป ส่วนที่เป็นพอยน์เตอร์หรือ Link จะเก็บค่า NULL หรือ NILL ใช้สัญลักษณ์ ^
โหนด (Note)
โครงสร้างแบบ 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 หรืออื่นๆ
Circular Linked list
ในปกติ Linked list เมื่อถึงโหนดสุดท้าย ค่าในฟิลด์ LINK หรือ โหนดถัดไปจะมีค่าเป็น NULL ซึ่งเราสามารถใช้ประโยชน์ได้โดยการเปลี่ยนให้ ค่า NULL ในฟิลด์ LINK เป็นตำแหน่งของโหนดแรกในลิสต์ หรือชี้ไปที่ต้นลิสต์ใหม่นั่นเอง ซึ่งเราจะเรียก Linked list แบบนี้ว่า Circular Linked listCircular Linked list ใช้ประโยชน์เมื่อต้องการให้ข้อมูลมีลักษณะเป็นวนรอบหรือลูป โดยแต่ละขั้นตอนจะมีการทำงานภายในลูป จะมีการย้ายตำแหน่งของพอยน์เตอร์ไปยังโหนดถัดไปใน Linked list ในลักษณะแบบวงกลม
Doubly linked list ประกอบด้วยส่วนของ Info และ พอยน์เตอร์ที่ชี้ไป 2 ทิศทาง คือ ชี้ไปยังโหนดถัดไป และชี้ไปยังโหนดก่อนหน้า ดังนั้นเราจึงสามารถทำการอ่านข้อมูลได้ 2 วิธี คือ การอ่านไปข้างหน้า และอ่านไปทางข้างหลัง
*********************************************************************************
ไม่มีความคิดเห็น:
แสดงความคิดเห็น