آموزش لیست پیوندی در c++ با درس 33 دقیقه ای و نکات کاربردی

لیست‌های پیوندی (Linked Lists) یکی از ساختارهای داده‌ای مهم در برنامه‌نویسی هستند که برای ذخیره‌سازی و مدیریت داده‌ها به کار می‌روند. این ساختار داده‌ای به دلیل انعطاف‌پذیری و قابلیت دسترسی سریع به عناصر، در بسیاری از کاربردها از جمله پیاده‌سازی صف‌ها، پشته‌ها و حتی گراف‌ها به کار می‌رود. در این مقاله، به بررسی عمیق لیست‌های پیوندی در زبان C++ خواهیم پرداخت و نحوه‌ی پیاده‌سازی و استفاده از این ساختار داده‌ای را با مثال‌های عملی بررسی خواهیم کرد.

تعریف لیست پیوندی

لیست پیوندی یک مجموعه‌ای از گره‌ها (Nodes) است که به صورت پیوندی به یکدیگر متصل شده‌اند. هر گره شامل دو بخش است:

1. داده‌ها (Data) که می‌تواند هر نوع داده‌ای باشد.
2. اشاره‌گر (Pointer) که آدرس گره بعدی را در لیست ذخیره می‌کند.

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

انواع لیست‌های پیوندی

لیست‌های پیوندی به چند دسته تقسیم می‌شوند:

در این نوع لیست، هر گره تنها به گره بعدی اشاره دارد. این ساده‌ترین نوع لیست پیوندی است.

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

در این نوع لیست، گره آخر به گره اول اشاره می‌کند و لیست به صورت حلقوی تشکیل می‌شود.

همه مطالب برنامه نویسی سی پلاس پلاس به ترتیب از اینجا ببینید

پیاده‌سازی لیست پیوندی تک‌جهته

در این بخش، به پیاده‌سازی لیست پیوندی تک‌جهته در زبان C++ می‌پردازیم. ابتدا باید یک ساختار (struct) برای گره‌ها تعریف کنیم.

#include <iostream></iostream>

using namespace std;

struct Node {

    int data;

    Node* next;

};

class LinkedList {

private:

    Node* head;

public:

    LinkedList() {

        head = nullptr;

    }

    // افزودن گره در ابتدای لیست

    void insertAtBeginning(int value) {

        Node* newNode = new Node();

        newNode->data = value;

        newNode->next = head;

        head = newNode;

    }

    // افزودن گره در انتهای لیست

    void insertAtEnd(int value) {

        Node* newNode = new Node();

        newNode->data = value;

        newNode->next = nullptr;

        if (head == nullptr) {

            head = newNode;

        } else {

            Node* temp = head;

            while (temp->next != nullptr) {

                temp = temp->next;

            }

            temp->next = newNode;

        }

    }

    // حذف گره از ابتدای لیست

    void deleteFromBeginning() {

        if (head == nullptr) {

            cout << "The list is empty." << endl;

            return;

        }

        Node* temp = head;

        head = head->next;

        delete temp;

    }

    // حذف گره از انتهای لیست

    void deleteFromEnd() {

        if (head == nullptr) {

            cout << "The list is empty." << endl;

            return;

        }

        if (head->next == nullptr) {

            delete head;

            head = nullptr;

        } else {

            Node* temp = head;

            while (temp->next->next != nullptr) {

                temp = temp->next;

            }

            delete temp->next;

            temp->next = nullptr;

        }

    }

    // نمایش لیست

    void display() {

        if (head == nullptr) {

            cout << "The list is empty." << endl;

            return;

        }

        Node* temp = head;

        while (temp != nullptr) {

            cout << temp->data << " -> ";

            temp = temp->next;

        }

        cout << "NULL" << endl;

    }

};

تحلیل عملکرد

لیست‌های پیوندی مزایا و معایبی دارند که در زیر به آن‌ها اشاره می‌کنیم:

مزایا:

1. انعطاف‌پذیری در اندازه: برخلاف آرایه‌ها که اندازه ثابتی دارند، لیست‌های پیوندی می‌توانند به راحتی بزرگ یا کوچک شوند.
2. افزودن و حذف عناصر: افزودن و حذف عناصر در لیست‌های پیوندی بدون نیاز به جابجایی سایر عناصر انجام می‌شود.
3. استفاده بهینه از حافظه: لیست‌های پیوندی تنها به اندازه عناصر موجود در لیست، حافظه مصرف می‌کنند.

معایب:

1. دسترسی تصادفی: برخلاف آرایه‌ها، دسترسی به یک عنصر خاص در لیست پیوندی نیازمند پیمایش لیست از ابتدا تا آن عنصر است.
2. هزینه حافظه اضافی: هر گره علاوه بر داده، نیاز به حافظه‌ای برای ذخیره آدرس گره بعدی دارد.
3. پیچیدگی پیاده‌سازی: پیاده‌سازی و مدیریت لیست‌های پیوندی پیچیده‌تر از آرایه‌ها است.

ترفندهای فوق العاده کاربردی چگونه می‌توان زبان C++ را یاد گرفت؟ بهترین روش یادگیری

