تنفيذ القوائم المرتبطة في لغة C: شرح شامل مع أمثلة عملية

1. المقدمة

لغة C هي إحدى لغات البرمجة واسعة الاستخدام في برمجة الأنظمة وتطوير الأنظمة المدمجة. من بين هياكل البيانات فيها، يُعَدّ “هيكل القائمة” أداةً مفيدة جدًا لإدارة البيانات ومعالجتها. في هذه المقالة، سنشرح بالتفصيل هيكل القائمة في لغة C، بدءًا من المفاهيم الأساسية وحتى أمثلة عملية على التنفيذ.

أهمية هيكل القائمة

هيكل القائمة هو هيكل بيانات يُستخدم لإدارة البيانات مع الحفاظ على ترتيبها. وهو مفيد بشكل خاص في الحالات التالية:

• إدارة البيانات المرتبة
• إضافة أو حذف البيانات بشكل ديناميكي
• الاستخدام الفعّال للذاكرة

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

هدف هذه المقالة

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

أهداف التعلم

1. فهم أساسيات هيكل القائمة.
2. تعلم كيفية تنفيذ القوائم المرتبطة في لغة C.
3. تنمية القدرة على التطبيق من خلال أمثلة عملية.

2. ما هو هيكل القائمة

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

المفهوم الأساسي لهيكل القائمة

يتكون هيكل القائمة من عناصر بيانات (عُقد) متصلة ببعضها بشكل تسلسلي. كل عقدة تحتوي على عنصرين أساسيين:

1. جزء البيانات: يحتوي على القيمة الفعلية.
2. جزء الرابط: يحتوي على مؤشر (Pointer) يشير إلى العقدة التالية.

تسمح هذه البنية بإضافة أو حذف البيانات ديناميكيًا، مما يجعلها مفيدة للتعامل مع البيانات ذات الطول المتغير.

الفرق بين المصفوفة والقائمة

هناك اختلافات جوهرية بين المصفوفات وهياكل القوائم من حيث طريقة إدارة البيانات:

بشكل عام، يُفضل استخدام هيكل القائمة عندما تكون المرونة مطلوبة، بينما تكون المصفوفات مناسبة للوصول السريع إلى البيانات.

نظرة عامة وخصائص القائمة المرتبطة

من أشهر أمثلة هياكل القوائم ما يُعرف بـ “القائمة المرتبطة”. وتتميز هذه القائمة بالخصائص التالية:

1. إمكانية تغيير الحجم ديناميكيًا
   يمكن إضافة أو حذف العقد حسب الحاجة لإدارة الذاكرة بكفاءة.
2. سهولة الإدراج والحذف
   بفضل تعديل المؤشرات، يمكن إدراج أو حذف عناصر من أي موقع بسهولة.
3. البحث أبطأ
   الوصول إلى البيانات يتم بالتتابع من البداية، مما يجعل البحث عن عنصر محدد أبطأ نسبيًا.

أنواع القوائم المرتبطة

هناك ثلاثة أنواع رئيسية من القوائم المرتبطة:

1. القائمة أحادية الاتجاه
   كل عقدة تشير فقط إلى العقدة التالية.

• تستهلك ذاكرة أقل وبنيتها بسيطة.
• يمكن التحرك للأمام فقط، ولا يمكن العودة للخلف.

1. القائمة ثنائية الاتجاه
   كل عقدة تشير إلى العقدة السابقة والعقدة التالية.

• تمكن من التحرك في كلا الاتجاهين لمرونة أكبر.
• تستهلك ذاكرة أكبر من القائمة أحادية الاتجاه.

1. القائمة الدائرية
   العقدة الأخيرة تشير إلى العقدة الأولى.

• مناسبة للعمليات الدورية حيث يمكن العودة للبداية بعد الوصول للنهاية.
• مفيدة في الاستخدامات الخاصة مثل أنظمة الدوران (Round Robin).

