รายการเชื่อมโยงแบบวงกลม: ข้อดีและข้อเสีย

รายการเชื่อมโยงแบบวงกลมคืออะไร?

รายการเชื่อมโยงแบบวงกลมคือลำดับของโหนดที่จัดเรียงไว้เพื่อให้แต่ละโหนดสามารถเชื่อมโยงใหม่ได้tracแต่ละ "โหนด" เป็นองค์ประกอบที่อ้างอิงถึงตัวเอง โดยมีตัวชี้ไปยังโหนดหนึ่งหรือสองโหนดในบริเวณใกล้เคียง

ด้านล่างนี้เป็นภาพของรายการเชื่อมโยงแบบวงกลมที่มี 3 โหนด

ตรงนี้คุณจะเห็นว่าแต่ละโหนดนั้น...tracสามารถเชื่อมโยงตัวเองได้ ตัวอย่างที่แสดงด้านบนเป็นรายการเชื่อมโยงเดี่ยวแบบวงกลม

หมายเหตุ: รายการเชื่อมโยงแบบวงกลมที่ง่ายที่สุดคือโหนดเดียวที่มีตัวชี้ next อยู่ภายใน tracกลับสู่ตัวเอง ดังแสดงในภาพด้านล่าง

ขั้นพื้นฐาน Operaเงื่อนไขในรายการเชื่อมโยงแบบวงกลม

การดำเนินการพื้นฐานสามอย่างบนรายการเชื่อมโยงแบบวงกลม ได้แก่:

1. การแทรก
2. การลบและ
3. การข้ามผ่าน

• การแทรกเป็นกระบวนการของการวางโหนดในตำแหน่งที่ระบุในรายการเชื่อมโยงแบบวงกลม
• การลบเป็นกระบวนการลบโหนดที่มีอยู่ออกจากรายการที่เชื่อมโยง โหนดสามารถระบุได้โดยการเกิดขึ้นของค่าหรือตามตำแหน่งของโหนด
• การท่องไปในรายการเชื่อมโยงแบบวงกลม คือกระบวนการแสดงเนื้อหาทั้งหมดของรายการเชื่อมโยงและทำซ้ำtracย้อนกลับไปยังโหนดต้นทาง

ส่วนถัดไปจะอธิบายวิธีการทำงานของการแทรก และประเภทของการแทรกสองแบบที่เป็นไปได้ในรายการเชื่อมโยงเดี่ยวแบบวงกลม

การแทรก Operaการ

ขั้นแรก คุณต้องสร้างโหนดหนึ่งโหนดที่มีตัวชี้ next ชี้กลับไปยังตัวมันเอง ดังแสดงในภาพด้านล่าง หากไม่มีโหนดเริ่มต้นนี้ การแทรกครั้งแรกจะกลายเป็นโหนดแรกในรายการ

ถัดไป มีความเป็นไปได้สองประการ:

• การแทรกข้อมูล ณ ตำแหน่งปัจจุบันของรายการเชื่อมโยงแบบวงกลม ซึ่งเทียบเท่ากับการแทรกข้อมูลที่จุดเริ่มต้นหรือจุดสิ้นสุดของรายการเชื่อมโยงแบบเดี่ยวทั่วไป — ในรายการเชื่อมโยงแบบวงกลม จุดเริ่มต้นและจุดสิ้นสุดคือจุดเดียวกัน
• การแทรกหลังจากโหนดที่จัดทำดัชนี โหนดควรระบุด้วยหมายเลขดัชนีที่สอดคล้องกับค่าองค์ประกอบ

หากต้องการแทรกข้อมูลที่ต้นหรือท้ายของรายการเชื่อมโยงแบบวงกลม — กล่าวคือ ที่ตำแหน่งที่เพิ่มโหนดแรกสุด — ให้ทำตามขั้นตอนด้านล่าง:

• คุณจะต้องทำลายการเชื่อมโยงตนเองที่มีอยู่ไปยังโหนดที่มีอยู่
• ตัวชี้ถัดไปของโหนดใหม่จะเชื่อมโยงกับโหนดที่มีอยู่
• ตัวชี้ถัดไปของโหนดสุดท้ายจะชี้ไปที่โหนดที่แทรก

