Google         youtube            psv            สพม.11

ลิ้งค์ลิสต์ทางเดียว

โดยทั่งไปลิ้งค์ลิสต์จะมีโหนดที่มี ส่วนการเชื่อมต่อชี้ไปยังโหนดถัดไปเพียงทาง เดียว (Unidirectional)         ดังที่ผ่านมา เรียกว่าลิ้งค์ลิสต์ทางเดียว (Singly Linked List ) ซึ่งนอกจากจะมีชุดปฏิบัติการแทรกและลบโหนดแล้วยังมีอัลกอรึทึมในการจัดการ ลิงค์แบบอื่น ๆ ดังนี้

1.การค้นหาแต่ละโหนด เป็นการเริ่มต้น ที่โหนดแรกจากนั้นหาไปทีละโหนดตามลำดับที่เชื่อมต่อกันจนกว่าจะพบโหนดใน ลิงค์ลิสต์ อัลกอริทึมการวิ่งไปยังแต่ละโหนดในลิ้งค์ลิสต์

2.การแทรกโหนดที่ตอนต้นลิ้งค์ลิสต์ เป็น การสร้างโหนดใหม่ขึ้นมาและกำหนดเป็นโหนดแรกของลิ้งค์ลิสต์ โดยโหนดใหม่นี้ ถ้าหากให้การลบโหนดเป็นที่โหนดแรกเช่นกัน ลักษณะการทำงานจะเป็นแบบเดียวกับโครงสร้างข้อมูลสแตก ดังในรูปที่ 6.9 และจำนวนค่าสมาชิกที่ใส่ลงไปก็ไม่จำกัดเหมือนกับการใช้อาร์เรย์

3.การแทรกโหนดที่ตอนต้นลิงค์ลิสต์ เป็น การสร้างโหนดใหม่ขึ้นมาและนำไปต่อจากโหนดสุดท้ายของลิงค์ลิสต์ (Append)โดย โหนดสุดท้ายเดิมจะชี้ไปยังโหนดใหม่ที่กลายเป็นโหนดสุดท้ายแทน ถ้าให้การลบโหนดเป็นที่โหนดแรกทำให้ลักษณะการทำงานจะเป็นแบบเดียวกับโครง สร้างข้อมูลคิว ดังรูปที่ 6.10 โดยมีตัวแปรพอยน์เตอร์ Front ชี้ที่โหนดแรกและ Rear ชี้ที่โหนดสุดท้าย จำนวนค่าสมาชิกที่ใส่ลงไปก็ไม่จำกัดเหมือนกับการใช้อาร์เรย์

4.การสลับด้านของรายการในลิ้งค์ลิสต์ เป็น การสร้างลิงค์ลิสต์ใหม่ให้รายการสลับด้านกับลิ้งค์ลิสต์ตัวเก่า โดยให้โหนดสุดท้ายเปลี่ยนป็นโหนดแรก และให้โหนดแรกกลายเป็นโหนดสุดท้าย นอกจากนี้ยังมีอัลกอรึทึมอื่น ๆ อีก เช่น การรวมสองลิ้งค์ลิสต์เป็นลิ้งค์ลิต์เดียว หรือแยกลิ้งค์ลิสต์เดียวเป็นสองลิ้งค์ลิสต์

ลิ้งค์ลิสต์วงกลม

โดย ปกติการใช้ลิ้งค์ลิสต์ เมื่อตัวแปรพอยน์เตอร์ P ชี้ไปยังโหนดหนึ่งจะไม่สามารถชี้กลับไปยังโหนดก่อน หน้าน้ำได้ วิธีการอย่างหนึ่งที่ทำให้สามารถวิ่งจากโหนดหนึ่งไปยังโหนดอื่น ๆ ได้ในลิงค์ลิสต์ โดยให้ตัวชี้ของโหนดสุดท้ายซึ่งเดิมเป็นค่า NULL ก็ให้ชี้กลับไปยังโหยดแรก แทน ดังในรูปที่ 6.11 และเรียกว่าลิงค์ลิสต์วงกลม (Circular Linked List)