پیاده‌سازی لیست پیوندی دو‌جهته

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

#include <iostream></iostream>

using namespace std;

struct Node {

    int data;

    Node* prev;

    Node* next;

};

class DoublyLinkedList {

private:

    Node* head;

public:

    DoublyLinkedList() {

        head = nullptr;

    }

    // افزودن گره در ابتدای لیست

    void insertAtBeginning(int value) {

        Node* newNode = new Node();

        newNode->data = value;

        newNode->prev = nullptr;

        newNode->next = head;

        if (head != nullptr) {

            head->prev = newNode;

        }

        head = newNode;

    }

    // افزودن گره در انتهای لیست

    void insertAtEnd(int value) {

        Node* newNode = new Node();

        newNode->data = value;

        newNode->next = nullptr;

        if (head == nullptr) {

            newNode->prev = nullptr;

            head = newNode;

        } else {

            Node* temp = head;

            while (temp->next != nullptr) {

                temp = temp->next;

            }

            temp->next = newNode;

            newNode->prev = temp;

        }

    }

    // حذف گره از ابتدای لیست

    void deleteFromBeginning() {

        if (head == nullptr) {

            cout << "The list is empty." << endl;

            return;

        }

        Node* temp = head;

        head = head->next;

        if (head != nullptr) {

            head->prev = nullptr;

        }

        delete temp;

    }

    // حذف گره از انتهای لیست

    void deleteFromEnd() {

        if (head == nullptr) {

            cout << "The list is empty." << endl;

            return;

        }

        if (head->next == nullptr) {

            delete head;

            head = nullptr;

        } else {

            Node* temp = head;

            while (temp->next != nullptr) {

                temp = temp->next;

            }

            temp->prev->next = nullptr;

            delete temp;

        }

    }

    // نمایش لیست

    void display() {

        if (head == nullptr) {

            cout << "The list is empty." << endl;

            return;

        }

        Node* temp = head;

        while (temp != nullptr) {

            cout << temp->data << " <-> ";

            temp = temp->next;

        }

        cout << "NULL" << endl;

    }

};

بلد باشید ۱۰ نکته مفید برای کدنویسی صحیح در c++

پیاده‌سازی لیست پیوندی حلقوی

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

#include <iostream></iostream>

using namespace std;

struct Node {

    int data;

    Node* next;

};

class CircularLinkedList {

private:

    Node* head;

public:

    CircularLinkedList() {

        head = nullptr;

    }

    // افزودن گره در انتهای لیست

    void insertAtEnd(int value) {

        Node* newNode = new Node();

        newNode->data = value;

        if (head == nullptr) {

            head = newNode;

            newNode->next = head;

        } else {

            Node* temp = head;

            while (temp->next != head) {

                temp = temp->next;

            }

            temp->next = newNode;

            newNode->next = head;

        }

    }

    // حذف گره از ابتدای لیست

    void deleteFromBeginning() {

        if (head == nullptr) {

            cout << "The list is empty." << endl;

            return;

        }

        if (head->next == head) {

            delete head;

            head = nullptr;

        } else {

            Node* temp = head;

            Node* last = head;

            while (last->next != head) {

                last = last->next;

            }

            head = head->next;

            last->next = head;

            delete temp;

        }

    }

    // نمایش لیست

    void display() {

        if (head == nullptr) {

            cout << "The list is empty." << endl;

            return;

        }

        Node* temp = head;

        do {

            cout << temp->data << " -> ";

            temp = temp->next;

        } while (temp != head);

        cout << "HEAD" << endl;

    }

};

<strong> </strong>

کاربردهای لیست‌های پیوندی

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

1. پیاده‌سازی صف‌ها و پشته‌ها: صف‌ها و پشته‌ها می‌توانند به راحتی با استفاده از لیست‌های پیوندی پیاده‌سازی شوند.
2. مدیریت حافظه: لیست‌های پیوندی در مدیریت حافظه پویا به کار می‌روند، به خصوص در سیستم‌هایی که نیاز به تخصیص و آزادسازی مکرر حافظه دارند.
3. گراف‌ها: گراف‌ها نیز می‌توانند با استفاده از لیست‌های پیوندی نمایش داده شوند، به طوری که هر گره نمایانگر یک رأس و هر پیوند نمایانگر یک یال است.

دانلود کنید ۴ تا از بهترین جزوه های PDF آموزش C++ به همراه اپلیکیشن

نتیجه‌گیری

لیست‌های پیوندی یکی از ابزارهای قدرتمند در برنامه‌نویسی هستند که انعطاف‌پذیری و کارایی بالایی را برای مدیریت داده‌ها فراهم می‌کنند. در این مقاله، به بررسی انواع مختلف لیست‌های پیوندی پرداختیم و نحوه‌ی پیاده‌سازی آن‌ها را در زبان C++ با ارائه مثال‌های عملی توضیح دادیم. با توجه به ویژگی‌ها و مزایای لیست‌های پیوندی، این ساختار داده‌ای همچنان در بسیاری از الگوریتم‌ها و کاربردهای برنامه‌نویسی مورد استفاده قرار می‌گیرد.