لیست پیوندی در سی پلاس پلاس (LinkedList)

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

  1. آشنایی با شی گرایی
  2. آشنایی با توابع
  3. آشنایی با While
  4. Constructor


لیست پیوندی( LinkedList)

یکی از مشکلاتی که آرایه دارد ساختار و طول ثابت آن است بنابراین براحتی نمیتوان ساختار آن را طوری تغییر داد که با داده های(اطلاعات) ما همخوانی داشته باشد. همچنین آرایه هزینه insert و delete آن بالا است.

لیست پیوندی یک داده ساختار خطی است که بر خلاف آرایه طول آن میتواند تغییر کند و فضای اضافی را اشغال نکند. در لیست پیوندی هر عنصر یک Object (شی) جداگانه است. هر عنصر (از این به بعد به عنصر را نود می گوییم ) در لیست دو بخش دارد 1.داده (اطلاعات) 2. ارجاع(refrence) به شی(Object) بعدی.

لیست پیوندی در جاوا

در لیست  نود آخر همیشه ارجاع آن null است (البته در single linkedlist). نود اول را در لیست پیوندی head میگویند و ارجاع آن نگه داشته میشود. همان طور که گفته شد لیست پیوندی تعداد ثابتی نود ندارد و کاملا پویا است و به راحتی با داده های ما طول لیست اضافه و کم میشود. یکی از ایرادهای لیست پیوندی نسبت به آرایه این است که اجازه دسترسی مستقیم به نود خاصی را نمی دهد.

انواع لیست

لیست ها به دسته های مختلفی تقسیم میشوند.در این آموزش به معرفی جند نمومه از لیست ها می پردازیم. انواع لیست ها شامل:

  1. Single linked list: هر نود شامل یک داده و یک ارجاع به نود بعدی هستند.
  2. Double linked List:  هر نود علاوه بر ارجاع به نود بعدی، ارجاع به نود قبل هم دارند.
  3. Circular linked list: کاملا شبیه به single linked list هست فقط نود آخر ارجاعش به نود اول است.
لیست پیوندی در جاوا
لیست پیوندی در جاوا

پیاده سازی لیست پیوندی در سی پلاس پلاس

این قسمت به پیاده سازی لیست پیوندی در سی پلاس پلاس (Single linked list) پرداخته میشود. پیاده سازی لیست های پیوندی به صورت های مختفی است. ما یکی از آنها را بیان می کنیم. یک Struct به نام Node می‌سازیم که شامل دو متغیر است:

  1. داده Node
  2. ارجاع به نود بعدی
بیشتر بخوانید:  سطح دسترسی ها در سی پلاس پلاس (Access Modifiers)

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

مرحله بعد پیاده سازی خود لیست است. ابتدا کلاس Linkedlist را می‌نویسیم سپس برای استفاده از آن یک Main را پیاده سازی می‌کنیم. کلاس LinkedList شامل توابع و متغیر‌های زیر است :

  1. start: اولین عنصر لیست
  2. () create_node : این تابع یک نود می‌سازد.
  3. () deleteFirst: اولین خانه لیست ما را حذف می‌کند.
  4. () Insert: تابعی که یک نود به خانه های لیست ما اضافه می کند.
  5. () Display : تابعی که عناصر لیست را نمایش می‌دهد.

class LinkedList {
  public:
         node* start;
        node* create_node(int value);
        void insert(int value);
        void deleteFirst();
        void display();
        LinkedList()
        {
            start = NULL;
        }
};
node *LinkedList::create_node(int value) {
    struct node *temp;
    temp = new (struct node);
    if (temp == NULL) {
         cout << “Memory not allocated ” << endl;
         return 0;
    } else {
         temp->info = value;
         temp->next = NULL;
         return temp;
    }
}
void LinkedList::insert(int value) {
    struct node *temp, *s;
    temp = create_node(value);
    if(start == NULL){
         start = temp;
         cout << value << ” Inserted at List” << endl;
         return;
    }
    s = start;
    while (s->next != NULL) {
         s = s->next;
    }
    temp->next = NULL;
    s->next = temp;
    cout << value << ” Inserted at List” << endl;
}
void LinkedList::deleteFirst() {
    if (start == NULL) {
         cout << “The List is Empty” << endl;
         return;
    }
    node *temp = start;
    start = start->next;
    delete temp;
}
void LinkedList::display() {
    struct node *temp;
    if (start == NULL) {
         cout << “The List is Empty” << endl;
         return;
    }
    temp = start;
    cout << “Elements of list are: ” << endl;
    while (temp != NULL) {
         cout << temp->info << “->”;
         temp = temp->next;
    }
    cout << “NULL” << endl;
}

بیشتر بخوانید:  دانلود سورس الگوریتم دایکسترا در سی پلاس پلاس

در آخر هم یک Main برای برنامه مینویسیم.

     int main() {
    LinkedList l;
    l.insert(11);
    l.insert(22);
    l.insert(33);
    cout << “display List” << endl;
    l.display();
    l.deleteFirst();
    l.display();
    return 0;
}

خروجی برنامه به صورت زیر می‌باشد:

33 Inserted at List
display List
11->22->33->NULL
Elements of list are:
22->33->NULL

دانلود سورس کد:

پسورد فایل: www.codegate.ir

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *