โครงสร้างข้อมูลลิงค์ลิสต์
               

     วิธีแก้ปัญหาในการย้ายข้อมูลที่พบในการจัดเก็บที่มีรูปแบบเรียงตามลำดับ

(Sequential)เปลี่ยนมาใช้รูปแบบไม่เรียงตามลำดับ (Non-sequential)ซึ่งรูปแบบการ

เรียงตามลำดับจะมีสมาชิกเรียงต่อเนื่องติดกันในทางตรรกะ (Logical) และทางกายภาพ

(Physical) เป็นแบบเดียวกัน แต่รูปแบบไม่เรียงตามลำดับสมาชิกต่อเนื่องติดกันในทาง

ตรรกะ ส่วนทางกายภาพไม่จำเป็นต้องเหมือนกัน โดยในทางตรรกะจะแสดงด้วยแต่ละ

สมาชิกมีการชี้ (Point) ต้อไปยังสมาชิกตัวถัดไป สมาชิกทุกตัวในรายการจึงถูกเชื่อมต่อ

(Link) เข้าด้วยกัน ดังรูปที่ 6.1 เป็นรายการเชื่อมต่อหรือเรียกว่าลิ้งค์ลิสต์ (Linked List)

มีสมาชิก N ตัว แต่ละสมาชิกเรียกว่าโหนด (Node)


               

     จากรูปที่ 6.1 มีตัวแปรพอยน์เตอร์ First ชี้ไปยังโหนดแรกของรายการ แต่ละโหมดมี

ตัวเชื่อมเป็นพอยน์เตอร์ที่ชี้ไปยังโหนดถัดไปโดยโหนดสุดท้ายมีค่าเป็น NULL แสดงให้

ทราบว่าไม่ได้ชี้ไปยังโหมดถัดไป แต่ละโหนดเป็นโครงสร้างข้อมูลเรคคอร์ด ประกอบ

ด้วยสองส่วน คือ
               

1.ส่วนเก็บข้อมูล (Info)

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

2.ส่วนการเชื่อมต่อ (Next)

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

สำหรับในทางกายภาพของลิ้งค์ลิสต์ แต่ละดหนดไม่จำเป็นต้องอยู่ติดกัน อาจกระจัด

กระจายไปยู่ส่วนไหนก็ได้ในหน่วยความจำโดยมีตัวเชื่อมชี้ไปยังตัวตำแหน่งของโหน

ดถัดไป
               

     ดังที่กล่าวในตอนต้นโครงสร้างสแตกและคิวมีการใช้อาร์เรย์ในการเก็บค่า สมาชิก

ทุกตัวจึงถูกจำกัดให้เป็นชนิดเดียวกัน(Homogenous) ซึ่งแก้ไขโดยเปลี่ยนมาใช้

ลิ้งค์ลิสต์ที่มีโครงสร้างข้อมูลต่างกันได้ นอกจากนี้ยังมีผลดีในการปฏิบัติการแทรกข้อมูล

หรือลบข้อมูล เพียงแต่ย้ายการชี้ของตัวแปรพอยน์เตอร์เท่านั้น ทำให้สมาชิกอื่นไม่มีผล

กระทบ แต่ในกรณีค่าใช้จ่ายแล้วลิงค์ลิสต์จะสูงกว่าที่ต้องใช้พื้นที่เผิ่มมากขึ้นสำหรับ

ส่วนการเชื่อมต่อเพื่อชี้ไปยังโหนดถัดไป และการค้นหาโหนดที่ต้องการใช้เวลามาก

เนื่องจากเป็นการค้นหาเรียงตามลำดับ (Sequential Search) ได้โหนดเดียวโดยเริ่มต้น

ที่โหนดแรกเสมอ

การปฏิบัติการพื้นฐานของลิงค์ลิสต์
               

     สิ่งสำคัญอย่างหนึ่งในการใช้โครงสร้างข้อมูลลิงค์ลิสต์ คือ ตัวแปรพอยน์เตอร์

(Pointer Variable) ซึ่งเก็บค่าเป็นตำแหน่งแอดเดรสในหน่วยความจำ (Memory

Address) ในการปฏิบัติการกับลิ้งค์ลิสต์และให้มีความถูกต้องจะใช้ตัวแปรพอยน์เตอร์ใน

การจัดการเรื่องต่อไปนี้

1.ใช้ทดสอบกับค่า NULL

2.ใช้ทดสอบว่ามีค่าเท่ากับตัวแปรพอยน์เตอร์อื่น

3.กำหนดให้มีค่าเป็น NULL

4.กำหนดให้ชี้ไปยังโหนด
               

ชุดปฏิบัติการของลิ้งค์ลิสต์ที่ทกวานร่วมกับตัวแปรพอยน์เตอร์ มีดังนี้
 

