Singly Linked List

 ลิงค์ลิสต์แบบทางเดียว (Singly Linked List)


           ลิงค์ลิสต์เดียว หมายถึง Link List ที่แต่ละ node มีการแสดงออกลำดับก่อนหลังในทิศทางเดียวกัน โดยใช้ Pointer แสดงการเชื่อมโยง
การแทรกข้อมูลเข้าและลบข้อมูลออกจาก Link List (Insertion and Deletion)

1. การแทรกรายการข้อมูลเข้า (Insertion)

ก่อนการแทรก


หลังการแทรก


ขั้นตอนการแทรกรายการ
           1. กำหนดชื่อให้กับ node เช่น node n ใน AVAIL แล้ะเปลี่ยนไปชี้ยัง node ถัดจาก node n ของ Free pool
           2. node n ตัว pointer จะไปชี้ที่ node q 
           3. node p ตัว pointer จะเปลี่ยนจากชี้ที่ node q ไปชี้ node n แทน


ในการแทรกกรณีเฉพาะ 2 กรณี คือ
           ถ้า node n แทรกเข้ามาในตำแหน่งแรกของ List, ให้ทำข้อ 1,2 แล้วให้ head จะชี้ที่ node n




ถ้า node n เข้าต่อท้ายในตำแหน่งสุดท้ายของ list , ให้ทำข้อ 1 แล้วให้ pointer ของ node จะชี้ไปยัง null และตามด้วย pointer ของ node p ชี้ไปยัง node n


2.การลบรายการข้อมูลออก (Deletion)
            เมื่อมี node n ซึ่งอยู่ระหว่าง node p และ node q และต้องการลบ node n ออกจาก list นอกจากนี้ เมื่อลบ node n แล้วจะต้องคืน node n ให้กับ Free pool โดยการเก็บตำแหน่ง node n ลงในตำแหน่งเริ่มต้นของ Free Pool (AVAIL)



ขั้นตอนการลบรายการ
           1. ตัว pointer node p ชี้ไปยังตำแหน่งของ node q ซึ่งเดิม pointer node n ชี้อยู่
           2. ตัว pointer node n ชี้ไปยัง pointer ของ AVAIL ชี้อยู่
           3. ตัว pointer ของ AVAIL ชี้ไปยัง node n