[Data Structures | C++] Linked List & Array : 링크드리스트 & 배열
배열(Array) #
데이터를 물리적 주소에 순차적으로 저장하며 인덱스를 가지고 있어 바로 접근할 수 있기 때문에 접근 속도가 매우 빠르다.\ 그러나, 배열은 크가가 고정되어 있기 때문에 처음 지정된 사이즈보다 더 많은 데이터를 넣으려면 배열의 크기를 늘리는 연산을 해야하고 데이터 삽입/삭제시 해당 위치 다음칸에 있는 데이터를 모두 한칸씩 뒤로 밀거나 앞으로 당겨오는 연산을 해야하기 때문에 데이터 삽입/삭제에는 약한 모습을 보인다.
연결리스트(LinkedList) #
데이터를 저장할 때 데이터만 저장하는 것이 아니라 다음 데이터의 물리적 주소까지 같이 저장한다.\ (단순 연결리스트는 다음 데이터의 주소를, 이중 연결리스트는 이전 주소와 다음 주소를 모두 저장) 특정 데이터에 접근할 때 인덱스로 바로 접근할 수 있었던 배열과 달리 첫 노드부터 원하는 노드까지 링크를 따라가야 접근이 가능하기 때문에 배열에 비해 접근 속도는 떨어진다.\ 하지만 반대로, 데이터를 삽입/삭제 할 때에는 물리적 주소에 구애받지 않고 앞/뒤 노드의 주소만 끼워넣을 노드의 주소로 바꿔주면 되기 때문에 삽입/삭제는 배열보다 빠르다.
C++로 구현한 양방향 연결 리스트(Double Linked List) #
1/**
2 * 연결리스트(LinkedList)에 사용할 노드 클래스
3 */
4class Node
5{
6private:
7 Node *Llink;
8 Node *Rlink;
9
10 int IDNode;
11 int Data;
12public:
13 Node();
14 ~Node();
15
16
17 Node *getLlink() { return Llink; }
18 Node *getRlink() { return Rlink; }
19
20 void setLlink(Node *llink) { Llink = llink; }
21 void setRlink(Node *rlink) { Rlink = rlink; }
22
23 int getData() { return Data; }
24 void setData(int _Data) { Data = _Data; }
25
26 int GetID() { return IDNode; }
27 void SetID(int idnum) { IDNode = idnum; }
28};
29
30/**
31 * Double Linked List 클래스
32 */
33class DoubleList
34{
35private:
36 Node *Head;
37 Node *Tail;
38 int IDCount;
39public:
40 DoubleList();
41 ~DoubleList();
42
43 Node *getHead() { return Head; }
44 Node *getTail() { return Tail; }
45
46 Node *ArrangeNode(int pos);
47
48 void insertNode(int _data, int _location); //삽입 추가 (위치 입력 가능)
49 void delNode(int _location); //삭제 (위치 입력 가능)
50 void displayNode(); //출력
51 void AllDel(); //모두 삭제
52 int CountNode(); //현재 노드 갯수
53 int Find(int _location); //위치를 찾아 노드 데이터 찾기
54 void Reverse(); //뒤집기
55};
56
57/**
58 * Double Linked List 메뉴
59 */
60void Manager::Doublerun() {
61 int _menu = 0;
62 int find = 0;
63 int Num = 0;
64 int _position = 0;
65
66 while (true) {
67 cout << "1.추가 2.삭제 3.출력 4.전체삭제 5.노드 총 갯수\n6.찾기 7.링크드 뒤집기\n입력 : ";
68 cin >> _menu;
69
70 switch (_menu)
71 {
72 case INSERT:
73 cout << "추가할 정수 : ";
74 cin >> Num;
75 cout << "위치 입력 : ";
76 cin >> _position;
77 doublelist->insertNode(Num, _position);
78 break;
79 case DEL:
80 if (doublelist->getHead() == NULL) {
81 cout << "데이터가 없습니다." << endl << endl;
82 }
83 else {
84 int _location = 0;
85 cout << "데이터 삭제할 위치 : ";
86 cin >> _location;
87 doublelist->delNode(_location);
88 }
89 break;
90 case COUT:
91 if (doublelist->getHead() == NULL) {
92 cout << "데이터가 없습니다." << endl << endl;
93 }
94 else {
95 doublelist->displayNode();
96 }
97 break;
98 case ALLDEL:
99 if (doublelist->getHead() == NULL) {
100 cout << "데이터가 없습니다." << endl << endl;
101 }
102 else {
103 doublelist->AllDel();
104 }
105 break;
106 case COUNTNODE:
107 cout << "총 갯수 : " << doublelist->CountNode() << endl;
108 break;
109 case SEARCH:
110 if (doublelist->getHead() == NULL) {
111 cout << "데이터가 없습니다." << endl << endl;
112 }
113 else {
114 cout << "몇 번째 데이터 : ";
115 cin >> find;
116 cout << "당신이 찾는 데이터 : " << doublelist->Find(find) << endl << endl;
117 }
118 break;
119 case REVERSE:
120 cout << "뒤집기 전 출력 : " << endl;
121 doublelist->displayNode();
122 doublelist->Reverse();
123 cout << "뒤집기 후 출력 : " << endl;
124 doublelist->displayNode();
125 break;
126 default:
127 cout << "다시 입력해주세요" << endl;
128 break;
129 }
130 }
131}
132
133/**
134 * Node 추가
135 */
136void DoubleList::insertNode(int _data, int _position) {
137 ++IDCount;
138 Node *newNode = new Node;
139 newNode->setData(_data);
140 newNode->SetID(IDCount);
141
142 if (Head == NULL) {
143 Head = newNode;
144 Tail = Head;
145 }
146 else {
147 if (_position == 0) {
148 newNode->setRlink(Head);
149 Head->setLlink(newNode);
150 Head = newNode;
151 }
152 else if (_position == -1) {
153 newNode->setLlink(Tail);
154 Tail->setRlink(newNode);
155 Tail = newNode;
156 }
157 else {
158 Node *before = Head;
159 while ((--_position) > 0)
160 {
161 before = before->getRlink();
162 }
163 if (before->getRlink() != NULL) {
164 before->getRlink()->setLlink(newNode);
165 }
166 newNode->setLlink(before);
167 newNode->setRlink(before->getRlink());
168 before->setRlink(newNode);
169 }
170 }
171}
172
173/**
174 * Node 삭제
175 */
176void DoubleList::delNode(int _location) {
177 if (_location == 0) {
178 Head = Head->getRlink();
179 if (Head != NULL) {
180 Head->setLlink(NULL);
181 }
182 }
183 else {
184 Node *before = Head;
185 while ((--_location) > 0)
186 {
187 before = before->getRlink();
188 }
189 Node *after = before->getRlink()->getRlink();
190 if (after != NULL) {
191 before->setRlink(after);
192 after->setLlink(before);
193 }
194 else {
195 before->setRlink(NULL);
196 }
197 }
198}
199
200/**
201 * Node 출력
202 */
203void DoubleList::displayNode() {
204 Node *Temp = Head;
205 while (true)
206 {
207 if (Temp == NULL) {
208 break;
209 }
210 else {
211 cout << "ID:" << Temp->GetID() << " Data:" << Temp->getData() << endl;
212 Temp = Temp->getRlink();
213 }
214 }
215}
216
217/**
218 * Node 모두 삭제
219 */
220void DoubleList::AllDel() {
221 while (true)
222 {
223 if (Head == NULL) {
224 break;
225 }
226 else {
227 delNode(0);
228 }
229 }
230}
231
232/**
233 * 현재 Node 갯수
234 */
235int DoubleList::CountNode() {
236 int count = 0;
237
238 Node *now = new Node;
239 for (now = Head; now; now = now->getRlink()) {
240 count++;
241 }
242 return count;
243}
244
245/**
246 * Node 찾기
247 */
248int DoubleList::Find(int _location) {
249 Node *current = Head;
250 while ((--_location) >= 1) {
251 current = current->getRlink();
252 }
253 return current->getData();
254}
255
256/**
257 * Node 뒤집기
258 */
259void DoubleList::Reverse()
260{
261 Node *current = Head;
262 while (current != NULL)
263 {
264 Node *next = current->getRlink();
265 current->setRlink(current->getLlink());
266 current->setLlink(next);
267 if (next == NULL) {
268 Tail = Head;
269 Head = current;
270 break;
271 }
272 current = next;
273 }
274}Advertisement