ما هي القائمة المرتبطة المزدوجة (Doubly Linked List) وكيفية تنفيذها في C

ما هي القائمة المرتبطة المزدوجة (Doubly Linked List)؟

القائمة المرتبطة المزدوجة (Doubly Linked List) هي نوع من القوائم المرتبطة التي يمكن التنقل فيها في كلا الاتجاهين، للأمام وللخلف، حيث تحتوي كل عقدة على مؤشرين: الأول يشير إلى العقدة السابقة، والثاني يشير إلى العقدة التالية.

إنشاء قائمة مرتبطة مزدوجة

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

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

// تعريف العقدة المزدوجة
struct Node {
    int data;
    struct Node* prev;
    struct Node* next;
};

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

// إنشاء قائمة مرتبطة مزدوجة
struct Node* createDoublyLinkedList() {
    struct Node* head = NULL;
    struct Node* temp = 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;
        } else {
            temp->next = newNode;
            newNode->prev = temp;
        }
        temp = newNode;
    }
    
    return head;
}

عرض القائمة المرتبطة المزدوجة بالعكس

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

void displayReverse(struct Node* head) {
    struct Node* temp = head;

    if (head == NULL) {
        return;
    }

    // الانتقال إلى العقدة الأخيرة
    while (temp->next != NULL) {
        temp = temp->next;
    }

    // الطباعة بالعكس
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->prev;
    }
    printf("\n");
}

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

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

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

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

    return size;
}

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

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

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

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

    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;

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

    // البحث عن العنصر المطلوب
    while (temp != NULL && temp->data != key) {
        temp = temp->next;
    }

    // إذا لم يتم العثور على العنصر
    if (temp == NULL) {
        return head;
    }

    // تعديل المؤشرات لتخطي العقدة المحذوفة
    temp->prev->next = temp->next;
    if (temp->next != NULL) {
        temp->next->prev = temp->prev;
    }

    free(temp);
    return head;
}

دمج قائمتين مرتبطتين مزدوجتين

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

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

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

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

    return head1;
}

تقسيم القائمة المرتبطة المزدوجة إلى قائمتين

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

void splitDoublyLinkedList(struct Node* head, struct Node** firstHalf, struct Node** secondHalf) {
    struct Node* slow = head;
    struct Node* fast = head;

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

    *firstHalf = head;
    *secondHalf = slow->next;
    slow->next = NULL;
    if (*secondHalf != NULL) {
        (*secondHalf)->prev = NULL;
    }
}

الخاتمة

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