[자료구조] Circular Lists

Circular list

The link field of the last node points to the first node

마지막 노드의 link 부분이 첫번째 노드를 가르킨다.

 

#include <iostream>

using namespace std;

template <class T>
struct ChainNode {
    T data;
    ChainNode* link;
    ChainNode() : data(0), link(NULL) {}
    ChainNode(T _data) : data(_data), link(NULL) {}
};

template <class T>
class CircularList {
private:
    ChainNode<T> *first = NULL;
    ChainNode<T> *av = NULL;
public:
    CircularList() {
        first = new ChainNode<T>;
        first->link = first;
    }
    void insertFront(const T& e){
        ChainNode<T> *newNode = GetNode();
        newNode->data = e;
        newNode->link = first->link;
        first->link = newNode;
    }
    
    ChainNode<T>* GetNode(){
        ChainNode<T>* x;
        if(av) {
            x=av;
            av=av->link;
            printf("av\n");
        }
        else {
            x = new ChainNode<T>;
            printf("not av\n");
        }
        return x;
    }
    void InsertRear(const T &item) {
        ChainNode<T> *newNode = new ChainNode<T>(item);
        ChainNode<T> *cur = first->link;
        while (cur->link != first) {
            cur = cur->link;
        }
        cur->link = newNode;
        newNode->link = first;
    }
    void RetNode(ChainNode<T>*& x) {
        x->link=av;
        av=x;
        x=0;
    }
    void Delete(int idx) {
        ChainNode<T> *curr = first->link;
        if (idx < 1)
            cout << "1 이상의 숫자를 입력하셔야합니다" << endl;
        else if(idx==1)
            first->link = curr->link;
        else {
            int count = 1;
            ChainNode<T> *del = first->link;
            while (count < idx) {
                del = del->link;
                count++;
            }
            curr = del->link;
            del->link = curr->link;
        }
        RetNode(curr);
    }
    
    void print() {
        ChainNode<T> *cur;
        for (cur = first->link; cur != first; cur = cur->link) {
            cout << cur->data;
            if (cur->link != first)
                cout << "->";
            else
                cout << " ";
        }
        cout << endl;
    }
};



int main() {
    CircularList<int> list;
    list.insertFront(10);
    list.print();
    list.insertFront(20);
    list.print();
    list.Delete(1);
    list.print();
    list.insertFront(30);
    list.print();
    list.InsertRear(40);
    list.print();
}