لیست پیوندی در زبان C

یک پیاده‌سازی ساده از یک لیست پیوندی (Linked List) در زبان C است.

• در این بخش، یک ساختار به نام Node تعریف شده است که شامل دو فیلد است:

  • data: یک عدد صحیح که مقدار ذخیره شده در گره را نشان می‌دهد.

  • next: یک اشاره‌گر به گره بعدی در لیست، که به نوع ساختار Node اشاره دارد.

// تعریف یک ساختار (struct) برای گره‌های لیست پیوندی
struct Node
{
    int data;              // مقداری که در گره ذخیره می‌شود
    struct Node* next;     // اشاره‌گری به گره بعدی در لیست
};

• شروع تابعی به نام insertAtEnd که برای اضافه کردن یک گره جدید به انتهای لیست استفاده می‌شود. این تابع دو پارامتر دارد:

  • head_ref: اشاره‌گر به اشاره‌گر به سر لیست (برای امکان تغییر سر لیست اگر لیست خالی باشد).

  • new_data: داده‌ای که باید در گره جدید ذخیره شود.

// تابعی برای اضافه کردن یک گره جدید در انتهای لیست
void insertAtEnd(struct Node** head_ref, int new_data)

• در این خط یک گره جدید در حافظه با استفاده از تابع malloc ایجاد می‌شود و نوع آن به Node تبدیل می‌شود. این گره هنوز هیچ مقداری ندارد.

    // ایجاد یک گره جدید در حافظه
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

• یک اشاره‌گر کمکی به نام last ساخته می‌شود که در ابتدا به سر لیست اشاره می‌کند و برای پیمایش لیست استفاده خواهد شد.

    // اشاره‌گر کمکی برای پیمایش لیست
    struct Node* last = *head_ref; /* استفاده در مرحله یافتن آخر لیست */

• فیلد data گره جدید با مقدار new_data مقداردهی می‌شود و فیلد next به NULL تنظیم می‌شود چون این گره قرار است آخرین گره لیست باشد.

    // مقداردهی فیلدهای گره جدید
    new_node->data = new_data;
    new_node->next = NULL;   // چون قرار است در انتها قرار بگیرد، next خالی است

• اگر سر لیست خالی باشد (یعنی لیست خالی است)، گره جدید تبدیل به نخستین گره لیست می‌شود و تابع خاتمه می‌یابد.

    // اگر لیست خالی باشد، گره جدید نخستین گره می‌شود
    if (*head_ref == NULL) {
        *head_ref = new_node;
        return;
    }

• اگر لیست خالی نباشد، درون یک حلقه while پیمایش لیست انجام می‌شود تا به آخرین گره برسیم. تا زمانی که گره بعدی خالی نباشد، به گره بعدی منتقل می‌شویم.

    // پیمایش لیست تا رسیدن به آخرین گره
    while (last->next != NULL)
    {
        last = last->next;   // رفتن به گره بعدی
    }

• در نهایت، گره جدید به انتهای لیست متصل می‌شود و تابع خاتمه می‌یابد.

    // اتصال گره جدید به انتهای لیست
    last->next = new_node;
    return;

• این تابع به نام printList برای چاپ عناصر لیست پیوندی است.

• با استفاده از یک حلقه while تا زمانی که به انتهای لیست نرسیده‌ایم، مقادیر هر گره را چاپ می‌کند و به گره بعدی منتقل می‌شود.

// تابعی برای چاپ عناصر لیست پیوندی
void printList(struct Node* node)
{
    // تا زمانی که به انتهای لیست نرسیده‌ایم
    while (node != NULL) 
    {
        cout << node->data << " "; // چاپ مقدار گره
        node = node->next;         // رفتن به گره بعدی
    }
}

• در تابع main، یک لیست خالی ایجاد می‌شود که سر آن NULL است.

• سپس یک مقدار (۱) به انتهای لیست اضافه می‌شود و در نهایت کل لیست چاپ می‌شود.

این کد به طور کلی مثال ساده‌ای از استفاده از لیست پیوندی برای ذخیره و نمایش داده‌ها در زبان C است.

void main()
{
    // ایجاد یک لیست خالی (head خالی است)
    struct Node* head = NULL;

    // افزودن یک مقدار به انتهای لیست
    insertAtEnd(&head, 1);

    // چاپ کل لیست
    printList(head);
}

کد به زبان C++ در یک نگاه:

#include <iostream>
using namespace std;


// تعریف یک ساختار (struct) برای گره‌های لیست پیوندی
struct Node
{
    int data;              // مقداری که در گره ذخیره می‌شود
    struct Node* next;     // اشاره‌گری به گره بعدی در لیست
};

// تابعی برای اضافه کردن یک گره جدید در انتهای لیست
void insertAtEnd(struct Node** head_ref, int new_data) {

    // ایجاد یک گره جدید در حافظه
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

    // اشاره‌گر کمکی برای پیمایش لیست
    struct Node* last = *head_ref; /* استفاده در مرحله یافتن آخر لیست */

    // مقداردهی فیلدهای گره جدید
    new_node->data = new_data;
    new_node->next = NULL;   // چون قرار است در انتها قرار بگیرد، next خالی است

    // اگر لیست خالی باشد، گره جدید نخستین گره می‌شود
    if (*head_ref == NULL) {
        *head_ref = new_node;
        return;
    }

    // در غیر این صورت، پیمایش لیست تا رسیدن به آخرین گره
    while (last->next != NULL)
    {
        last = last->next;   // رفتن به گره بعدی
    }

    // اتصال گره جدید به انتهای لیست
    last->next = new_node;
    return;
}

// تابعی برای چاپ عناصر لیست پیوندی
void printList(struct Node* node)
{
    // تا زمانی که به انتهای لیست نرسیده‌ایم
    while (node != NULL) 
    {
        cout << node->data << " "; // چاپ مقدار گره
        node = node->next;         // رفتن به گره بعدی
    }
}

void main()
{
    // ایجاد یک لیست خالی (head خالی است)
    struct Node* head = NULL;

    // افزودن یک مقدار به انتهای لیست
    insertAtEnd(&head, 1);

    // چاپ کل لیست
    printList(head);
}

Telegram: @CaKeegan
Gmail : amidgm2020@gmail.com