Linked List(연결 리스트)

연결 리스트(Linked List)

연결 리스트는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다.

이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데,

노드의 포인터가 다음이나 이전의 노드와의 연결을 담당한다. 종류에는 단일, 이중, 원형 등의 연결 리스트가 있다.

배열이나 트리 구조와는 달리 특정 위치의 데이터를 검색해 내는데에는 O(n)의 시간이 걸리는 단점도 있다.

보통 조회가 드물고 추가, 삽입, 삭제가 잦은곳에 사용한다.

::보통 삽입/삭제 시 시간복잡도가 O(1)이라고 하는데, 그 위치를 찾아가는데 O(n)만큼 걸리므로 실제로는 O(n)::

*출저 : 위키백과

1) 선형 연결 리스트

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
178
179
180
template <typename T>
class LinkedList {
private:
    class Node {
 
    public:
        T data;
        Node* nextNode;
    };
 
    void valid(int);
    int size;
    Node *Head = new Node;
 
public:
    LinkedList();
    ~LinkedList();
    T get_data(int);
    bool isEmpty();
    int get_size();
    void insert(T);
    void insert(T, int);
    void change(T, int);
    void remove(int);
};
 
template<typename T>
LinkedList<T>::LinkedList() {
    LinkedList::Head->data = NULL;
    LinkedList::Head->nextNode = NULL;
    LinkedList::size = 0;
}
 
template<typename T>
LinkedList<T>::~LinkedList() {
    Node *t = LinkedList::Head;
    Node *de = LinkedList::Head;
 
    for (int i = 0; i < LinkedList::size; i++) {
        t = t->nextNode;
        delete de;
        de = t;
    }
}
 
template<typename T>
void LinkedList<T>::valid(int Count) {
    if (Count > LinkedList::size) {
        throw "Error : 유효하지 않은 index입니다.";
    }
}
 
template<typename T>
bool LinkedList<T>::isEmpty() {
    return LinkedList::size > 0 ? false : true;
}
 
template<typename T>
int LinkedList<T>::get_size() {
    return LinkedList::size;
}
 
template<typename T>
T LinkedList<T>::get_data(int index) {
    try {
        valid(index);
    }
    catch (const char* msg) {
        cout << msg << endl;
        return NULL;
    }
 
    Node* temp = LinkedList::Head;
    for (int i = 0; i < index; i++) {
        temp = temp->nextNode;
    }
    return temp->data;
}
 
template<typename T>
void LinkedList<T>::insert(T data) {
    Node * NewNode = new Node;
    NewNode->data = data;
    NewNode->nextNode = NULL;
 
    if (LinkedList::Head->data == NULL) {
        LinkedList::Head = NewNode;
    }
    else {
        Node* temp = LinkedList::Head;
        while (temp->nextNode != NULL) {
            temp = temp->nextNode;
        }
        temp->nextNode = NewNode;
    }
 
    LinkedList::size++;
}
 
template<typename T>
void LinkedList<T>::insert(T data, int index) {
    try {
        valid(index);
    }
    catch (const char* msg) {
        cout << msg << endl;
        return;
    }
 
    Node * NewNode = new Node;
    NewNode->data = data;
    NewNode->nextNode = NULL;
 
    if (LinkedList::Head->data == NULL) {
        LinkedList::Head = NewNode;
    }
    else if (LinkedList::Head->nextNode == NULL) {
        LinkedList::Head->nextNode = NewNode;
    }
    else {
        Node* temp = LinkedList::Head;
        for (int i = 0; i < index - 1; i++) {
            temp = temp->nextNode;
        }
        NewNode->nextNode = temp->nextNode;
        temp->nextNode = NewNode;
    }
 
    LinkedList::size++;
}
 
template<typename T>
void LinkedList<T>::change(T data, int index) {
    try {
        valid(index);
    }
    catch (const char* msg) {
        cout << msg << endl;
        return;
    }
 
    Node* temp = LinkedList::Head;
 
    for (int i = 0; i < index; i++) {
        temp = temp->nextNode;
    }
 
    temp->data = data;
}
 
