วิธีแก้ปัญหาในการย้ายข้อมูลที่พบในการจัดเก็บที่มีรูปแบบเรียงตามลำดับ(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 และขั้นตอนในการแทรกประกอบด้วย
- Next(New) =Next (P) กำหนดให้ตัวชี้ของโหนด I เปลี่ยนไปชี้ยังโหนด 3 ซึ่งเป็นส่วนหลังของการแทรกโหนดใหม่ ในรูปที่ 6.3
- 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 และขั้นตอนในการแทรกประกอบด้วยดังต่อไปนี้
- Next(New) = Next(P) กำหนดให้ตัวชี้ Right ของโหนด I เปลี่ยนไปชี้ยังโหนด 3 ซึ่งเป็นส่วนหลังของการแทรกโหนดใหม่ ในรูปที่ 6.19 และ Prior(New) = P กำหนดให้ตัวชี้ Left ของโหนด I เปลี่ยนไปชี้ยังโหนด 2 ซึ่งเป็นส่วนก่อนหน้าของการแทรกโหนดใหม่
- 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.6 อัลกอริทึมการลบโหนดออกจากลิงค์ลิสต์สองทาง
พิจารณาจากตัวอย่างลิงค์ลิสต์สองทางในรูปที่ 6.21 เป็นอัลกอริทึมในการลบโหนดออกจากลิงค์ลิสต์สองทาง โดยเริ่มต้นให้ตัวแปรพอยน์เตอร์ P ชี้ไปโหนด 2 ซึ่งเป็นโหนดที่ต้องการลบ และขั้นตอนการลบประกอบด้วย
- Next(Prior(P)) = Next(P) เป็นการใช้ตัวชี้ left ของโหนดที่ต้องการลบอ้างกลับไปยังโหนดก่อนหน้าเพื่อชี้ Right ชี้ไปยังโหนดถัดไปต่อจากโหนดที่ต้องการลบ ในรูปที่ 6.22
- Prior(Next(P)) = Prior(P) เป็นการใช้ตัวชี้ Right ขอองโหนดที่ต้องการลบอ้างไปยังโหนดถัดไปเพื่อสร้างตัวชี้ Left ชี้กลับไปยังโหนดก่อนหน้าโหนดที่ต้องการลบในรูปที่ 6.23
- Free(P) หลังจากนั้นจึงปลดปล่อยโหนดที่ต้องการลบซึ่งมีตัวแปรพอยน์เตอร์ P ชี้อยู่ เพื่อคืนพื้นที่หน่วยความจำของโหนดที่ลบไปและนำไปใช้กับงานอื่นได้ (Reuse) ได้เป็นรูปที่ 6.24
ลำดับการทำงานจะมี 3 โหนดที่มาเกี่ยวข้อง คือ โหนดที่ต้องการลงมีตัวแปรพอยน์เตอร์ P โหนดก่อนหน้าและโหนดถัดไป ส่วนโหนดอื่น ๆ ไม่ถูกเรียกใช้งานหรือเปลี่ยนแปลง
ลิ้งค์ลิสต์หลายทาง
มีอยู่หลายกรณีที่นำลิงค์ลิสต์มาใช้งานตามความเหมาะสมซึ่งแต่ละโหนดจะถูกกำหนดให้ส่วนการเชื่อมต่อมีมากกว่าสองทางเรียกว่าลิงค์ลิสต์หลายทาง (Multi-linked List) อย่างเช่นในรูปที่ 6.25 ที่แต่ละโหนดในลิงค์ลิสต์จะมีตัวชี้สามทางโดยมีพื้นฐานเป็นลิงค์ลิสต์สองทางซึ่งมีส่วนเก็บข้อมูลคือ NameLength เก็บค่าความยาวของสตริง กับส่วนเชื่อมต่อที่เป็นตัวชี้ Right และ Left และส่วนที่เชื่อมต่อที่สาม คือ ตัวชี้ NamePtr ใช้ชี้ไปยังข้อมูลจริงอีกทีซึ่งมีโครงสร้างข้อมูลสตริงเก็บไว้ในหน่วยความจำที่ขอมาแทนการเก็บไว้ภายในโหนด
