بخش ۱۴ - لیست‌های پیوندی

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

فهرست مثال‌ها

لیست‌های پیوندی - پیاده‌سازی غیرشیءگرا

در این مثال لست‌ پیوندی دوطرفه به صورت غیرشیءگرا پیاده‌سازی می‌شود. عناصر این لیست اعداد صحیح هستند.

1_NonOOLinkedList.cpp
#include <iostream>
using namespace std;

class Node {
public:
    Node(int d, Node *n = NULL, Node *p = NULL)
        : data(d), next(n), prev(p) {}

    int data;
    Node *next;
    Node *prev;
};

void print_list(Node *list) {
    for (Node* p = list; p != NULL; p = p->next)
        cout << p->data << ' ';
}

void rec_print_list(Node *list) {
    if (list == NULL)
        return;
    cout << list->data << ' ';
    rec_print_list(list->next); 
}

void push_front(Node*& list, int x) {
    Node *new_node = new Node(x);
    new_node->next = list;
    if (list != NULL)
        list->prev = new_node;
    list = new_node;
}

void push_back(Node *&list, int x) {
    Node *new_node = new Node(x);

    if (list != NULL) {
        Node *p = list;
        while (p->next != NULL)
            p = p->next;
    
        new_node->prev = p;
        p->next = new_node;
    } else
        list = new_node;
}

void delete_list(Node *&list) {
    Node *p = list;
    while (p != NULL) {
        Node *q = p;
        p = p->next;
        delete q;
    }
    list = NULL;
}

void rec_delete_list(Node *&list) {
    if (list == NULL)
        return;
    rec_delete_list(list->next);
    delete list;
    list = NULL;
}

int main() {
    Node *l = NULL;
    
    push_back(l, 86);
    push_front(l, 43);
    push_front(l, 12);
    
    print_list(l);
    cout << endl;

    push_back(l, 444);

    print_list(l);
    cout << endl;   

    cout << l << endl;

    delete_list(l);

    cout << l << endl;
    print_list(l);
    cout << endl;       
}
				
لیست‌های پیوندی - پیاده‌سازی در قالب کلاس

در این مثال لست‌ پیوندی دوطرفه به صورت یک کلاس پیاده‌سازی می‌شود. با وجود این که هر اشاره‌گر به Node را می‌توان به عنوان عنصر اول یک لیست پیوندی درنظر گرفت، مخفی‌سازی جزئیات پیاده‌سازی انگیزه‌ی ما برای بسته‌بندی لیست پیوندی در یک کلاس مجزا است.

2_BasicLinkedList.cpp
#include <iostream>
using namespace std;

class Node {
public:
    Node(int d, Node *n = NULL, Node *p = NULL) 
        : data(d), next(n), prev(p) {}

    int data;
    Node *next;
    Node *prev;
};

class List {
public:
    List();
    ~List();
    void print();
    void push_front(int x);
    void push_back(int x);
    Node* head() { return _head; }
    Node* last() { return _last; }
    void clear();
private:
    Node* _head;
    Node* _last;
};

List::List() {
    _head = NULL;
    _last = NULL;
}

void List::print() {
    for (Node* p = _head; p != NULL; p = p->next)
        cout << p->data << ' ';
}

void List::push_front(int x) {
    Node *new_node = new Node(x);
    new_node->next = _head;
    if (_head != NULL)
        _head->prev = new_node;
    _head = new_node;
    if (_last == NULL)
        _last = new_node;
}

void List::push_back(int x) {
    if (_head == NULL)
        push_front(x);
    else {
        Node *new_node = new Node(x);
        new_node->prev = _last;
        _last->next = new_node;
        _last = new_node;
    }
}

List::~List() {
    clear();
}

void List::clear() {
    Node *p = _head;
    while (p != NULL) {
        Node *q = p;
        p = p->next;
        delete q;
    }
    _head = NULL;
    _last = NULL;
}

int main() {
    List l;
    
    l.push_back(86);
    l.push_front(43);
    l.push_front(12);
    
    l.print();
    cout << endl;

    int sum = 0;
    for (Node* p = l.head(); p != NULL; p = p->next)
        sum += p->data;        
    cout << sum << endl;


    List l2;
    l2.push_back(1);
    l2.push_back(2);
    l2.push_back(3);
}
				
لیست پیوندی با تکرارکننده (iterator)

در مثال قبل دیدیم که دسترسی به عناصر یک لیست پیوندی از طریق دسترسی آزاد به ‌Node های آن مشکل‌ساز است. این مشکل از طریق تکرارکننده‌ها حل می‌شود. در این مثال دسترسی به عناصر لیست پیوندی از طریق تکرارکننده مهیا می‌شود

3_IteratorLinkedList.cpp
#include <iostream>
using namespace std;

class List {
private:
    class Node {
    public:
        Node(int d, Node *n = NULL, Node *p = NULL) 
            : data(d), next(n), prev(p) {}

        int data;
        Node *next;
        Node *prev;
    };

public:
    class Iterator {
    public:
        int next_element() {
            int to_be_returned = current->data;
            current = current->next;
            return to_be_returned;
        }
        bool has_more_elements() {
            return current != NULL;
        }
    private:
        Node *current;
        Iterator(Node* n) { current = n; }
        friend class List;
    };

public:
    List();
    ~List();
    void print();
    void push_front(int x);
    void push_back(int x);
    void clear();
    Iterator get_iterator() {
        return Iterator(_head);
    }
private:
    Node* _head;
    Node* _last;
};


int main() {
    List l;
    
    l.push_back(86);
    l.push_front(43);
    l.push_front(12);
    
    l.print();
    cout << endl;

    int sum = 0;
    
    List::Iterator it = l.get_iterator();
    while (it.has_more_elements())
        sum += it.next_element();
        
    cout << sum << endl;
}