ما هي القائمة المرتبطة الدائرية في C وكيفية تنفيذها

ما هي القائمة المرتبطة الدائرية (Circular Linked List)؟

القائمة المرتبطة الدائرية (Circular Linked List) هي نوع من القائمة المرتبطة، حيث تشير العقدة الأخيرة إلى العقدة الأولى، والعقدة الأولى تشير إلى العقدة الأخيرة، مما يجعلها بنية دائرية.

إنشاء قائمة مرتبطة دائرية

في المثال التالي، سنقوم بإنشاء قائمة مرتبطة دائرية مكونة من عدة عناصر:

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

struct Node {
    int data;
    struct Node* next;
};

// إنشاء عقدة جديدة
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// إنشاء قائمة مرتبطة دائرية
struct Node* createCircularLinkedList() {
    struct Node* head = NULL;
    struct Node* temp = NULL;
    struct Node* tail = NULL;
    int n, data;
    
    printf("أدخل عدد العناصر: ");
    scanf("%d", &n);
    
    for(int i = 0; i < n; i++) {
        printf("أدخل العنصر %d: ", i + 1);
        scanf("%d", &data);
        
        struct Node* newNode = createNode(data);
        
        if(head == NULL) {
            head = newNode;
            tail = newNode;
        } else {
            tail->next = newNode;
            tail = newNode;
        }
        tail->next = head; // ربط العنصر الأخير بالأول
    }
    
    return head;
}

عرض القائمة المرتبطة الدائرية بالعكس

لعرض القائمة المرتبطة الدائرية بالعكس، سنستخدم مكدس (stack) لتخزين العقدة ثم طباعة العقدة بالعكس:

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

#define MAX 100

void displayReverse(struct Node* head) {
    struct Node* stack[MAX];
    int top = -1;
    struct Node* temp = head;

    if (head == NULL) {
        return;
    }

    do {
        stack[++top] = temp;
        temp = temp->next;
    } while (temp != head);

    while (top != -1) {
        printf("%d ", stack[top--]->data);
    }
}

إيجاد حجم القائمة المرتبطة الدائرية

لحساب حجم القائمة المرتبطة الدائرية، سنقوم بالمرور عبر جميع العقد حتى نعود إلى العقدة الأولى:

int getSize(struct Node* head) {
    int size = 0;
    struct Node* temp = head;

    if (head == NULL) {
        return 0;
    }

    do {
        size++;
        temp = temp->next;
    } while (temp != head);

    return size;
}

البحث عن عنصر في القائمة المرتبطة الدائرية

للبحث عن عنصر في القائمة المرتبطة الدائرية، نقوم بمقارنة كل عقدة بالعقدة المطلوبة حتى نعود إلى العقدة الأولى:

struct Node* searchItem(struct Node* head, int key) {
    struct Node* temp = head;

    if (head == NULL) {
        return NULL;
    }

    do {
        if (temp->data == key) {
            return temp;
        }
        temp = temp->next;
    } while (temp != head);

    return NULL;
}

تحديث عنصر في القائمة المرتبطة الدائرية

لتحديث عنصر في القائمة المرتبطة الدائرية، سنبحث عن العنصر المطلوب ثم نقوم بتحديث قيمته:

void updateItem(struct Node* head, int oldValue, int newValue) {
    struct Node* temp = searchItem(head, oldValue);

    if (temp != NULL) {
        temp->data = newValue;
        printf("تم تحديث العنصر بنجاح.\n");
    } else {
        printf("العنصر غير موجود.\n");
    }
}

حذف عنصر من القائمة المرتبطة الدائرية

لحذف عنصر من القائمة المرتبطة الدائرية، نبحث عن العنصر المطلوب ونتجاوز العقدة المحذوفة:

struct Node* removeItem(struct Node* head, int key) {
    struct Node* temp = head;
    struct Node* prev = NULL;

    // إذا كانت العقدة الأولى هي المطلوبة
    if (head == NULL) {
        return NULL;
    }

    // إذا كانت العقدة الأولى تحتوي على العنصر
    if (temp->data == key) {
        while (temp->next != head) {
            temp = temp->next;
        }
        temp->next = head->next;
        free(head);
        return temp->next;
    }

    // البحث عن العقدة المطلوبة
    do {
        prev = temp;
        temp = temp->next;
    } while (temp != head && temp->data != key);

    if (temp->data == key) {
        prev->next = temp->next;
        free(temp);
    }

    return head;
}

دمج قائمتين دائريتين

لدمج قائمتين دائريتين، نقوم بالوصول إلى نهاية القائمة الأولى ثم نربطها ببداية القائمة الثانية:

struct Node* combineCircularLists(struct Node* head1, struct Node* head2) {
    struct Node* temp = head1;

    // الوصول إلى نهاية القائمة الأولى
    while (temp->next != head1) {
        temp = temp->next;
    }

    // ربط القائمة الثانية
    temp->next = head2;

    // الوصول إلى نهاية القائمة الثانية
    temp = head2;
    while (temp->next != head2) {
        temp = temp->next;
    }

    // ربطها ببداية القائمة الأولى
    temp->next = head1;

    return head1;
}

تقسيم القائمة الدائرية إلى قائمتين

لتقسيم القائمة الدائرية إلى قائمتين، سنجد نقطة الوسط ثم نقوم بفصل القائمة إلى قسمين:

void splitCircularList(struct Node* head, struct Node** firstHalf, struct Node** secondHalf) {
    struct Node* slow = head;
    struct Node* fast = head->next;

    // إيجاد نقطة الوسط
    while (fast != head && fast->next != head) {
        slow = slow->next;
        fast = fast->next->next;
    }

    *firstHalf = head;
    *secondHalf = slow->next;
    slow->next = head;

    struct Node* temp = *secondHalf;
    while (temp->next != head) {
        temp = temp->next;
    }
    temp->next = *secondHalf;
}

الخاتمة

في هذا الدرس، تعلمنا كيفية إنشاء قائمة مرتبطة دائرية، وإجراء العديد من العمليات عليها مثل العرض، البحث، التحديث، الحذف، الدمج، والتقسيم. القوائم المرتبطة الدائرية تستخدم في العديد من التطبيقات مثل الأنظمة الدورية والموجهة.