ปัญหา อย่างหนึ่งของการใช้ลิงค์ลิสต์วงกลมคือการวิ่งไปแต่ละโหนดจะเป็นการวนลูปที่ ไม่รู้จบ แนวทางหนึ่งในการแก้ปัญหาคือ การเพิ่มโหนดหัรายการ (Head Node) เข้ามาในตอนต้นหรือตอนท้ายลิงค์ลิสต์วงกลม ดังในรูปที่ 6.12 ซึ่งมีความแตกต่างจากโหนดอื่น ๆ ที่มีข้อมูลพิเศษหรือค่าสัญลักษณ์ (Flag) บอกให้ทราบว่าเป็นโหนดหัวรายการ

การ วิ่งไปแต่ละโหนดจะทราบได้ว่าจุดสิ้นสุดอยู่ตรงไหนโดยใช้โหนดหัวรายการ นอกจากนี้การใช้โหนดหัวรายการ กับลิงค์ลิสต์ทางเดียวช่วยการทำงานมีประสิทธิภาพมากขึ้น เช่น ทุก ๆ โหนดในลิงค์ลิสต์จะมีโหนดก่อนหน้าเสมอ ทำให้อัลกอริทึมในการแทรกหรือลบโหนดมีความสะดวงและง่ายขึ้น เมื่อลิงค์ลิสต์วงกลมว่าง (Empty Circular Linked Lidt) จะมีเพียงโหนดหัวรายการเท่านั้นและมีพอยน์เตอร์ชี้กลับมาที่ตัวเอง ดังในรูปที่ 6.13

ตัวอย่างการใช้ลิ้งค์ลิสต์วงกลม

                ปัญหา โจเซฟ (Josephus Problem) เป็นที่รู้จักกันมากและนำลิงค์ลิสต์วงกลมมาใช้ในการแก้ ปัญหา   เริ่มต้นเมื่อมีทหารกลุ่มหนึ่งถูกข้าศึกล้อมรอบอยู่ในเมืองซึ่งไม่ สามารถต่อสูและหมดหวังที่จะชนะได้ แต่มีม้าเพียงตัวเดียวที่จะขี่พาหนีออกไปได้ กลุ่มทหารจึงตัดสินใจ เลือกคนที่โชคดีขี่ม้าหนีไปโดยการให้ทุกคนนั่งเป็นวงกลม  จากนั้นสุ่มเลือก ชื่อทหารคนหนึ่งเพื่อเริ่มต้นและนับทหารทีละคนในวงกลมจนเท่ากับ  N  ก็ให้ ทหารคนนั้นออกจากวงกลม  และเริ่มต้นนับแบบเดิมเมื่อถึงคนที่  N  ก็ออกจากวง กลมไปเรื่อย ๆ จนจำนวนทหารลดลงเหลือเพียงคนสุดท้ายเป็นผู้ที่ได้ขี่ม้าหนีไป  เช่น  รูป ที่  6.14  มีทหารอยู่  5  คนมีการนับเพื่อคัดออกเท่ากับ  4 จาก รูป  (a)  จะได้คนสุดท้ายคือคนที่เริ่มต้นนับในรูป  (e)

ถ้าเราเป็น ทหารคนหนึ่งควรจะยีนเป็นลำดับเท่าไรจึงจะเป็นคนสุดท้ายโดยมีทะหารทั้ง หมด M คน และจำนวนการนับเพื่อคัดออกเท่ากับ N อัลกอริทึมในการปัญหาดังกล่าวจึงนำ ลิงค์ลิสต์วงกลมมาช่วยดังในตารางที่ 6.4 คือ โปรแกรม Linklist

ลิ้งค์ลิสต์สองทาง

ใน บางครั้งการทำงานกับลิงค์ลิสต์อาจต้องการวิ่งไปยังโหนดต่าง ๆ ในลิงค์ลิสต์โดยการถอยกลับไปยังโหนดก่อนหน้าหรือลบแต่ละโหนด เพื่อห้เกิดประสิทธิภาพจึงนำลิงค์ลิสต์สองทาง (Doubly Linked List) มาใช้แทนลิงค์ลิสต์ทางเดียว ดังในรูปที่ 6.15ซึ่งแต่ละโหนดประกอบด้วย 3 ส่วน คือ

1.ส่วนเก็บข้อมูล (Info) ใช้เก็บข้อมูลข่าวสารที่มีโครงสร้างข้อมูลเบื้องต้นหรือเรียบง่าย

