ما هي القائمة المرتبطة (Linked List) وكيفية التعامل معها باستخدام لغة C

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

القائمة المرتبطة (Linked List) هي بنية بيانات ديناميكية تتألف من مجموعة من العقد (Nodes)، حيث تحتوي كل عقدة على عنصر بيانات بالإضافة إلى مؤشر يشير إلى العقدة التالية. على عكس المصفوفات، فإن القائمة المرتبطة تُخصص الذاكرة بشكل ديناميكي ويمكن تغيير حجمها بسهولة أثناء التشغيل.

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

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

#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* createLinkedList() {
    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;
        }
        temp = newNode;
    }
    
    return head;
}

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

لعرض القائمة المرتبطة بالعكس، سنستخدم دالة استدعاء ذاتي (recursion) للوصول إلى العقدة الأخيرة أولًا:

void displayReverse(struct Node* head) {
    if(head == NULL)
        return;
    displayReverse(head->next); // الاستدعاء الذاتي للوصول إلى النهاية
    printf("%d ", head->data);  // الطباعة بعد الرجوع
}

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

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

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;
    struct Node* prev = NULL;
    
    // إذا كانت العقدة الأولى هي المطلوبة
    if(temp != NULL && temp->data == key) {
        head = temp->next;
        free(temp);
        return head;
    }
    
    // البحث عن العقدة المطلوبة
    while(temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }
    
    // إذا لم يتم العثور على العنصر
    if(temp == NULL)
        return head;
    
    // إزالة العقدة
    prev->next = temp->next;
    free(temp);
    
    return head;
}

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

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

struct Node* combineLists(struct Node* head1, struct Node* head2) {
    struct Node* temp = head1;
    
    // الوصول إلى نهاية القائمة الأولى
    while(temp->next != NULL) {
        temp = temp->next;
    }
    
    // ربط القائمة الثانية
    temp->next = head2;
    
    return head1;
}

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

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

void splitList(struct Node* head, struct Node** firstHalf, struct Node** secondHalf) {
    struct Node* slow = head;
    struct Node* fast = head->next;
    
    // إيجاد نقطة الوسط باستخدام مؤشرين
    while(fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    
    // تقسيم القائمة
    *firstHalf = head;
    *secondHalf = slow->next;
    slow->next = NULL;
}

الخاتمة

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