آموزش کد لیست پیوندی حلقوی c++ (یکطرفه و دوطرفه)

لیست‌های پیوندی (Linked Lists) یکی از ساختارهای داده‌ای پایه در علم رایانه هستند که امکان ذخیره و مدیریت داده‌ها به صورت خطی و ترتیبی را فراهم می‌کنند. از بین انواع مختلف این ساختارها، لیست پیوندی حلقوی (Circular Linked List) از اهمیت ویژه‌ای برخوردار است. این ساختار، برخلاف لیست‌های پیوندی معمولی، شروع یا پایان مشخصی ندارد و به صورت یک حلقه از گره‌ها (Nodes) سازمان‌دهی می‌شود. در این مقاله، به بررسی لیست پیوندی حلقوی یک‌طرفه (Singly Circular Linked List)، لیست پیوندی حلقوی دوطرفه (Doubly Circular Linked List) و مزایا و کاربردهای هر یک از آنها پرداخته می‌شود.

لیست پیوندی حلقوی چیست؟

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

انواع لیست پیوندی حلقوی

لیست پیوندی حلقوی را می‌توان به دو نوع اصلی تقسیم کرد:

1-لیست پیوندی یکتای حلقوی (Circular Singly Linked List): در این نوع لیست (تصویر بالا)، هر گره تنها یک اشاره‌گر به گره بعدی دارد. گره آخر به گره اول متصل است، به طوری که یک حلقه تشکیل می‌شود. در این نوع لیست، پیمایش تنها در یک جهت امکان‌پذیر است.

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

مزایای لیست پیوندی

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

معایب لیست پیوندی

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

بلد باشید: ۷ تا از نکات کاربردی برنامه نویسی C++

ساختار لیست پیوندی حلقوی

لیست پیوندی حلقوی یک‌طرفه

لیست پیوندی حلقوی یک‌طرفه، نوعی لیست پیوندی است که در آن هر گره فقط به گره بعدی اشاره می‌کند و گره آخر به گره اول متصل می‌شود و یک ساختار حلقوی ایجاد می‌کند. این لیست معمولاً با استفاده از لیست پیوندی یگانه (Singly Linked List) پیاده‌سازی می‌شود و هیچ گره‌ای به گره قبلی خود دسترسی ندارد.

لیست پیوندی حلقوی دوطرفه

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

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

لیست پیوندی حلقوی در بسیاری از کاربردهای واقعی مورد استفاده قرار می‌گیرد که برخی از مهم‌ترین آن‌ها عبارتند از:

1. مدیریت فهرست‌های پخش موسیقی: در برنامه‌های پخش موسیقی یا ویدئو، برای اجرای پیوسته و بدون توقف آهنگ‌ها یا ویدئوها، از لیست پیوندی حلقوی استفاده می‌شود.
2. الگوریتم‌های زمان‌بندی CPU: در سیستم‌عامل‌ها برای زمان‌بندی فرآیندها و تخصیص زمان به آن‌ها به صورت دایره‌ای، از این نوع لیست استفاده می‌شود.
3. بازی‌ها: در برخی از بازی‌های کامپیوتری که نیاز به حرکت مداوم کاراکترها در یک مسیر حلقوی دارند، از لیست پیوندی حلقوی استفاده می‌شود.
4. پیاده‌سازی صف‌ها و پشته‌ها: به دلیل ساختار حلقوی، این لیست‌ها می‌توانند به‌عنوان صف یا پشته در برنامه‌های مختلف استفاده شوند.
5. بافرهای دایره‌ای: در برنامه‌هایی که نیاز به مدیریت حجم زیادی از داده‌ها به صورت پیوسته وجود دارد، از این ساختارها به عنوان بافرهای دایره‌ای استفاده می‌شود.
6. سیستم‌های بلادرنگ: در برنامه‌هایی مانند پخش‌کننده‌های ویدیو و صدا، لیست‌های پیوندی حلقوی امکان پردازش داده‌ها به صورت پیوسته و بدون توقف را فراهم می‌کنند.

