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

#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;       
}
					

#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;

    l.head()->next = NULL;

    List l2;
    l2.push_back(1);
    l2.push_back(2);
    l2.push_back(3);
    l2.last()->next = l.head()->next;
}
					

#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;
};

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;
    
    List::Iterator it = l.get_iterator();
    while (it.has_more_elements())
        sum += it.next_element();
        
    cout << sum << endl;
}