[STL] list 구현

더미 노드를 이용한 이중 링크드 리스트

#include <iostream>
#include <cstdio>
 
using namespace std;
 
class NODE {
    friend class LIST;
 
private:
    int data;
    NODE *left;
    NODE *right;
};
 
class LIST {
private:
    int sz;
    NODE *head;
    NODE *tail;
 
public:
    LIST() {
        //cout << "\n\n생성자 호출\n\n" << endl;
        sz = 0;
        NODE *dummyHead = new NODE;
        NODE *dummyTail = new NODE;
 
        dummyHead->left = dummyHead->right = NULL;
        dummyTail->left = dummyTail->right = NULL;
 
        head = dummyHead;
        tail = dummyTail;
    }
 
    ~LIST() {
        init();
        delete head;
        delete tail;
 
        //cout << "\n\n소멸자 호출\n\n " << endl; 
    }
 
    void init() {
        // 더미노드 사이 모든 값 삭제
        NODE *pos = head;
        while (pos->right != NULL)
        {
            NODE *delNode = pos;
            pos = pos->right;
 
            delete delNode;
        }
        delete tail; // 마지막 tail이 삭제되지 않았다.
 
                     // 더미노드 새로 생성(생성자와 동일)
        NODE *dummyHead = new NODE;
        NODE *dummyTail = new NODE;
 
        dummyHead->left = dummyHead->right = NULL;
        dummyTail->left = dummyTail->right = NULL;
 
        head = dummyHead;
        tail = dummyTail;
        sz = 0;
    }
    void insert(int val) {
        // 리스트가 형성되어 있지 않았을 때
        if (head->right == NULL)
        {
            NODE *newNode = new NODE;
            newNode->data = val;
 
            newNode->left = head;
            head->right = newNode;
 
            newNode->right = tail;
            tail->left = newNode;
        }
 
        else
        {
            NODE *newNode = new NODE;
            newNode->data = val;
 
            newNode->left = tail->left;
            tail->left->right = newNode;
 
            newNode->right = tail;
            tail->left = newNode;
        }
        sz++;
    }
    void del(int val) {
        NODE *pos = head;
        bool isFind = false;
        while (pos->right != NULL)
        {
            if (pos->data == val)
            {
                pos->left->right = pos->right;
                pos->right->left = pos->left;
                delete pos;
                isFind = true;
                break;
            }
            pos = pos->right;
        }
 
        if (isFind)
            sz--;
        else
            cout << "삭제할 데이터가 없습니다." << endl;
    }
 
    void all() {
        NODE *pos = head;
        while (pos != NULL)
        {
            // 더미노드는 출력하지 않는다.
            if (!(pos == head || pos == tail))
                cout << pos->data << " ";
 
            pos = pos->right;
        }
        cout << endl;
    }
 
    int size() {
        return sz;
    }
};
int main()
{
    LIST list;
    while (1)
    {
        int num;
        cout << "1 :: 초기화\n2 :: 추가\n3 :: 삭제\n4 :: 전체출력\n5 :: 총 개수\n6 :: 종료\n입력 :: ";
        cin >> num;
 
        if (num == 1)
            list.init();
 
        else if (num == 2)
        {
            int val;
            cout << "값 :: ";
            cin >> val;
            list.insert(val);
        }
 
        else if (num == 3)
        {
            int val;
            cout << "값 :: ";
            cin >> val;
            list.del(val);
        }
 
        else if (num == 4)
            list.all();
 
        else if (num == 5)
            cout << list.size() << endl;
 
        else if (num == 6)
            break;
 
        cout << endl;
    }
 
    return 0;
}
 
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>