في القسم التالي، سنشرح كيفية تنفيذ القوائم المرتبطة في لغة C مع أمثلة عملية على الأكواد.

3. تنفيذ القائمة المرتبطة في لغة C

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

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

تتكون القائمة المرتبطة من العناصر التالية:

1. تعريف العقدة (Node)

• تحتوي كل عقدة على بيانات ومؤشر إلى العقدة التالية.

1. مؤشر الرأس (Head Pointer)

• يشير إلى أول عنصر في القائمة ويُستخدم لإدارة القائمة بالكامل.

مثال على كود: تنفيذ أساسي للقائمة المرتبطة

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

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

// تعريف العقدة
typedef struct Node {
    int data;                 // جزء البيانات
    struct Node* next;        // مؤشر للعقدة التالية
} Node;

// إنشاء عقدة جديدة
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node)); // تخصيص الذاكرة
    if (newNode == NULL) {
        printf("فشل في تخصيص الذاكرة.\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL; // المؤشر التالي يكون NULL مبدئيًا
    return newNode;
}

// إدراج عقدة في بداية القائمة
void insertAtHead(Node** head, int data) {
    Node* newNode = createNode(data);
    newNode->next = *head; // العقدة الجديدة تشير إلى الرأس الحالي
    *head = newNode;       // تحديث الرأس ليكون العقدة الجديدة
}

// طباعة عناصر القائمة
void printList(Node* head) {
    Node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

// تحرير الذاكرة
void freeList(Node* head) {
    Node* temp;
    while (head != NULL) {
        temp = head;
        head = head->next;
        free(temp); // تحرير الذاكرة
    }
}

int main() {
    Node* head = NULL; // تهيئة قائمة فارغة

    // إضافة بيانات إلى القائمة
    insertAtHead(&head, 3);
    insertAtHead(&head, 2);
    insertAtHead(&head, 1);

    // عرض القائمة
    printList(head);

    // تحرير الذاكرة
    freeList(head);

    return 0;
}

شرح الكود

1. إنشاء العقدة

• يتم استخدام تخصيص الذاكرة الديناميكي لإنشاء عقدة جديدة.

1. إدراج العقدة

• يمكن إدراج البيانات في بداية القائمة أو نهايتها لتوسيع القائمة.

1. حذف العقدة

• يمكن حذف عقدة معينة أو العقدة الأولى في القائمة.

1. إدارة الذاكرة

• يجب تحرير الذاكرة المستخدمة لمنع تسرب الذاكرة (Memory Leak).

4. أنواع القوائم المرتبطة

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

1. القائمة أحادية الاتجاه

القائمة أحادية الاتجاه هي هيكل ترتبط فيه كل عقدة بالعقدة التالية فقط.

الخصائص:

• يمكن التحرك في اتجاه واحد فقط عبر عناصر القائمة.
• تستهلك القليل من الذاكرة وسهلة التنفيذ نسبيًا.

المميزات:

• الحجم متغير ديناميكيًا بفضل تخصيص الذاكرة الديناميكي.
• إضافة وحذف العناصر تتم بكفاءة.

العيوب:

• لا يمكن الرجوع إلى العقد السابقة، مما يجعل البحث العكسي غير فعال.

2. القائمة ثنائية الاتجاه

القائمة ثنائية الاتجاه تحتوي على مؤشرين في كل عقدة: واحد يشير إلى العقدة التالية، وآخر إلى العقدة السابقة.

الخصائص:

• كل عقدة تحتوي على رابط أمامي ورابط خلفي.
• تتيح التنقل في كلا الاتجاهين، مما يوفر مرونة أكبر.

المميزات:

• سهولة البحث والحذف في أي اتجاه.
• إمكانية التلاعب بالقائمة في أي نقطة بسهولة.

العيوب:

• تستهلك ذاكرة أكبر من القائمة أحادية الاتجاه.
• التنفيذ أكثر تعقيدًا بسبب وجود مؤشرين.

3. القائمة الدائرية

القائمة الدائرية هي هيكل بيانات ترتبط فيه العقدة الأخيرة بالعقدة الأولى.

الخصائص:

• لا يوجد نهاية للقائمة؛ يمكن الدوران حولها بلا توقف.
• يمكن تنفيذها كقائمة أحادية الاتجاه أو ثنائية الاتجاه.

المميزات:

• مناسبة للعمليات التي تتطلب التكرار المستمر مثل الجداول الدورية.
• تسهل الانتقال بين بداية ونهاية القائمة.

العيوب:

• إدارة المؤشرات تتطلب الحذر لأن القائمة لا تنتهي.

جدول مقارنة بين أنواع القوائم

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

5. عمليات القائمة المرتبطة

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

1. إدراج عنصر

هناك ثلاث طرق رئيسية لإدراج عنصر في القائمة المرتبطة:

(1) الإدراج في بداية القائمة

إضافة عقدة جديدة في بداية القائمة.

void insertAtHead(Node** head, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = *head; // العقدة الجديدة تشير إلى الرأس الحالي
    *head = newNode;       // تحديث الرأس ليصبح العقدة الجديدة
}

(2) الإدراج في نهاية القائمة

إضافة عقدة جديدة في نهاية القائمة.

void insertAtTail(Node** head, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;

    if (*head == NULL) { // إذا كانت القائمة فارغة
        *head = newNode;
        return;
    }

    Node* temp = *head;
    while (temp->next != NULL) { // الوصول إلى آخر عقدة
        temp = temp->next;
    }
    temp->next = newNode; // ربط العقدة الأخيرة بالعقدة الجديدة
}

2. حذف عنصر

هناك طريقتان أساسيتان لحذف عنصر من القائمة المرتبطة:

(1) حذف العنصر الأول

void deleteAtHead(Node** head) {
    if (*head == NULL) {
        printf("القائمة فارغة.\n");
        return;
    }
    Node* temp = *head;
    *head = (*head)->next; // تحديث الرأس ليشير إلى العقدة التالية
    free(temp); // تحرير الذاكرة
}

(2) حذف عنصر بقيمة محددة

void deleteNode(Node** head, int key) {
    Node* temp = *head;
    Node* prev = NULL;

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

    // البحث عن العقدة المستهدفة
    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }

    if (temp == NULL) {
        printf("القيمة غير موجودة.\n");
        return;
    }

    prev->next = temp->next;
    free(temp);
}

3. البحث عن عنصر

البحث عن بيانات محددة داخل القائمة.

int search(Node* head, int key) {
    Node* temp = head;
    int position = 0;

    while (temp != NULL) {
        if (temp->data == key) {
            return position; // إرجاع الموقع إذا تم العثور عليه
        }
        temp = temp->next;
        position++;
    }
    return -1; // إذا لم يتم العثور على العنصر
}

4. عرض القائمة

طباعة جميع عناصر القائمة بالترتيب.

void printList(Node* head) {
    Node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

الخلاصة

في هذا القسم، قمنا بتنفيذ العمليات الأساسية للقوائم المرتبطة:

• الإدراج: دعم إضافة العناصر في بداية أو نهاية القائمة أو في أي موقع محدد.
• الحذف: إمكانية حذف العنصر الأول أو عنصر بقيمة معينة.
• البحث: تحديد موقع عنصر معين في القائمة.

6. ملاحظات حول إدارة الذاكرة

في هذا القسم، سنشرح أهمية إدارة الذاكرة عند تنفيذ القوائم المرتبطة في لغة C، مع التركيز على تخصيص الذاكرة الديناميكي ومنع تسرب الذاكرة (Memory Leak)، لضمان كتابة برامج آمنة وفعّالة.

1. ما هو تخصيص الذاكرة الديناميكي؟

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

مثال على كود: تخصيص عقدة في الذاكرة

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node)); // تخصيص الذاكرة
    if (newNode == NULL) { // التحقق من نجاح التخصيص
        printf("فشل في تخصيص الذاكرة.\n");
        exit(1); // إنهاء البرنامج
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

2. أهمية تحرير الذاكرة

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

مثال على كود: تحرير الذاكرة

void freeList(Node* head) {
    Node* temp;
    while (head != NULL) {
        temp = head;         // حفظ العقدة الحالية
        head = head->next;   // الانتقال إلى العقدة التالية
        free(temp);          // تحرير الذاكرة
    }
}

3. أفضل الممارسات لمنع تسرب الذاكرة

1. تحرير الذاكرة دائمًا بعد الانتهاء من استخدامها

• يجب تحرير أي ذاكرة مخصصة فور الانتهاء من استخدامها.

1. استخدام أدوات فحص الذاكرة

• يمكن استخدام أدوات مثل Valgrind أو AddressSanitizer لاكتشاف أماكن تسرب الذاكرة.

مثال على استخدام Valgrind (في بيئة Linux)

valgrind --leak-check=full ./a.out

3. إدارة المؤشرات بوضوح

• تحديد ملكية المؤشر بوضوح وتجنب تعدد الجهات التي تتحكم في المؤشر نفسه.
• إعادة تعيين المؤشر إلى NULL بعد تحريره لمنع الوصول غير المقصود إليه.

الخلاصة

• التخصيص الديناميكي للذاكرة ضروري لمرونة القوائم المرتبطة.
• نسيان تحرير الذاكرة قد يؤدي إلى تسرب الذاكرة وتعطل البرنامج.
• استخدام أدوات فحص الذاكرة يساعد في كتابة برامج أكثر أمانًا.

7. أمثلة تطبيقية واستخدامات عملية

في هذا القسم، سنستعرض بعض الأمثلة على هياكل بيانات مبنية على القوائم المرتبطة، مع التركيز على المكدس (Stack) والطابور (Queue)، لإظهار مرونة وفائدة هذه البنية في التطبيقات البرمجية.

1. مثال على تنفيذ المكدس (Stack)

المكدس هو هيكل بيانات يعتمد على مبدأ Last In, First Out (LIFO)، أي أن آخر عنصر يتم إدخاله هو أول عنصر يتم إخراجه.

مثال على كود: تنفيذ المكدس باستخدام قائمة مرتبطة

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

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

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

void push(Node** top, int data) {
    Node* newNode = createNode(data);
    newNode->next = *top;
    *top = newNode;
}

int pop(Node** top) {
    if (*top == NULL) {
        printf("المكدس فارغ.\n");
        exit(1);
    }
    Node* temp = *top;
    int poppedData = temp->data;
    *top = (*top)->next;
    free(temp);
    return poppedData;
}

void printStack(Node* top) {
    while (top != NULL) {
        printf("%d -> ", top->data);
        top = top->next;
    }
    printf("NULL\n");
}

int main() {
    Node* stack = NULL;

    push(&stack, 10);
    push(&stack, 20);
    push(&stack, 30);

    printf("محتوى المكدس: ");
    printStack(stack);

    printf("القيمة التي تم إخراجها: %d\n", pop(&stack));
    printf("القيمة التي تم إخراجها: %d\n", pop(&stack));

    printf("محتوى المكدس: ");
    printStack(stack);

    return 0;
}

2. مثال على تنفيذ الطابور (Queue)

الطابور هو هيكل بيانات يعتمد على مبدأ First In, First Out (FIFO)، أي أن أول عنصر يتم إدخاله هو أول عنصر يتم إخراجه.

مثال على كود: تنفيذ الطابور باستخدام قائمة مرتبطة

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

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

typedef struct Queue {
    Node* front;
    Node* rear;
} Queue;

Queue* createQueue() {
    Queue* q = (Queue*)malloc(sizeof(Queue));
    q->front = q->rear = NULL;
    return q;
}

void enqueue(Queue* q, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    if (q->rear == NULL) {
        q->front = q->rear = newNode;
        return;
    }
    q->rear->next = newNode;
    q->rear = newNode;
}

int dequeue(Queue* q) {
    if (q->front == NULL) {
        printf("الطابور فارغ.\n");
        exit(1);
    }
    Node* temp = q->front;
    int data = temp->data;
    q->front = q->front->next;

    if (q->front == NULL) {
        q->rear = NULL;
    }

    free(temp);
    return data;
}

void printQueue(Queue* q) {
    Node* temp = q->front;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

int main() {
    Queue* q = createQueue();

    enqueue(q, 1);
    enqueue(q, 2);
    enqueue(q, 3);

    printf("محتوى الطابور: ");
    printQueue(q);

    printf("القيمة التي تم إخراجها: %d\n", dequeue(q));
    printf("القيمة التي تم إخراجها: %d\n", dequeue(q));

    printf("محتوى الطابور: ");
    printQueue(q);

    return 0;
}

الخلاصة

• المكدس (Stack) مناسب للعمليات التي تتبع مبدأ LIFO، مثل استدعاءات الدوال أو معالجة التعابير الرياضية.
• الطابور (Queue) مناسب للعمليات التي تتبع مبدأ FIFO، مثل إدارة المهام أو عمليات الانتظار في الأنظمة.

8. الخاتمة

في هذه المقالة، تناولنا بالتفصيل القوائم المرتبطة في لغة C، بدءًا من المفاهيم الأساسية، مرورًا بأمثلة عملية على التنفيذ، وصولاً إلى الاستخدامات المتقدمة. في هذا الجزء، سنراجع أهم النقاط ونقترح خطوات لمواصلة التعلم والتطبيق.

1. مراجعة أهم النقاط

أساسيات القوائم المرتبطة

• القوائم المرتبطة هي هياكل بيانات مرنة يمكن تغيير حجمها ديناميكيًا.
• على عكس المصفوفات، يسهل إضافة وحذف العناصر، لكن البحث عن عنصر معين قد يكون أبطأ.

أمثلة التنفيذ والعمليات الأساسية

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

الأنواع والاستخدامات

• القائمة أحادية الاتجاه: بسيطة وخفيفة، مناسبة للمهام الأساسية.
• القائمة ثنائية الاتجاه: تسمح بالتنقل في الاتجاهين، مفيدة في البحث والتعديل المتكرر.
• القائمة الدائرية: مثالية للعمليات الدورية وأنظمة الدوران.

أمثلة عملية

• استخدمنا القوائم المرتبطة في تنفيذ المكدس (Stack) والطابور (Queue).
• تساعد هذه الهياكل في تحسين الخوارزميات وتطوير أنظمة أكثر كفاءة.

2. المهارات المكتسبة

من خلال هذه المقالة، من المفترض أنك اكتسبت المهارات التالية:

• فهم هياكل البيانات وكيفية استخدامها بمرونة.
• تعزيز مهارات البرمجة عبر كتابة أكواد منظمة وقابلة للصيانة.
• تحسين القدرة على حل المشكلات من خلال اختيار الهيكل المناسب لكل حالة.

3. مواضيع للمتابعة

1. تطبيقات متقدمة لهياكل البيانات

• هياكل الأشجار (مثل الشجرة الثنائية، و AVL Tree).
• خوارزميات الرسوم البيانية (بحث عمق أول DFS، بحث عرض أول BFS).

1. إدارة البيانات المتقدمة

• جداول التجزئة (Hash Tables) والهياكل المرتبطة بها.
• التصميم الهجين بين المصفوفات والقوائم.

1. تحسين الخوارزميات

• تحسين خوارزميات الفرز والبحث.
• تحليل التعقيد الزمني والمكاني للبرامج.

4. أفكار لمشاريع عملية

• تطبيق لإدارة المهام باستخدام القوائم المرتبطة.
• أنظمة المحاكاة التي تعتمد على الطوابير والمكدسات.
• أدوات تحليل البيانات التي تستخدم هياكل بيانات مخصصة.

5. كلمة أخيرة

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