دانلود کنید: آموزش صفر تا صد برنامه نویسی سی پلاس پلاس (فارسی+ pdf)

ایجاد و پیمایش لیست پیوندی حلقوی

ایجاد لیست پیوندی حلقوی یک‌طرفه

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

ایجاد لیست پیوندی حلقوی دوطرفه

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

پیمایش لیست پیوندی حلقوی

دو روش برای پیمایش لیست پیوندی حلقوی وجود دارد:

1. پیمایش تا رسیدن به گره سر: در این روش، از یک حلقه استفاده می‌شود که گره‌ها را یکی پس از دیگری پیمایش می‌کند تا دوباره به گره سر برسد.
2. پیگیری گره‌های بازدید شده: در این روش، گره‌های پیمایش‌شده در یک مجموعه یا لیست ذخیره می‌شوند تا از تکرار پیمایش جلوگیری شود.

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

کد لیست پیوندی حلقوی c++ (یکطرفه و دوطرفه)

در اینجا دو نمونه کد برای پیاده‌سازی لیست پیوندی حلقوی (یکطرفه و دوطرفه) در زبان C++ آورده شده است:

1-لیست پیوندی یکتای حلقوی (Circular Singly Linked List)

#include <iostream></iostream>

using namespace std;

struct Node {

    int data;

    Node* next;

};

class CircularSinglyLinkedList {

private:

    Node* head;

public:

    CircularSinglyLinkedList() : head(nullptr) {}

    void append(int value) {

        Node* newNode = new Node();

        newNode->data = value;

        if (!head) {

            head = newNode;

            newNode->next = head;

        } else {

            Node* temp = head;

            while (temp->next != head) {

                temp = temp->next;

            }

            temp->next = newNode;

            newNode->next = head;

        }

    }

    void display() {

        if (!head) return;

        Node* temp = head;

        do {

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

            temp = temp->next;

        } while (temp != head);

        cout << endl;

    }

    ~CircularSinglyLinkedList() {

        if (!head) return;

        Node* temp = head;

        while (temp->next != head) {

            Node* next = temp->next;

            delete temp;

            temp = next;

        }

        delete temp;

    }

};

int main() {

    CircularSinglyLinkedList csll;

    csll.append(1);

    csll.append(2);

    csll.append(3);

    csll.append(4);

    csll.display();  // Output: 1 2 3 4

    return 0;

}

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

2-لیست پیوندی دوطرفه حلقوی (Circular Doubly Linked List)

#include <iostream></iostream>

using namespace std;

struct Node {

    int data;

    Node* next;

    Node* prev;

};

class CircularDoublyLinkedList {

private:

    Node* head;

public:

    CircularDoublyLinkedList() : head(nullptr) {}

    void append(int value) {

        Node* newNode = new Node();

        newNode->data = value;

        if (!head) {

            head = newNode;

            newNode->next = head;

            newNode->prev = head;

        } else {

            Node* last = head->prev;

            last->next = newNode;

            newNode->next = head;

            newNode->prev = last;

            head->prev = newNode;

        }

    }

    void display() {

        if (!head) return;

        Node* temp = head;

        do {

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

            temp = temp->next;

        } while (temp != head);

        cout << endl;

    }

    ~CircularDoublyLinkedList() {

        if (!head) return;

        Node* temp = head;

        while (temp->next != head) {

            Node* next = temp->next;

            delete temp;

            temp = next;

        }

        delete temp;

    }

};

int main() {

    CircularDoublyLinkedList cdll;

    cdll.append(1);

    cdll.append(2);

    cdll.append(3);

    cdll.append(4);

    cdll.display();  // Output: 1 2 3 4

    return 0;

}

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

ویدیوی آموزشی
لیست پیوندی یک طرفه:

لیست پیوندی دو طرفه:

لیست پیوندی حلقوی:

پس ...

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