ลิงค์ลิสต์แบบเชิงเส้น เป็นลิงค์ลิสต์ที่หากจะเข้าถึงทุกๆโหนดในลิสต์จำเป็นต้องเริ่มต้นจากที่หัวของลิงค์ลิสต์นั้นเสมอ ปัญหาก็คือหากมีพอยเตอร์ start เพียงพอยเตอร์เดียวชี้อยู่ที่โหนดใดๆในลิสต์นั้น เราสามารถเข้าถึงข้อมูลได้เฉพาะโหนดที่อยู่ตั้งแต่ start ชี้เป็นต้น แต่ไม่สามารถเข้าถึงโหนดที่อยู่ก่อนหน้าstartได้
ทางเลือกหนึ่งซึ่งสามารถแก้ปัญหาข้างต้นได้ คือ เราอาจใช้วิธีเชื่อมโยงฟิลด์ next ของโหนดท้ายสุด ซึ่งเดิมเก็บค่า NULL ให้เปลี่ยนไปชี้ยังโหนดแรก ดังภาพ
Yupa Sudan Dara Arun
root
head
ลิงค์ลิสต์ข้างต้นมีลักษณะวนเป็นวงกลม เราเรียกลิงค์ลิสต์นี้ว่าลิงค์ลิสต์แบบวงกลม จะเห็นได้ว่าแต่ละโหนดก่อนหน้าและโหนดตามหลัง ยกเว้นกรณีลิงค์ลิสต์ว่างเปล่าเท่านั้นที่ head จะเป็น NULL จึงไม่มีโหนดก่อนหน้าหรือโหนดตามหลัง
วิธีการแทรกโหนดที่ชี้โดย p เข้าไปในลิงค์ลิสต์ที่ว่างเปล่า เพื่อให้ลิงค์ลิสต์มีลักษณะเป็นวงกลม
If (head = = NULL
{
head = p ;
head -> next = head ;
}
ภาพที่ได้
|
|
|
Arun |
head
p
ข้อดีของลิงค์ลิสต์แบบวงกลมก็คือ เราสามารถเข้าถึงทุกๆโหนดในลิสต์ได้โดยไม่จำเป็นต้องเริ่มต้นท่องจากโหนดแรกสุกของลิสต์เท่านั้น แต่เราสามารถเริ่มต้นจากท่องจากโหนดใดๆในลิสต์ก็ได้ เพราะเมื่อวนมาบรรจบกับโหนดที่เริ่มต้นท่อง นั้นก็แสดงว่าเราได้เข้าถึงทุกๆโหนดในลิสต์แล้ว
จากภาพของลิงค์ลิสต์แบบวงกลมที่ผ่านมา พบว่ามีพอยเตอร์ถึง 2 ตัวที่ชี้อยุ่ที่หัวของลิสต์ ซึ่งไม่ได้ให้ใช้ประโยชน์กับโครงสร้างนี้อย่างเต็มที่ ดังนั้น เพื่อเพิ่มประสิทธิภาพและความสะดวกในการเข้าถึงข้อมูล จึงแนะนำให้ย้าย head แทนที่จะชี้โหนดแรกสุดให้เปลี่ยนไปชี้ยังโหนดท้ายสุดแทน และเนื่องจาก head เป็นพอยเตอร์ที่ไม่ได้ชี้ที่โหนดแรกอีกต่อไป จึงสมควรเปลี่ยนชื่อของตัวแปรนี้ให้เหมาะสม โดยอาจตั้งชื่อใหม่ว่า list แทน
ตัวอย่าง การพิมพ์ทุกโหนดจากลิสต์แบบวงกลมที่มี list ชี้อยู่ที่โหนดสุดท้าย
Void printList (Ptr *lise)
{
Ptr *start ;
If (list = = NULL)
Printf (“The lust is empty\m”) ;
Else
{
start = lust ;
do
{
printf (“%d ” , start -> next -> info) ;
start = start -> next ;
} while (start ! = list ) ;
}
} /*printfList*/