template<typename T>
void LinkedList<T>::remove(int index) {
    try {
        valid(index);
    }
    catch (const char* msg) {
        cout << msg << endl;
        return;
    }
 
    Node* temp = LinkedList::Head;
    Node* remove = LinkedList::Head;
 
    if (index == 0) {
        LinkedList::Head = LinkedList::Head->nextNode;
    }
    else {
        for (int i = 0; i < index - 1; i++) {
            temp = temp->nextNode;
            remove = remove->nextNode;
        }
        remove = remove->nextNode;
 
        temp->nextNode = remove->nextNode;
    }
 
    remove->nextNode = NULL;
    delete remove;
    LinkedList::size--;
}
Colored by Color Scripter
cs

2) 원형 연결 리스트

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
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
template <typename T>
class LinkedList {
private:
    class Node {
 
    public:
        T data;
        Node* nextNode;
        Node* preNode;
    };
 
    void valid(int);
    int size;
    Node *Head = new Node;
 
public:
    LinkedList();
    ~LinkedList();
    T get_data(int, bool);
    bool isEmpty();
    int get_size();
    void insert(T);
    void insert(T, int);
    void change(T, int);
    void remove(int);
};
 
template<typename T>
LinkedList<T>::LinkedList() {
    LinkedList::Head->data = NULL;
    LinkedList::Head->nextNode = Head;
    LinkedList::Head->preNode = Head;
    LinkedList::cur = LinkedList::Head;
    LinkedList::size = 0;
}
 
template<typename T>
LinkedList<T>::~LinkedList() {
    Node *t = LinkedList::Head;
    Node *de = LinkedList::Head;
 
    for (int i = 0; i < LinkedList::size; i++) {
        t = t->nextNode;
        delete de;
        de = t;
    }
}
 
template<typename T>
void LinkedList<T>::valid(int Count) {
    if (Count > LinkedList::size) {
        throw "Error : 유효하지 않은 index입니다.";
    }
}
 
template<typename T>
bool LinkedList<T>::isEmpty() {
    return LinkedList::size > 0 ? false : true;
}
 
template<typename T>
int LinkedList<T>::get_size() {
    return LinkedList::size;
}
 
template<typename T>
T LinkedList<T>::get_data(int index, bool dir) {
    try {
        valid(index);
    }
    catch (const char* msg) {
        cout << msg << endl;
        return NULL;
    }
 
    Node* temp = LinkedList::Head;
 
    if (dir) {
        for (int i = 0; i < index; i++) {
            temp = temp->nextNode;
        }
    }
    else if (!dir) {
        for (int i = 0; i < index; i++) {
            temp = temp->preNode;
        }
    }
    return temp->data;
}
 
template<typename T>
void LinkedList<T>::insert(T data) {
    Node * NewNode = new Node;
    NewNode->data = data;
    NewNode->nextNode = NewNode;
    NewNode->preNode = NewNode;
 
    if (LinkedList::Head->data == NULL) {
        LinkedList::Head = NewNode;
    }
    else {
        Node* temp = LinkedList::Head;
        for (int i = 0; i < LinkedList::size - 1; i++) {
            temp = temp->nextNode;
        }
        temp->nextNode = NewNode;
        NewNode->preNode = temp;
        NewNode->nextNode = LinkedList::Head;
        LinkedList::Head->preNode = NewNode;
    }
 
    LinkedList::size++;
}
 
template<typename T>
void LinkedList<T>::insert(T data, int index) {
    try {
        valid(index);
    }
    catch (const char* msg) {
        cout << msg << endl;
        return;
    }
 
    Node * NewNode = new Node;
    NewNode->data = data;
    NewNode->nextNode = NewNode;
    NewNode->preNode = NewNode;
 
    if (LinkedList::Head->data == NULL) {
        LinkedList::Head = NewNode;
    }
    else if (LinkedList::Head->nextNode == LinkedList::Head) {
        LinkedList::Head->nextNode = NewNode;
        LinkedList::Head->preNode = NewNode;
        NewNode->nextNode = LinkedList::Head;
        NewNode->preNode = LinkedList::Head;
    }
    else {
        Node* temp = LinkedList::Head;
        for (int i = 0; i < index - 1; i++) {
            temp = temp->nextNode;
        }
        NewNode->nextNode = temp->nextNode;
        NewNode->preNode = temp;
        temp->nextNode = NewNode;
    }
 
    LinkedList::size++;
}
 