1.Node(P) 

     ส่งโหนดที่ถูกชี้ด้วยต้วแปรพอยน์เตอร์ P กลับมาให้
 

2.INFO(P)

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

3.Next(P) 

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

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

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

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

 


     ตัวอย่างการแทรกโหนดใหม่ไว้ในลิ้งค์ลิสต์ โดยเริ่มต้นสร้างเป็นโหนด I ในหน่วย

ความจำกำหนดส่วนเก็บข้อมูลมีค่า L ส่วนการเชื่อมต่อมี่ค่าเป็น NULL ซึ่งมีตัวแปร

พอยน์เตอร์ New  ชี้อยู่ ดังในรูปที่ 6.2 และมีลิงค์ลิสต์ที่ต้องการแทรกโหนดใหม่เข้า

มาระหว่างโหนด 2 เป็นโหนดก่อนหน้า (Predecessor) และโหนด 3 เป็นโหนดถัดไป

(Successor) ดังนั้นจึงกำหนดให้ตัวแปรพอยน์เตอร์ P ชี้ไปยังโหนด 2 และขั้นตอนใน

การแทรกประกอบด้วย

  1. Next(New) =Next (P)

     กำหนดให้ตัวชี้ของโหนด I เปลี่ยนไปชี้ยังโหนด 3 ซึ่งเป็นส่วนหลังของการแทรก

โหนดใหม่ ในรูปที่ 6.3

 

 

 

 

 

  1. Next(P) =New

 

     กำหนดให้ตัวชี้ของโหนด 2 ที่มีตัวแปรพอยน์เตอร์ P ชี้อยู่เปลี่ยนไปชี้ยังโหนด I ที่มี

ตัวแปรพอยน์เตอร์ New ชี้อยู่ ในรูปที่ 6.4


        เมื่อการแทรกโหนดเสร็จสิ้น โหนด I จะมาต่อจากโหนดก่อนหน้าและแทนที่

ลำดับของโหนดถัดไป การทำงานดังกล่าวจะมีเพียง 2 โหนดที่เดี่ยวขอ้งคือโหนดใหม่ I

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

แปลง

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

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

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

 


     พิจารณาจากตัวอย่างลิ้งค์ลิสต์ในรูปที่ 6.5 ต่อไปนี้ เป็นอัลกอริทึมในการลบโหนด

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

หน้าโหนด 3 ที่ต้องการลบ และชั้นตอนในการลบประกอบด้วย

 (a)       Q = Next (P) เป็นการใช้ตัวแปรพอยน์เตอร์ Q เป็นตัวช่วย กำหนดให้ชี้ไปยัง

โหนด 3 ที่ต้องการลบในรูปที่ 6.6
                  
(b)     Next(P) =Next (Q)  กำหนดให้ตัวชี้ของโหนด 2 ที่มีตัวแปรพอยน์เตอร์ P ชี้อยู

เปลี่ยนไปชี้ยังโหนด 4 ซึ่งเป็นโหนดถัดไปหลังโหนดที่ตัวแปรพอยน์เตอร์ Q ชี้อยู่ ในรูป

ที่ 6.7
 

 (c) Free (Q) หลังจากนั้นจึงปลดปล่อยโหนดที่ต้องการลบซึ่งมีตัวพอยน์เตอร์ Q ชี้อยู่

เพื่อคืนพื้นที่หน่วยความจำของโหนดที่ลบไปและนำไปใช้กับงานอื่นได้ (Reuse)ได้เป็น

รูปที่ 6.8

               

     ลำดับการทำงานดังกล่าวจะเห็นว่ามีเพียง 2 โหนดเท่านั้นที่มาเกี่ยวข้อง คือ โหนด

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

ยกเว้นในกรณีที่ตัวแปรพอยน์เตอร์ P ชี้ไปยังโหนดสุดท้ายไม่สามารถลบโหนดถัดไปได้

ซึ่งต้องมีการไขอัลกอริทึมโดยตรวจสอบก่อนจะทำการลบ
 

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

     โดยทั่งไปลิ้งค์ลิสต์จะมีโหนดที่มีส่วนการเชื่อมต่อชี้ไปยังโหนดถัดไปเพียงทาง

เดียว (Unidirectional)  ดังที่ผ่านมา เรียกว่าลิ้งค์ลิสต์ทางเดียว (Singly Linked List )

ซึ่งนอกจากจะมีชุดปฏิบัติการแทรกและลบโหนดแล้วยังมีอัลกอรึทึมในการจัดการลิงค์

แบบอื่น ๆ ดังนี้
               

1.การค้นหาแต่ละโหนด

     เป็นการเริ่มต้นที่โหนดแรกจากนั้นหาไปทีละโหนดตามลำดับที่เชื่อมต่อกันจนกว่า