2.ส่วนการเชื่อมต่อถัดไป (Next) เป็นตัวชี้หรือพอยน์เตอร์เก็บค่าแอดเดรสใช้อ้างไปยังโหนดถัดไปในหน่วยความจำ

3.ส่วนการเชื่อมต่อก่อนหน้า เป็นตัวชี้หรือพอยน์เตอร์เก็บค่าแอดเดรสใช้อ้างกลับไปยังโหนดก่อนหน้าในหน่วยความจำ

ลิงค์ ลิสต์สองทางบางครั้งเรียกว่าลิงค์ลิสต์สมมาตร (Symmetrically Linked List) เนื่องจากมีตัวชี้จากสองทิศทาง(Bidirectional) ทั้งด้านซ้ายและขวา เมื่อนำมาใช้เป็นลิงค์ลิสต์สองทางวงกลม (Circular Doubly Linked List) ได้ดังในรูปที่ 6.16 โดยอาจยกเลิกโหนดหัวรายการก็ได้

ในการ ปฏิบัติการจะชี้ไปยังโหนดถัดไปโดยใช้ Next(P) และชี้กลับไปยังโหนดก่อนหน้า โดยใช้ Prior(P) ตัวชี้ทั้งสองมักจะเป็นพอยน์เตอร์ใช้ ชื่อ Right และ Left หรือใช้ s-link (Successor) และ          p-link (Predecessor) ดังนั้นเมื่อมีตัวแปรพอยน์เตอร์ p ชี้ไปยังโหนดใดจะได้ว่า

Next (Prior (P)) = P = Prior (Next (P))

การ ถอยกลับไปหนึ่งโหนดและไปข้างหน้าหนึ่งโหนดก็จะกลับมายังโหนดเดิม หรือไปข้างหน้าหนึ่งโหนดและถอยกลับหนึ่งโหนดก็กลับมายังโหนดเดิมเช่นกัน สำหรับลิงค์ลิสต์สองทางว่าง (Empty Doubly Linked List) มีพอยน์เตอร์ทั้งสองชี้กลับมายังโหนดหัวรายการดังในรูปที่ 6.17 ซึ่ง ไม่มีโหนดอื่นอยู่ในลิงค์ลิสต์ จะได้ว่า

Prior (Head) = Head = Next (Head)

การแทรกโหนดไว้ในลิงค์ลิสต์สองทาง

การแทรกโหนดใหม่เข้าไปไว้ในลิงค์ลิสต์สองทางจะมีอัลกอริทึมดังในตารางที่ 6.5

อัลกอริทึมการแทรกโหนดใหม่ลงในลิงค์ลิสต์สองทาง

ตัวอย่าง ที่ใช้จะเริ่มต้นโดยใช้โหนดใหม่ I ขึ้นในหน่วยความจำ กำหนดส่วนเก็บข้อมูลมีค่า L, ส่วนการเชื่อมต่อ Left และRight มีค่า เป็น NULL ซึ่งเป็นตัวแปรพอยน์เตอร์ New ชี้อยู่ดังในรูปที่ 6.18 และมี ลิงค์ลิสต์สองทางที่มีการแทรกโหนดใหม่เข้ามาระหว่างโหนด 2 เป็นโหนดก่อนหน้า และโหนด 3 เป็นโหนดถัดไป จึงกำหนดให้ตัวแปรพอยน์เตอร์ P ชี้ไปยังโหนด 2 และขั้นตอนในการแทรกประกอบ ด้วยดังต่อไปนี้

(a)    Next(New) = Next(P) กำหนดให้ตัวชี้ Right ของโหนด I เปลี่ยนไปชี้ยังโหนด 3 ซึ่งเป็น ส่วนหลังของการแทรกโหนดใหม่ ในรูปที่ 6.19 และ Prior(New) = P กำหนดให้ตัวชี้ Left ของโหนด I เปลี่ยนไปชี้ยังโหนด 2 ซึ่งเป็นส่วนก่อน หน้าของการแทรกโหนดใหม่

(b)    Next(P) = New กำหนดให้ตัวชี้ Right ของโหนด 2 ที่มีตัวแปรพอยน์เตอร์ P ชี้อยู่ เปลี่ยนไปชี้ที่โหนด I ที่มีตัวแปรพอยน์เตอร์ New ชี้อยู่ ในรูปที่ 6.20 และ Prior(P) = New กำหนดให้ตัวชี้ Left ของโหนด 3 เปลี่ยนไปชี้ยังโหนด I เช่นกัน

