โครงสร้างข้อมูลแบบ Linked Lists

• ลิงค์ลิสต์เป็นการนำข้อมูลแต่ละโหนดมาจัดเรียงต่อกันเป็นลิสต์ที่มีการเชื่อมโยงกัน
• ภายในแต่ละโหนดแบ่งส่วนประกอบได้เป็น 2 ฟิลด์ คือ ข้อมูล และแอดเดรสของโหนดถัดไป (Link) โดยฟิลด์ข้อมูลสามารถเก็บข้อมูลได้มากกว่าหนึ่งค่า
• ลิงค์ลิสต์เป็นการนำข้อมุลแต่ละโหนดมาเรียงต่อกันเป็นลิสต์ สิ่งที่เป็นตัวกำหนดลำดับ คือ ฟิลด์แอดเดรสของแต่ละโหนด
• การเข้าถึงลิงค์ลิสต์เริ่มต้นจะต้องมีพอยน์เตอร์ชี้ไปยังโหนดแรกของลิงค์ลิสต์ (Head)
• ฟิลด์แอดเดรสของโหนดสุดท้ายต้องกำหนดให้เป็น null ซึ่งเป็นการกำหนดให้จบลิงค์ลิสต์
• ลิงค์ลิสต์ที่ไม่มีโหนดอยู่ภายในจะเรียกว่า ลิสต์ว่าง (empty list หรือ null list)
• ลิงค์ลิสต์เดี่ยว (Single Linked List) คือ ลิงค์ลิสต์ที่มีฟิลด์แอดเดรสเพียงฟิลด์เดียวสำหรับชี้ตำแหน่งของโหนดถัดไป

• ลิงค์ลิสต์คู่ (Double Linked List) คือ ลิงค์ลิสต์ที่มีฟิลด์แอดเดรสจำนวน 2 ฟิลด์ สำหรับชี้ตำแหน่งของโหนถัดไปและตำแหน่งของโหนดที่อยู่ก่อนหน้า

Insert a node to the right of node(p)

      สมมติว่า กำหนดให้ Double linked list  เป็น List of integers  และต้องการแทรกโหนดทางขวามือจากโหนดที่ p ชี้อยู่  และกำหนด q และ r  เป็นตัวชี้ไปยังโหนดใด ๆ

q = getnode()

info(q) = x

r = right(p)

left(r) = q

right(q) = r

left(q) = p

right(p) = q

 Insert a node to the left of node(p)
      สมมติว่า กำหนดให้ Double linked list  เป็น List of integers  และต้องการแทรกโหนดทางซ้ายมือจากโหนดที่ p ชี้อยู่  และกำหนด q และ r  เป็นตัวชี้ไปยังโหนดใด ๆ

        q = getnode()
info(q) = x
r = left(p)
right(r) = q
left(q) = r
right(q) = p
left(p) = q

Delete a given node

     สมมติว่า กำหนดให้ Double linked list  เป็น List of integers  และต้องการลบโหนดที่ p ชี้อยู่ และเก็บค่า info ของโหนดนั้นไว้ในตัวแปร X

กำหนด q และ r  เป็นตัวชี้ไปยังโหนดใด ๆ

x  =  info(p)
q = left(p)
r = right(p)
right(q) = r
left(r) = q
freenode(p)