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

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

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

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

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

หมายเหตุ: รายการลิงก์แบบวงกลมที่ง่ายที่สุดคือโหนดที่ติดตามเฉพาะตัวมันเองตามที่แสดง

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

การดำเนินการพื้นฐานบนรายการลิงก์แบบวงกลมมีดังนี้:

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

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

ในส่วนถัดไป คุณจะเข้าใจการแทรกโหนด และประเภทของการแทรกที่เป็นไปได้ใน Circular Singly Linked List

การแทรก Operaการ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

หมายเหตุ: เนื่องจากมีการจัดเรียงแบบวนรอบ การแทรกโหนดจึงเกี่ยวข้องกับขั้นตอนเดียวกันสำหรับโหนดใดๆ ตัวชี้ที่ทำให้วงจรเสร็จสมบูรณ์ก็ทำให้วงจรเสร็จสมบูรณ์เหมือนกับโหนดอื่นๆ

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

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

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

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

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

การลบ Operaการ

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

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

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

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

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

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

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

ขั้นตอนที่ 3) ฟรี /deallocate โหนดแรก

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

#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. สำหรับโค้ด addEmpty ให้จัดสรรโหนดว่างโดยใช้ฟังก์ชัน 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. หากไม่มีองค์ประกอบที่จะแทรก คุณควรตรวจสอบให้แน่ใจว่าได้เพิ่มลงในรายการว่างและควบคุมการส่งคืน
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 ต้องแน่ใจว่ามีตัวชี้ก่อนหน้าที่เก็บผลลัพธ์ที่เคลื่อนที่ครั้งล่าสุด
3. การเคลื่อนที่ครั้งถัดไปจึงจะเกิดขึ้นได้
4. หากพบข้อมูล หรืออุณหภูมิย้อนกลับไปยังตัวชี้สุดท้าย do- While จะสิ้นสุดลง ส่วนถัดไปของโค้ดจะตัดสินใจว่าจะต้องทำอะไรกับไอเท็ม

...
    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. ลิงค์ โหนดก่อนหน้ากับโหนดใหม่ เชื่อมโยงโหนดปัจจุบันกับอุณหภูมิ (ตัวแปรการสำรวจ)
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. ตัวแปรชั่วคราวเพียงข้ามลิงก์ไปข้างหน้าหนึ่งลิงก์
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. การแอบดูหรือการแวะผ่านจะไม่สามารถทำได้หากไม่มีความจำเป็น ผู้ใช้จำเป็นต้องจัดสรรหรือแทรกโหนด
2. หากมีเพียงหนึ่งโหนด ก็ไม่จำเป็นต้องข้าม เนื้อหาของโหนดสามารถพิมพ์ได้ และ while ลูปจะไม่ทำงาน
3. หากมีมากกว่าหนึ่งโหนด อุณหภูมิจะพิมพ์รายการทั้งหมดจนถึงองค์ประกอบสุดท้าย
4. เมื่อถึงองค์ประกอบสุดท้าย การวนซ้ำจะสิ้นสุดลง และฟังก์ชันจะส่งคืนการเรียกไปยังฟังก์ชันหลัก

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

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