สรุปเรื่อง Linked -List
ลิงค์ลิสต์เดี่ยว
รูปแบบการเก็บข้อมูลโดยการใช้โครงสร้างแบบ Linked -List อาจมีการเชื่อมต่อกันเป็นเส้นตรง(linear) หรือไม่เรียงเป็นเส้นตรง ติดต่อกันไป (nonlinear) ในจำนวนที่ไม่แน่นอน เรียกสมาชิก ของลิงค์ลิสต์ว่า "โหนด" (node) แต่ละโหนดไม่จำเป็นต้องมีสมาชิกในตำแหน่งที่ประชิดกัน โครงสร้างของแต่ละโหนดจะประกอบด้วย 2 ส่วน ส่วนแรกบรรจุสารสนเทศของสมาชิก (INFO) ส่วนที่สองบรรจุตำแหน่งของโหนดถัดไป หรือ โหนดที่ตามมาหลัง (LINK) โหนดสุดท้ายของลิงค์ลิส จะไม่มีโหนดตามหลัง หรือลิงค์ไม่มีการเก็บตำแหน่งของโหนดใด ๆ แต่จะเก็บ ค่า NULL แทน (แทนด้วยเครื่องหมาย / ) ซึ่งเป็นสัญญาณว่าสิ้นสุดลิงค์ลิสต์ ลิงค์ลิสต์เดี่ยวจึงหมายถึง ลิงค์ลิสต์ที่ แต่ละโหนดมีลิงค์ตัวเดียว ส่วนลิงค์ลิสต์ใดที่ไม่มีโหนดเลยเรียกว่า ลิสค์ว่าง (empty)
การท่องลิงค์ลิสต์โหนดที่ถูกชี้โดย พอยเตอร์ใด จะมีชื่อเช่นเดียวกับชื่อพอยเตอร์นั้น ในการท่องลิงค์ลิสต์จะเริ่มต้นค้นหาจาก โหนดแรกไปเรื่อย ๆ จนกว่าจะพบโหนดที่ต้องการการแทรกข้อมูลและการลบข้อมูลการแทรกข้อมูลลงในลิงค์ลิสต์ สามารถจะกระทำได้โดยการเปลี่ยนพอยเตอร์บางตัว และค้นหาข้อมูลใน ลิงค์ลิสต์ เพื่อหาตำแหน่งของโหนดที่มาก่อนโหนดที่ต้องการแทรก สิ่งสำคัญในการแทรกข้อมูลในลิงค์ลิสต์ คือ ลำดับการ เปลี่ยนพอยเตอร์การลบโหนดออกจากลิงค์ลิสต์ จะกระทำโดยการเปลี่ยนพอยเตอร์บางตัว เริ่มต้นก็จะต้องหาโหนดที่มาก่อน โหนดที่ต้องการลบ จากนั้นก็ทำการเปลี่ยนพอยเตอร์ ลิสต์พร้อมใช้งานในทางความคิดโหนดทั้งหมด จะเก็บอยู่ ในรายการอิสระ ซึ่งเราเรียกว่า ลิงค์ลิสต์พร้อมใช้งาน (availability list ) หรือ หน่วยเก็บรวม (storage pool ) เมื่อต้องการนำโหนดมาแทรกในลิงค์ลิสต์ ก็จะมีพอยเตอร์ 1 ตัวในการที่จะชี้ไปยังสมาชิกตัวแรกของลิสต์พร้อมใช้งาน แล้วนำหนดอิสระมาจากลิงค์ลิสต์พร้อมใช้งาน และเชื่อมกับ ลิสต์ในตำแหน่งที่ต้องการในขณะเดียวกัน ถ้ามีการลบโหนดออกจากลิสต์ เราก็จะต้องมีการคืนโหนดไปยังลิสต์พร้อมใช้งาน เพื่อให้สามารถจะนำมาใช้ได้ในภายหลัง ลิงค์ลิสวงกลมลิงค์ลิสต์ชนิดนี้ เกิดจากการปรับปรุงค่าลิงค์ลิสต์ เพื่อให้การประมวลผลที่ดีขึ้น โดยการแทนค่าลิงค์ที่เป็น NULL ของโหนดสุดท้ายของลิงค์ลิสต์ด้วยตำแหน่ง ที่อยู่ของโหนดแรก ลิงค์ลิสต์ในลักษณะนี้เราเรียกว่า ลิงค์ลิสต์วงกลม (circular linking linear list ) หรือ ลิสต์วงกลม ( circular list)ลิงค์ลิสต์วงกลม มีประโยชน์กว่าลิงค์ลิสต์ธรรมดามากกล่าวคือ1. ในการเข้าถึงข้อมูล ของโหนดลิงค์ลิสต์วงกลมโหนดทุกโหนด สามารถเข้าถึงได้จากโหนดใด ๆ ที่กำหนดให้ โดยผ่านทางสายโซ่ (ลิงค์ ) ของลิสต์2. ในการลบโหนด ในการค้นหาโหนดที่มาก่อนโหนดใด ๆ สามารถเริ่มต้นค้นหาในโหนดนั้นได้เลย ข้อเสียของลิงค์ลิสต์วงกลม1. ในการประมวลผลหากไม่ระมัดระวัง อาจทำให้การประมวลผลวนรอบซ้ำไม่รู้จบ (infinite loop )จึงต้อง รู้จุดสิ้นสุดของการทำงาน โดยเราจะแทนจุดสุดท้ายของลิงค์ด้วยโหนดพิเศษ ที่ง่ายต่อการจำแนกโหนดในลิสต์วงกลม ซึ่งเราเรียกโหนดพิเศษนี้ว่า " โหนดหัว" (head node) หรือ "หัวลิสต์" (head list ) ของลิสต์วงกลม เทคนิคนี้จะทำให้ ลิสต์ไม่สามรถเป็นลิสต์ว่างได้ ลิงค์ลิสต์คู่ในลิงค์ลิสต์ประเภทนี้จะมีโหนดซึ่งประกอบด้วยลิงค์ลิสต์ 2 ส่วน เพื่อแสดงโหนดที่มาก่อน และโหนดที่มาที หลัง โหนดที่มาก่อนเราเรียกว่า ลิงค์ซ้าย (left link) ซึ่งแทนด้วยพอยเตอร์ LLINK และลิงค์ที่แทนโหนดที่มาหลังเรา เรียกว่า ลิงค์ขวา(rigth ilnk) ซึ่งแทนด้วยพอยเตอร์ RLINK ซึ่งลิงค์ลิสต์ที่ประกอบด้วย คุณสมบัติดังกล่าวเราเรียกว่า "ลิงค์ลิสต์เชิงเส้นคู่ "(double linked linear list) หรือลิงค์ลิสต์คู่ (double linked list) ในแต่ละทิศทาง ไม่ว่าขวาสุด หรือซ้ายสุด จะมีค่า NULL เพื่อแสดงว่าสิ้นสุดลิสต์ในแต่ละทิศทาง การแทรกข้อมูลในลิงค์ลิสต์คู่การพิจารณาแทรกโหนดในลิงค์ลิสต์คู่มีดังกรณีที่จะเป็นไปได้ดังนี้1. เมื่อลิงค์ลิสต์ว่าง ให้แทนโดยการกำหนดให้ พอยเตอร์ L และพอยเตอร์ R ชี้ไปยังตำแหน่งโหนดใหม่ และกำหนดให้ลิงค์ซ้ายและลิงค์ขวาของโหนดใหม่มีค่า NULLblockquote>
2.เมื่อแทรกโหนดใหม่ลงในกึ่งกลางของลิงค์ลิสต์ ลิงค์ลิสต์ก่อนการแทรกและหลังการแทรก ลำดับการเปลี่ยน พอยเตอร์มีความสำคัญมาก หากเปลี่ยนในลำดับที่ไม่ถูกต้องอาจทำให้โหนดที่บรรจุค่าเดิมสูญหายไป3. เมื่อมีการแทรกโหนดใหม่ทางด้านซ้ายของโหนดซ้ายสุดของลิสต์ จะทำให้พอยเตอร์ L มีค่าเปลี่ยนไป การลบข้อมูลอกจากลิงค์ลิสต์คู่ในการลบโหนดประเภทนี้ แตกต่างจากการลบโหนดในลิงค์ลิสเดี่ยวคือไม่จำเป็นต้องมีการค้นหาโหนดที่มาก่อน โหนดที่จะลบ เพียงกำหนดตำแหน่งของโหนดที่จะลบก็สามารถทราบตำแหน่งของโหนดที่มาก่อน และโหนดที่มาทีหลังโหนดนั้นถ้าลิงค์ลิสต์มีโหนดเพียงโหนดเดียว การลบโหนดออกจากลิงค์ลิสต์จะทำให้ได้ลิงค์ลิสต์ว่าง คือพอยเตอร์ซ้ายสุด และขวาสุดจะถูกกำหนดให้มีค่าเป็น NULL หากพิจารณาขั้นตอนการลบข้อมูลและแทรกข้อมูลในลิงค์ลิสต์ แบบลิงค์ลิสต์คู่ สามารถทำให้ง่ายขึ้นได้ คือในกรณีที่ลิงค์ลิสต์ว่าง สามารถกำหนดให้ลิงค์ลิสต์ไม่เคยว่างได้ โดยการกำหนดโหนดพิเศษ ขึ้นมา 1 โหนด ซึ่งจะเป็นโหนดที่มีอยู่ในลิงค์ลิสต์ตลอดเวลา จึงทำให้ลิงค์ลิสต์ว่างมีเพียง 1 โหนด ที่เป็นโหนดพิเศษเท่านั้น ซึ่งเรียกว่าโหนดหัว (Head node)ของลิงค์ลิสต์ และนอกจกนั้นยังสามารถสร้างลิงค์ลิสคู่เป็นลิงค์ลิสต์วงกลมได้ ขั้นตอนวิธีในการแทรกและลบโหนดตามหลังโหนดที่กำหนดให้ใด ๆ จะลดลำดับขั้นตอนให้น้อยลง
สมัครสมาชิก:
ส่งความคิดเห็น (Atom)
ไม่มีความคิดเห็น:
แสดงความคิดเห็น