จะพบโหนดในลิงค์ลิสต์ดังในตารางที่ 6.3

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


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.c

ตารางที่ 6.4 ตัวอย่างโปรแกรม LinList.c

 

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

     ในบางครั้งการทำงานกับลิงค์ลิสต์อาจต้องการวิ่งไปยังโหนดต่าง ๆ ในลิงค์ลิสต์โดย

การถอยกลับไปยังโหนดก่อนหน้าหรือลบแต่ละโหนด เพื่อห้เกิดประสิทธิภาพจึงนำลิงค์

ลิสต์สองทาง (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
 

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

 


 
     ตัวอย่างที่ใช้จะเริ่มต้นโดยใช้โหนดใหม่ I ขึ้นในหน่วยความจำ กำหนดส่วนเก็บ

ข้อมูลมีค่า L, ส่วนการเชื่อมต่อ Left และ Right มีค่าเป็น NULL ซึ่งเป็นตัวแปร

พอยน์เตอร์ New ชี้อยู่ดังในรูปที่ 6.18 และมีลิงค์ลิสต์สองทางที่มีการแทรกโหนดใหม่

เข้ามาระหว่างโหนด 2 เป็นโหนดก่อนหน้าและโหนด 3 เป็นโหนดถัดไป จึงกำหนดให้

ตัวแปรพอยน์เตอร์ P ชี้ไปยังโหนด 2 และขั้นตอนในการแทรกประกอบด้วยดังต่อไปนี้

  1. Next(New) = Next(P) กำหนดให้ตัวชี้ Right ของโหนด I เปลี่ยนไปชี้ยังโหนด

3 ซึ่งเป็นส่วนหลังของการแทรกโหนดใหม่ ในรูปที่ 6.19 และ Prior(New) = P

กำหนดให้ตัวชี้ Left ของโหนด I เปลี่ยนไปชี้ยังโหนด 2 ซึ่งเป็นส่วนก่อนหน้าของ

การแทรกโหนดใหม่

  1. 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 ซึ่งเป็น

โหนดที่ต้องการลบ และขั้นตอนการลบประกอบด้วย

  1. Next(Prior(P)) = Next(P) เป็นการใช้ตัวชี้ left ของโหนดที่ต้องการลบอ้างกลับ

ไปยังโหนดก่อนหน้าเพื่อชี้ Right ชี้ไปยังโหนดถัดไปต่อจากโหนดที่ต้องการลบ

ในรูปที่ 6.22

 

  1. Prior(Next(P)) = Prior(P) เป็นการใช้ตัวชี้ Right ขอองโหนดที่ต้องการลบอ้างไป

ยังโหนดถัดไปเพื่อสร้างตัวชี้ Left ชี้กลับไปยังโหนดก่อนหน้าโหนดที่ต้องการลบในรูป

ที่ 6.23

  1. Free(P) หลังจากนั้นจึงปลดปล่อยโหนดที่ต้องการลบซึ่งมีตัวแปรพอยน์เตอร์ P ชี้

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

(Reuse) ได้เป็นรูปที่ 6.24

       ลำดับการทำงานจะมี 3 โหนดที่มาเกี่ยวข้อง คือ โหนดที่ต้องการลงมีตัวแปร

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

เปลี่ยนแปลง

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

      มีอยู่หลายกรณีที่นำลิงค์ลิสต์มาใช้งานตามความเหมาะสมซึ่งแต่ละโหนดจะถูก

กำหนดให้ส่วนการเชื่อมต่อมีมากกว่าสองทางเรียกว่าลิงค์ลิสต์หลายทาง (Multi-linked

List) อย่างเช่นในรูปที่ 6.25 ที่แต่ละโหนดในลิงค์ลิสต์จะมีตัวชี้สามทางโดยมีพื้นฐาน

เป็นลิงค์ลิสต์สองทางซึ่งมีส่วนเก็บข้อมูลคือ NameLength เก็บค่าความยาวของสตริง

กับส่วนเชื่อมต่อที่เป็นตัวชี้ Right และ Left และส่วนที่เชื่อมต่อที่สาม คือ ตัวชี้

NamePtr ใช้ชี้ไปยังข้อมูลจริงอีกทีซึ่งมีโครงสร้างข้อมูลสตริงเก็บไว้ในหน่วยความจำที่

ขอมาแทนการเก็บไว้ภายในโหนด

      ลิงค์ลิสต์หลายทางจะเป็นลักษณะพื้นฐานของโครงสร้างของข้อมูลอื่นที่จะกล่าวใน

บทต่อ ๆ ไป เช่น ทรี (Tree) กราฟ (Graph) และนำไปใช้จัดการกับแฟ้มข้อมูล (File)