template<typename T>
void LinkedList<T>::change(T data, int index) {
    try {
        valid(index);
    }
    catch (const char* msg) {
        cout << msg << endl;
        return;
    }
 
    Node* temp = LinkedList::Head;
 
    for (int i = 0; i < index; i++) {
        temp = temp->nextNode;
    }
 
    temp->data = data;
}
 
template<typename T>
void LinkedList<T>::remove(int index) {
    try {
        valid(index);
    }
    catch (const char* msg) {
        cout << msg << endl;
        return;
    }
 
    Node* temp = LinkedList::Head;
    Node* remove = LinkedList::Head;
 
    if (index == 0) {
        LinkedList::Head = LinkedList::Head->nextNode;
    }
    else {
        for (int i = 0; i < index - 1; i++) {
            temp = temp->nextNode;
            remove = remove->nextNode;
        }
        remove = remove->nextNode;
 
        temp->nextNode = remove->nextNode;
        remove->nextNode->preNode = temp;
    }
 
    remove->nextNode = NULL;
    delete remove;
    LinkedList::size--;
}
Colored by Color Scripter
cs

3) 원형 이중 연결 리스트

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
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
template <typename T>
class LinkedList {
private:
    class Node {
 
    public:
        T data;
        Node* nextNode;
        Node* preNode;
    };
 
    void valid(int);
    int size;
    Node *Head = new Node;
    Node *cur;
 
public:
    LinkedList();
    ~LinkedList();
    T get_data(int, bool);
    bool isEmpty();
    int get_size();
    void insert(T);
    void insert(T, int);
    void change(T, int);
    void remove(int, bool);
};
 
template<typename T>
LinkedList<T>::LinkedList() {
    LinkedList::Head->data = NULL;
    LinkedList::Head->nextNode = Head;
    LinkedList::Head->preNode = Head;
    LinkedList::cur = LinkedList::Head;
    LinkedList::size = 0;
}
 
template<typename T>
LinkedList<T>::~LinkedList() {
    Node *t = LinkedList::Head;
    Node *de = LinkedList::Head;
 
    for (int i = 0; i < LinkedList::size; i++) {
        t = t->nextNode;
        delete de;
        de = t;
    }
}
 
template<typename T>
void LinkedList<T>::valid(int Count) {
    if (Count > LinkedList::size) {
        throw "Error : 유효하지 않은 index입니다.";
    }
}
 
template<typename T>
bool LinkedList<T>::isEmpty() {
    return LinkedList::size > 0 ? false : true;
}
 
template<typename T>
int LinkedList<T>::get_size() {
    return LinkedList::size;
}
 
template<typename T>
T LinkedList<T>::get_data(int index, bool dir) {
 
    Node* temp = LinkedList::cur;
 
    if (dir) {
        for (int i = 0; i < index; i++) {
            temp = temp->nextNode;
        }
    }
    else if (!dir) {
        for (int i = 0; i < index; i++) {
            temp = temp->preNode;
        }
    }
    return temp->data;
}
 
template<typename T>
void LinkedList<T>::insert(T data) {
    Node * NewNode = new Node;
    NewNode->data = data;
    NewNode->nextNode = NewNode;
    NewNode->preNode = NewNode;
 
    if (LinkedList::Head->data == NULL) {
        LinkedList::Head = NewNode;
        LinkedList::cur = Head;
    }
    else {
        Node* temp = LinkedList::Head;
        for (int i = 0; i < LinkedList::size - 1; i++) {
            temp = temp->nextNode;
        }
        temp->nextNode = NewNode;
        NewNode->preNode = temp;
        NewNode->nextNode = LinkedList::Head;
        LinkedList::Head->preNode = NewNode;
    }
 
    LinkedList::size++;
}
 