เมื่อ มีการแทรกโหนดเสร็จสิ้น โหนด I จะต่อจากโหนด 2 และแทนที่ลำดับของโหนด 3 ซึ่งจะกลายเป็นโหนดที่ 4 ใน การทำงานจะมี 3 โหนดที่เกี่ยวข้องคือ โหนดใหม่ I โหนดที่ตัวแปรพอยน์เตอร์ P ชี้อยู่ และโหนดถัดไป ซึ่งต่างจากลิงค์ลิสต์ทางเดียวที่เกี่ยวข้องเพียง 2 โหนด

การลบโหนดออกจากลิงค์ลิสต์สองทาง

อัลกอริทึมที่นำมาใช้ลบโหนดออกจากลิงค์ลิสต์

ตารางที่ 6.6 อัลกอริทึมการลบโหนดออกจากลิงค์ลิสต์สองทาง

พิจารณา จากตัวอย่างลิงค์ลิสต์สองทางในรูปที่ 6.21 เป็นอัลกอริทึมในการลบโหนดออกจาก ลิงค์ลิสต์สองทาง โดยเริ่มต้นให้ตัวแปรพอยน์เตอร์ P ชี้ไปโหนด 2 ซึ่งเป็นโหนดที่ต้องการลบ และขั้นตอนการลบประกอบด้วย

(a)    Next(Prior(P)) = Next(P) เป็นการใช้ตัวชี้ left ของโหนดที่ต้องการลบอ้างกลับไปยังโหนดก่อน หน้าเพื่อชี้ Right ชี้ไปยังโหนดถัดไปต่อจากโหนดที่ต้องการลบ ในรูปที่ 6.22

(b)    Prior(Next(P)) = Prior(P) เป็นการใช้ตัวชี้ Right ขอองโหนดที่ต้องการลบอ้างไปยังโหนดถัดไป เพื่อสร้างตัวชี้ Left ชี้กลับไปยังโหนดก่อนหน้าโหนดที่ต้องการลบในรูป ที่ 6.23

(c)    Free(P) หลังจากนั้นจึงปลดปล่อยโหนดที่ต้องการลบซึ่ง มีตัวแปรพอยน์เตอร์ P ชี้อยู่ เพื่อคืนพื้นที่หน่วยความจำของโหนดที่ลบไปและนำไปใช้กับงานอื่น ได้ (Reuse) ได้เป็นรูปที่ 6.24

ลำดับการทำงานจะมี 3 โหนดที่มาเกี่ยว ข้อง คือ โหนดที่ต้องการลงมีตัวแปรพอยน์เตอร์ P โหนดก่อนหน้าและโหนดถัดไป ส่วนโหนดอื่น ๆ ไม่ถูกเรียกใช้งานหรือเปลี่ยนแปลง

ลิ้งค์ลิสต์หลายทาง

มี อยู่หลายกรณีที่นำลิงค์ลิสต์มาใช้งานตามความเหมาะสมซึ่งแต่ละโหนดจะถูกกำหนด ให้ส่วนการเชื่อมต่อมีมากกว่าสองทางเรียกว่าลิงค์ลิสต์หลายทาง (Multi- linked List) อย่างเช่นในรูปที่ 6.25 ที่แต่ละโหนดในลิงค์ลิสต์จะมีตัวชี้สามทางโดย มีพื้นฐานเป็นลิงค์ลิสต์สองทางซึ่งมีส่วนเก็บข้อมูลคือ NameLength เก็บค่า ความยาวของสตริง กับส่วนเชื่อมต่อที่เป็นตัวชี้ Right และ Left และส่วนที่เชื่อมต่อที่สาม คือ ตัวชี้ NamePtr ใช้ชี้ไปยังข้อมูลจริงอีกทีซึ่งมีโครงสร้างข้อมูลสตริงเก็บ ไว้ในหน่วยความจำที่ขอมาแทนการเก็บไว้ภายในโหนด

ลิงค์ลิสต์หลายทางจะ เป็นลักษณะพื้นฐานของโครงสร้างของข้อมูลอื่นที่จะกล่าวในบทต่อ ๆ ไป เช่น ทรี (Tree) กราฟ(Graph) และนำไปใช้จัดการกับแฟ้มข้อมูล (File)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s