반응형

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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
#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 >>
Crocus






반응형

'Applied > 자료구조' 카테고리의 다른 글

힙(Heap) 자료구조  (4) 2018.03.04
[STL] deque 구현  (2) 2018.02.28
[STL] Pair 구현  (0) 2018.01.26
[STL] Vector 구현  (0) 2018.01.26
트라이(Trie) 자료구조  (6) 2017.10.18