template<typename T>
void LinkedList<T>::insert(T data, int index) {
 
    Node * NewNode = new Node;
    NewNode->data = data;
    NewNode->nextNode = NewNode;
    NewNode->preNode = NewNode;
 
    if (LinkedList::Head->data == NULL) {
        LinkedList::Head = NewNode;
        LinkedList::cur = Head;
    }
    else if (LinkedList::Head->nextNode == LinkedList::Head) {
        LinkedList::Head->nextNode = NewNode;
        LinkedList::Head->preNode = NewNode;
        NewNode->nextNode = LinkedList::Head;
        NewNode->preNode = LinkedList::Head;
    }
    else {
        Node* temp = LinkedList::Head;
        for (int i = 0; i < index - 1; i++) {
            temp = temp->nextNode;
        }
        NewNode->nextNode = temp->nextNode;
        NewNode->preNode = temp;
        temp->nextNode = NewNode;
    }
 
    LinkedList::size++;
}
 
template<typename T>
void LinkedList<T>::change(T data, int index) {
 
    Node* temp = LinkedList::Head;
 
    for (int i = 0; i < index; i++) {
        temp = temp->nextNode;
    }
 
    temp->data = data;
}
 
template<typename T>
void LinkedList<T>::remove(int index, bool dir) {
 
    Node* temp = LinkedList::cur;
    Node* remove = LinkedList::cur;
 
    if (cur == Head && index == 0) {
        if (LinkedList::size == 1) {
            delete remove;
            LinkedList::size--;
            LinkedList::Head = NULL;
            return;
        }
        else {
            LinkedList::Head->preNode->nextNode = Head->nextNode;
            LinkedList::Head->nextNode->preNode = Head->preNode;
            LinkedList::Head = LinkedList::Head->preNode;
        }
    }
    else if(dir){
        for (int i = 0; i < index - 1; i++) {
            temp = temp->nextNode;
            remove = remove->nextNode;
        }
        remove = remove->nextNode;
 
        temp->nextNode = remove->nextNode;
        remove->nextNode->preNode = temp;
 
        if (remove == LinkedList::Head) {
            LinkedList::Head->preNode->nextNode = Head->nextNode;
            LinkedList::Head->nextNode->preNode = Head->preNode;
            LinkedList::Head = LinkedList::Head->preNode;
        }
    }
    else if (!dir){
        for (int i = 0; i < index; i++) {
            temp = temp->preNode;
            remove = remove->preNode;
        }
        temp = temp->preNode;
 
        temp->nextNode = remove->nextNode;
        remove->nextNode->preNode = temp;
 
        if (remove == LinkedList::Head) {
            LinkedList::Head->preNode->nextNode = Head->nextNode;
            LinkedList::Head->nextNode->preNode = Head->preNode;
            LinkedList::Head = LinkedList::Head->preNode;
        }
    }
 
    LinkedList::cur = remove->preNode;
    LinkedList::cur->nextNode = remove->nextNode;
    remove->nextNode = NULL;
    remove->preNode = NULL;
    delete remove;
    LinkedList::size--;
}
 
Colored by Color Scripter
cs

[연결 리스트 예제 : http://gyutts.tistory.com/68]

[원형 연결 리스트 예제 : http://gyutts.tistory.com/63]

[원형 이중 연결 리스트 예제 : http://gyutts.tistory.com/64]

저작자표시

'Programming > Data Structure' 카테고리의 다른 글

Hash Table(해시 테이블) (0)	2018.08.05
Heap(힙) & Priority Queue(우선순위 큐) (0)	2018.06.30

Developer Q.bot

Linked List(연결 리스트)

'Programming > Data Structure' 카테고리의 다른 글

티스토리툴바

Linked List(연결 리스트)

'Programming > Data Structure' 카테고리의 다른 글

'Programming/Data Structure' Related Articles

티스토리툴바