หมายเหตุ: ตัวชี้ที่ระบุจุดเริ่มต้นหรือจุดสิ้นสุดของวงกลมสามารถกำหนดใหม่ให้กับโหนดใดก็ได้ การวนรอบวงกลมจะยังคงกลับไปยังโหนดเดิม ดังที่ได้กล่าวไว้ในภายหลังในบทความนี้

ขั้นตอนใน (a) i-iii แสดงไว้ด้านล่าง:

(โหนดที่มีอยู่)

ขั้นตอน 1) ทำลายลิงค์ที่มีอยู่

ขั้นตอน 2) สร้างลิงก์ส่งต่อ (จากโหนดใหม่ไปยังโหนดที่มีอยู่)

ขั้นตอน 3) สร้างลิงก์วนซ้ำไปยังโหนดแรก

ต่อไป คุณจะลองแทรกหลังโหนด

ตัวอย่างเช่น ให้แทรก “VALUE2” ต่อท้ายโหนดที่มี “VALUE0” โดยสมมติว่าจุดเริ่มต้นคือโหนดที่มี “VALUE0”

• ตัดการเชื่อมต่อระหว่างโหนดแรกและโหนดที่สอง แล้ววางโหนดที่มีข้อความ “VALUE2” ไว้ตรงกลาง
• ตัวชี้ next ของโหนดแรกจะเชื่อมโยงไปยังโหนดใหม่ และตัวชี้ next ของโหนดใหม่จะเชื่อมโยงไปยังสิ่งที่เคยเป็นโหนดที่สอง
• ส่วนประกอบอื่นๆ ยังคงเหมือนเดิม โหนดทั้งหมดถูกจัดเรียงใหม่tracสามารถทำได้ด้วยตนเอง

หมายเหตุ: เนื่องจากการจัดเรียงเป็นแบบวนรอบ ขั้นตอนการแทรกโหนดจึงเหมือนกันไม่ว่าคุณจะเลือกตำแหน่งใดก็ตาม ตัวชี้ที่ปิดวงจรจะทำงานเหมือนกับตัวชี้อื่นๆ ในรายการ

นี่แสดงไว้ด้านล่าง:

(สมมติว่ามีเพียงสองโหนด นี่เป็นกรณีเล็กน้อย)

ขั้นตอน 1) ลบลิงค์ภายในระหว่างโหนดที่เชื่อมต่อ

ขั้นตอน 2) เชื่อมต่อโหนดด้านซ้ายเข้ากับโหนดใหม่

ขั้นตอน 3) เชื่อมต่อโหนดใหม่เข้ากับโหนดด้านขวามือ

การลบ Operaการ

สมมติว่ามีลิสต์เชื่อมโยงแบบวงกลมที่มี 3 โหนด กรณีการลบมีสองกรณีดังนี้:

• การลบองค์ประกอบปัจจุบัน
• การลบหลังจากองค์ประกอบ

การลบตอนเริ่มต้น/สิ้นสุด:

1. สำรวจไปยังโหนดแรกจากโหนดสุดท้าย
2. การลบจากส่วนท้ายสุดนั้นใช้เพียงขั้นตอนการท่องไปเพียงครั้งเดียวเท่านั้น คือจากโหนดสุดท้ายไปยังโหนดแรก
3. ลบลิงก์ระหว่างโหนดสุดท้ายกับโหนดแรก
4. เชื่อมโยงโหนดสุดท้ายกับองค์ประกอบถัดไปของโหนดแรก
5. ฟรีโหนดแรก

(การตั้งค่าที่มีอยู่)

ขั้นตอน 1) ลบลิงก์วงกลมออก

ขั้นตอน 2) ลบลิงก์ระหว่างโหนดแรกและโหนดถัดไป ลิงก์โหนดสุดท้ายไปยังโหนดที่ตามหลังโหนดแรก

ขั้นตอน 3) ปล่อย/ยกเลิกการจัดสรรโหนดแรก

การลบหลังจากโหนด:

