لیست‌های پیوند در ++C (لیست پیوندی تکی)

لیست پیوندی (‌Linked List‌) یکی از مهم‌ترین ساختار‌های داده است. اغلب ما با موقعیت‌هایی روبرو می‌شویم که داده، ماهیت پویا دارد و تعداد داده‌ها نمی‌تواند پیش‌بینی شود یا تعداد داده‌ها در طول اجرای برنامه تغییر می‌کند. لیست‌های پیوندی در این نوع موقعیت‌ها بسیار مفید هستند.

پیاده‌سازی لیست پیوندی در ++C با استفاده از اشاره‌گرها صورت می‌گیرد. اگر تسلط قوی به اشاره‌گر‌ها ندارید، می‌توانید صفحه pointers chapter را مرور کنید. همچنین می‌توانید تعدادی از سوالات خوب را در صفحه practice section مشاهده کنید.

یک لیست پیوندی از بسیاری گِره (nodes) ساخته شده است که به طور طبیعی متصل شده‌اند. هر گرِه اساسا به 2 بخش تقسیم شده است؛ یک بخش داده را نگه می‌دارد و بخش دیگر به یک گرِه متفاوت متصل شده است. این شبیه به تصویر زیر است:

در اینجا، هر گره حاوی یک عضو داده است (بخش بالایی تصویر) و به گره دیگر (بخش پائینی تصویر) متصل می‌شود. توجه کنید که آخرین گره به گره‌ی دیگری اشاره نمی‌کند و تنها NULL را ذخیره می‌کند.

در ++C، ما با استفاده از ساختار‌ها و اشاره‌گرها به این قابلیت دست پیدا می‌کنیم. هر ساختار بیانگر یک گره با تعدادی داده است و همین‌طور یک اشاره‌گر به ساختاری دیگر از همان نوع. این اشاره‌گر آدرس گره بعدی را نگه می‌دارد و مابین 2 گره اتصالی ایجاد می‌کند. بنابراین ساختار چیزی شبیه این است:

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

اولین عضو داده از ساختار (به نام node) یک interger برای نگه‌داشتن یک عدد صحیح است و دومین عضو داده اشاره‌گری به یک گره (از همان ساختار) است. این به این معنی است که دومین عضو داده آدرس گره بعدی را نگه می‌دارد و به این طریق، هر گره همان‌گونه که در تصویر بالا نشان داده شد، متصل می‌شوند.

تصویر ارائه شده در بالا، ساختار زیر را نمایش می‌دهد:

و  این تصویر بیانگر لیست پیوندی است:

بنابراین اگر ما به اولین گره دسترسی داشته باشیم، پس می‌توانیم به هر گره از لیست پیوندی دسترسی داشته باشیم. برای مثال، اگر 'a' یک گره است، پس a->next گره بعدی به 'a' است (اشاره‌گر آدرس گره‌ی بعدی که به نام  'next' است را ذخیره می‌کند).

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

کدنویسی یک لیست‌پیوندی

الان شما به مفهوم لیست پیوندی آگاه هستید. بیاید آن را کدنویسی کنیم. اولین قسمت ایجاد یک گره است (structure).

#include <iostream>

using namespace std;

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

حالا، یک کلاس 'linked_list' ایجاد خواهیم کرد که شامل همه‌ی توابع و اعضای داده مورد نیاز یک لیست پیوندی است. این کلاس از ساختار 'node' برای ایجاد کردن لیست پیوندی استفاده می‌کند.

دومین و مهم‌ترین بخش از لیست پیوندی این است که همیشه اولین گره را دنبال کند، چرا که دسترسی به اولین گره به معنی دسترسی به کل لیست است. بنابراین اولین گره‌مان را با عنوان 'head' فراخوانی کنیم:

#include <iostream>

using namespace std;

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

class linked_list
{
private:
    node *head,*tail;
public:
    linked_list()
    {
        head = NULL;
        tail = NULL;
    }
};

int main()
{
    linked_list a;
    return 0;
}

ما 2 گره ساختیم، head و tail. اولین گره را در head و دومین گره را در tail ذخیره خواهیم کرد. سازنده‌ی لیست پیوندی هر دوی head و tail را برابر NULL قرار داده است، چرا که ما هنوز هیچ عنصری را به لیست پیوندیمان اضافه نکرده‌ایم و بنابراین هر دو NULL هستند.

حالا، بیاید یک تابع برای اضافه کردن یک گره به لیست پیوندیمان ایجاد کنیم:

#include <iostream>

using namespace std;

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

class linked_list
{
private:
    node *head,*tail;
public:
    linked_list()
    {
        head = NULL;
        tail = NULL;
    }

    void add_node(int n)
    {
        node *tmp = new node;
        tmp->data = n;
        tmp->next = NULL;

        if(head == NULL)
        {
            head = tmp;
            tail = tmp;
        }
        else
        {
            tail->next = tmp;
            tail = tail->next;
        }
    }
};

int main()
{
    linked_list a;
    a.add_node(1);
    a.add_node(2);
    return 0;
}

اگر با تابع 'malloc' آشنا نیستند، پس تنها dynamic memory allocation chapter را بخوانید.

node *tmp = new node - ما حافظه‌ی مورد نیاز برای یک گره را با اُپریتور new تخصیص دادیم. حال، 'tmp' به یک گره اشاره دارد (یا حافظه برای یک گره تخصیص داده شده).

tmp->data = n - ما یک مقدار را به 'data' از 'tmp' دادیم که به تابع ارسال شده است.

tmp->next = NULL - ما در خط قبلی، مقدار 'data' دادیم و در این خط، مقدار اشاره‌گر next را NULL قرار دادیم و بنابراین گره‌مان 'tmp' کامل شده است.

بخش بعدی بعد از ایجاد یک گره، متصل کردن گره‌ها و ایجاد لیست پیوندی است. ابتدا بررسی می‌کنیم که آیا head خالی (NULL) است یا نه. اگر head خالی بود، به این معنی است که هنوز هیچ لیست پیوندی وجود ندارد و گره‌ِ فعلیمان ( tmp ) head خواهد بود.

if(head == NULL)
 {
   head = tmp;
   tail = tmp;
 }

اگر head خالی (NULL) باشد، گرهِ فعلیمان (tmp) اولین گره از لیست پیوندی است و  این هم head و tail خواهد شد. (در حال حاضر، در شرایط موجود، آخرین عنصر هستند)

اگر head خالی (NULL) نباشد، به این معنی است که یک لیست پیوندی داریم و فقط باید گره در انتهای لیست‌ پیوندی اضافه کنیم:

else
 {
   tail->next = tmp;
   tail = tail->next;
 }

گره جدید (tmp) به tail داده می‌شود و سپس tail را تغییر دادیم چرا که گره جدید tail است.

سعی کنید کد را با تخصیص 2 یا 3 گره‌ِ توسط مکانیزم بالا درک کنید و آن متوجه خواهید شد.

منبع: وب سایت codesdope