1. ดำเนินการไปเรื่อยๆ จนกว่าจะพบโหนดถัดไปที่เป็นโหนดที่จะถูกลบ
2. เคลื่อนที่ไปยังโหนดถัดไป โดยวางตัวชี้บนโหนดก่อนหน้า
3. เชื่อมต่อโหนดก่อนหน้ากับโหนดหลังโหนดปัจจุบัน โดยใช้ตัวชี้ถัดไป
4. ปลดปล่อยโหนดปัจจุบัน (delinked)

ขั้นตอน 1) สมมติว่าเราจำเป็นต้องลบโหนดที่มี “VALUE1”

ขั้นตอน 2) ลบการเชื่อมโยงระหว่างโหนดก่อนหน้าและโหนดปัจจุบัน จากนั้นเชื่อมโยงโหนดก่อนหน้าโดยตรงกับโหนดที่ชี้โดยตัวชี้ถัดไปของโหนดปัจจุบัน (โหนดถัดจาก VALUE1)

ขั้นตอน 3) ฟรีหรือจัดสรรโหนดปัจจุบันใหม่

การข้ามผ่านรายการเชื่อมโยงแบบวงกลม

ในการวนลูปผ่านลิสต์เชื่อมโยงแบบวงกลมโดยเริ่มจากตัวชี้สุดท้าย ก่อนอื่นให้ตรวจสอบว่าตัวชี้สุดท้ายเป็นค่าว่าง (NULL) หรือไม่ ถ้าไม่ใช่ค่าว่าง ให้ตรวจสอบว่าลิสต์มีเพียงองค์ประกอบเดียวหรือไม่ มิฉะนั้น ให้วนลูปผ่านลิสต์ด้วยตัวชี้ชั่วคราว จนกว่าจะถึงตัวชี้สุดท้ายอีกครั้ง ดังแสดงในภาพเคลื่อนไหวด้านล่าง

ข้อดีของรายการเชื่อมโยงแบบวงกลม

ข้อดีบางประการของรายการลิงก์แบบวงกลมคือ:

1. ไม่มีข้อกำหนดสำหรับการกำหนด NULL ในโค้ด รายการแบบวงกลมไม่เคยชี้ไปที่ตัวชี้ NULL เว้นแต่จะมีการจัดสรรคืนทั้งหมด
2. โครงสร้างข้อมูลแบบลิสต์เชื่อมโยงวงกลมมีข้อดีสำหรับการดำเนินการกับจุดสิ้นสุดของลิสต์ เนื่องจากจุดเริ่มต้นและจุดสิ้นสุดตรงกัน Algorithms เช่น การจัดตารางเวลาแบบวนรอบ (round-robin scheduling) สามารถจัดการกระบวนการที่อยู่ในคิวได้อย่างราบรื่น โดยไม่พบตัวชี้ที่ค้างอยู่หรือตัวชี้ที่เป็นค่าว่าง (NULL pointer)
3. โครงสร้างข้อมูลแบบลิงค์ลิสต์วงกลมยังคงรองรับการดำเนินการปกติทั้งหมดเช่นเดียวกับลิงค์ลิสต์เดี่ยว โครงสร้างข้อมูลแบบลิงค์ลิสต์วงกลม รายการที่เชื่อมโยงสองครั้ง วิธีนี้ยังช่วยลดความจำเป็นในการไล่ดูข้อมูลทั้งหมดเพื่อค้นหาองค์ประกอบได้อีกด้วย ในกรณีที่แย่ที่สุด เป้าหมายจะอยู่ตรงข้ามกับตัวชี้เริ่มต้น ดังนั้นจึงจำเป็นต้องไล่ดูข้อมูลเพียงครึ่งหนึ่งของรายการเท่านั้น

ข้อเสียของ Circular Linked List

ข้อเสียในการใช้ Linked List แบบวงกลมมีดังนี้

1. รายการแบบวงกลมมีความซับซ้อนกว่า รายการที่เชื่อมโยงเดี่ยวๆ.
2. Revการกลับลำดับของลิสต์แบบวงกลมนั้นซับซ้อนกว่าการกลับลำดับของลิสต์แบบเชื่อมโยงเดี่ยวหรือแบบเชื่อมโยงคู่
3. หากไม่จัดการการยุติลูปอย่างระมัดระวัง โค้ดการวนซ้ำอาจเข้าสู่ลูปไม่สิ้นสุดได้
4. การหาจุดสิ้นสุดของรายการและการเขียนเงื่อนไขควบคุมลูปที่ถูกต้องนั้นยากกว่า
5. การแทรกข้อมูลที่จุดเริ่มต้นจำเป็นต้องไล่ดูรายการทั้งหมดเพื่อไปยังโหนดสุดท้าย (จากมุมมองของการใช้งานจริง)

รายการที่เชื่อมโยงเดี่ยวเป็นรายการที่เชื่อมโยงแบบวงกลม

ขอแนะนำให้คุณอ่านและนำโค้ดภาษา C ด้านล่างไปใช้งาน โค้ดนี้แสดงให้เห็นถึงการคำนวณทางคณิตศาสตร์ของตัวชี้ที่เกี่ยวข้องกับรายการเชื่อมโยงเดี่ยวแบบวงกลม

#include<stdio.h>
#include<stdlib.h>

struct node
{
    int item;
    struct node *next;
};

struct node* addToEmpty(struct node*,int);
struct node *insertCurrent(struct node *, int);
struct node *insertAfter(struct node *, int, int);
struct node *removeAfter(struct node *, int);
struct node *removeCurrent(struct node *);

void peek(struct node *);

int main()
{
...

คำอธิบายของรหัส:

1. โค้ดสองบรรทัดแรกคือไฟล์ส่วนหัวที่จำเป็น
2. ส่วนถัดไปจะอธิบายโครงสร้างของแต่ละโหนดที่อ้างอิงถึงตัวเอง โดยประกอบด้วยค่าและตัวชี้ที่มีชนิดเดียวกันกับโครงสร้างนั้น
3. แต่ละอินสแตนซ์ของโครงสร้างจะเชื่อมโยงกับวัตถุโครงสร้างอื่นๆ ที่มีประเภทเดียวกัน
4. มีฟังก์ชันต้นแบบที่แตกต่างกันสำหรับ:
   1. การเพิ่มองค์ประกอบลงในรายการเชื่อมโยงที่ว่างเปล่า
   2. การใส่ที่ ชี้ให้เห็นในปัจจุบัน ตำแหน่งของรายการเชื่อมโยงแบบวงกลม
   3. การแทรกตามหลังสิ่งที่เฉพาะเจาะจง การจัดทำดัชนี ค่าในรายการที่เชื่อมโยง
   4. การลบ/การลบหลังจากรายการใดรายการหนึ่ง การจัดทำดัชนี ค่าในรายการที่เชื่อมโยง
   5. การลบที่ตำแหน่งชี้ปัจจุบันของรายการเชื่อมโยงแบบวงกลม
5. ฟังก์ชันสุดท้ายจะพิมพ์แต่ละองค์ประกอบผ่านการแวะเวียนแบบวงกลมที่สถานะใดๆ ของรายการที่เชื่อมโยง

int main()
{
    struct node *last = NULL;
    last = insertCurrent(last,4);
    last = removeAfter(last, 4);
    peek(last);
    return 0;
}

struct node* addToEmpty(struct node*last, int data)
{
    struct node *temp = (struct node *)malloc(sizeof( struct node));
    temp->item = data;
    last = temp;
    last->next = last;
    return last;
}
  
struct node *insertCurrent(struct node *last, int data)

คำอธิบายของรหัส:

1. สำหรับโค้ด addToEmpty ให้จัดสรรโหนดว่างโดยใช้ฟังก์ชัน malloc()
2. นำข้อมูลที่เข้ามาใส่ไว้ในโหนดชั่วคราว
3. กำหนดให้โหนดชั่วคราวเป็นโหนดสุดท้าย และตั้งค่าตัวชี้ถัดไปของโหนดนั้นให้ชี้ไปยังตัวมันเอง เพื่อให้โหนดเดี่ยวชี้กลับไปยังตัวมันเอง
4. ส่งตัวชี้ตัวสุดท้ายกลับไปยัง main() / บริบทของแอปพลิเคชัน

struct node *insertCurrent(struct node *last, int data)
{
    if(last == NULL)
    {
       return    addToEmpty(last, data);
    }
    struct node *temp = (struct node *)malloc(sizeof( struct node));
    temp -> item = data;
    temp->next = last->next;
    last->next = temp;
    return last;
}
struct node *insertAfter(struct node *last, int data, int item)
{
    struct node *temp = last->next, *prev = temp, *newnode =NULL;
…

คำอธิบายของรหัส

1. หากรายการว่างเปล่า ให้ส่งต่อไปยัง addToEmpty() และส่งการควบคุมกลับ
2. สร้างโหนดชั่วคราวเพื่อวางไว้ต่อจากโหนดปัจจุบัน
3. เชื่อมต่อจุดต่างๆ ตามที่แสดงในแผนภาพด้านบน
4. ส่งคืนค่าตัวชี้สุดท้ายที่ตรงกับรูปแบบที่ใช้ในฟังก์ชันก่อนหน้า

...
struct node *insertAfter(struct node *last, int data, int item)
{
    struct node *temp = last->next, *prev = temp, *newnode =NULL;
    if (last == NULL)
    {
       return addToEmpty(last, item);
    }
    do
    {
        prev = temp;
        temp = temp->next;
    } while (temp->next != last && temp->item != data );

    if(temp->item != data)
    {
       printf("Element not found. Please try again");
...

คำอธิบายของรหัส:

1. หากรายการว่างเปล่า ให้ละเว้นคีย์การค้นหา เพิ่มรายการปัจจุบันเป็นโหนดเดียวในรายการ และส่งการควบคุมกลับ
2. ในแต่ละรอบของการวนลูป do-while ตัวชี้ previous จะเก็บผลลัพธ์ที่ได้จากการวนลูปครั้งล่าสุด
3. จากนั้นจึงจะเริ่มขั้นตอนการสำรวจถัดไป
4. ลูป do-while จะสิ้นสุดลงเมื่อพบข้อมูลเป้าหมาย หรือเมื่อตัวแปร temp กลับไปชี้ที่ตำแหน่งสุดท้ายอีกครั้ง บล็อกโค้ดต่อไปนี้จะตัดสินใจว่าจะทำอย่างไรกับข้อมูลที่พบ

...
    if(temp->item != data)
    {
       printf("Element not found. Please try again");
       return last;
    }
    else
    {
   	 newnode = (struct node *)malloc(sizeof(struct node));
             newnode->item = item;
             prev->next = newnode;
             newnode->next = temp;
    }
    return last;
}

struct node *removeCurrent(struct node *last)
...

คำอธิบายของรหัส:

1. หากตรวจสอบรายการทั้งหมดแล้วแต่ไม่พบรายการที่ต้องการ ให้แสดงข้อความ “ไม่พบรายการ” และส่งการควบคุมกลับไปยังผู้เรียกใช้งาน
2. หากพบโหนดเป้าหมาย ให้จัดสรรโหนดใหม่สำหรับค่าที่จะแทรกเข้าไป
3. ลิงค์ เชื่อมโยงโหนดก่อนหน้ากับโหนดใหม่ และเชื่อมโยงตัวชี้ next ของโหนดใหม่กับ temp (ตัวแปรการท่องไปในโหนด)
4. การดำเนินการนี้จะวางองค์ประกอบใหม่ไว้ต่อจากโหนดเป้าหมายในรายการเชื่อมโยงแบบวงกลมทันที จากนั้นการควบคุมจะกลับไปยังผู้เรียกใช้

struct node *removeCurrent(struct node *last)
{
    if(last == NULL)
    {
        printf("Element Not Found");
        return NULL;
    }
    struct node *temp = last->next;
    last->next = temp->next;
    free(temp);
    return last;
}

struct node *removeAfter(struct node *last, int data)

คำอธิบายของรหัส

1. ในการลบโหนดสุดท้าย (ปัจจุบัน) ก่อนอื่นให้ตรวจสอบว่ารายการว่างเปล่าหรือไม่ หากว่างเปล่า จะไม่สามารถลบองค์ประกอบใด ๆ ได้
2. ตัวแปร temp จะเลื่อนลิงก์ไปข้างหน้าหนึ่งลิงก์
3. เชื่อมตัวชี้ตัวสุดท้ายเข้ากับโหนดถัดจากโหนดแรก
4. ปล่อยตัวชี้ชั่วคราวเพื่อยกเลิกการจัดสรรโหนดที่ไม่ได้เชื่อมโยง

struct node *removeAfter(struct node *last,int data)
{
    struct node *temp = NULL,*prev = NULL;
    if (last == NULL)
    {
   	 printf("Linked list empty. Cannot remove any element\n");
   	 return NULL;
    }
    temp = last->next;
    prev = temp;
    do
    {
        prev = temp;
        temp = temp->next;
    } while (temp->next != last && temp->item != data );

    if(temp->item != data)
    {
      printf("Element not found");
...

คำอธิบายของรหัส

1. เช่นเดียวกับฟังก์ชันการลบก่อนหน้านี้ ให้ตรวจสอบก่อนว่ารายการว่างเปล่าหรือไม่ หากว่างเปล่า จะไม่สามารถลบองค์ประกอบใดๆ ได้
2. สอง ชี้ ได้รับมอบหมายตำแหน่งเฉพาะเพื่อค้นหาองค์ประกอบที่จะถูกลบ
3. ตัวเลขชี้ตำแหน่งจะเลื่อนไปทีละตัว (อุณหภูมิเส้นทางก่อนหน้า)
4. การท่องไปจะดำเนินต่อไปจนกว่าจะพบองค์ประกอบเป้าหมาย หรือจนกว่าตัวชี้ถัดไปจะไปถึงโหนดสุดท้ายอีกครั้ง

    if(temp->item != data)
    {
        printf("Element not found");
        return last;
    }
    else
    {
        prev->next = temp->next;
        free(temp);
    }
    return last;
}

void peek(struct node * last)
{
    struct node *temp = last;
    if (last == NULL)
    {
   return;

คำอธิบายของโปรแกรม

1. หากทำการสำรวจรายการเชื่อมโยงทั้งหมดแล้วไม่พบเป้าหมาย จะแสดงข้อความ “ไม่พบองค์ประกอบ”
2. มิเช่นนั้น องค์ประกอบจะถูกยกเลิกการเชื่อมโยงและปล่อยให้เป็นอิสระในขั้นตอนที่ 3 และ 4
3. ตัวชี้ก่อนหน้าเชื่อมโยงกับโหนดที่ชี้โดยตัวชี้ถัดไปของ temp (โหนดถัดจากโหนดที่กำลังถูกลบ)
4. จากนั้นตัวชี้ชั่วคราวจะถูกปล่อยให้เป็นอิสระ

...
void peek(struct node * last)
{
    struct node *temp = last;
    if (last == NULL)
    {
         return;  
    }
    if(last -> next == last)
    {
        printf("%d-", temp->item);
    }
    while (temp != last)
    {
       printf("%d-", temp->item);
       temp = temp->next;
    }
}

คำอธิบายของรหัส

1. การสำรวจแบบ Peek เป็นไปไม่ได้หากไม่มีโหนดอยู่เลย ผู้ใช้ต้องจัดสรรหรือแทรกโหนดก่อน
2. หากมีโหนดเพียงโหนดเดียว ไม่จำเป็นต้องวนลูปผ่านโหนดนั้น เพราะเนื้อหาของโหนดจะถูกพิมพ์ออกมาโดยตรง และลูป while จะไม่ทำงาน
3. หากมีโหนดมากกว่าหนึ่งโหนด ฟังก์ชัน temp จะพิมพ์ทุกรายการจนถึงองค์ประกอบสุดท้าย
4. เมื่อถึงองค์ประกอบสุดท้ายแล้ว ลูปจะสิ้นสุดลง และฟังก์ชันจะส่งการควบคุมกลับไปยัง main()

การประยุกต์รายการเชื่อมโยงแบบวงกลม

• การใช้การตั้งเวลาแบบ Round-Robin ในกระบวนการของระบบและการตั้งเวลาแบบวงกลมในกราฟิกความเร็วสูง
• การจัดตารางเวลาแบบโทเค็นริงในเครือข่ายคอมพิวเตอร์
• ใช้ในอุปกรณ์แสดงผล เช่น ป้ายโฆษณาดิจิทัลที่ต้องการการแสดงข้อมูลอย่างต่อเนื่อง

คำถามที่พบบ่อย