자료구조
연결 리스트 다른 이름으로는 링크드 리스트(Linked List)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 선형 자료구조이다. 이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 된다.
연결 리스트의 종류로는 단일, 이중, 환형 연결 리스트가 존재한다.
리스트는 연결 리스트를 의미하는가?
아니다 리스트라는 자료구조는 구현 방법에 따라서 크게 두 가지로 나뉜다.
- 순차 리스트: 배열을 기반으로 구현된 리스트
- 연결 리스트: 메모리의 동적 할당을 기반으로 구현된 리스트
연결 리스트의 삽입 삭제
더미 노드를 가지는 연결 리스트의 삽입 삭제 과정이다. 더미 노드를 추가하는 이유는 노드를 추가, 삭제, 조회를 더 간결하게 하기 위해서이다.
여기서 5라는 데이터를 추가로 삽입했을 때의 과정은 아래와 같다.
curr가 nullptr가 나올 때까지 반복문을 돌며 curr가 nullptr이면 데이터가 없는 것 이기 때문에 새로운 노드를 여기에 추가를 한다.
위와 같은 과정을 통해 노드에 새로운 데이터가 삽입이 된다.
이번에는 특정 노드를 삭제하고자 한다.
여기서 중간에 있는 6 노드를 삭제한다.
curr 포인터가 삭제하고자 하는 데이터를 가지고 있는 노드에 도착할 때까지 반복문을 돌고 해당하는 노드에 도착을 하면 pred노드의 next을 curr노드의 next로 바꿔준다.
그 후 curr가 가리키고 있는 노드를 Delete를 하여 메모리 릭(memory leak)이 생기지 않도록 한다.
소스코드
|
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
|
#pragma once
#include<iostream>
template <class T>
class pList {
private:
class Node {
public:
Node* next_;
T data_;
Node() :data_(), next_(nullptr) {}
Node(T data) :data_(data), next_(nullptr) {}
};
Node head_;
size_t size_;
public:
pList() :size_(0) {}
void InitNode(T data) {
Node* pred;
Node* curr;
pred = &head_;
curr = pred->next_;
while (true) {
if (curr == nullptr) {
Node* node = new Node(data);
node->next_ = curr;
pred->next_ = node;
break;
}
pred = pred->next_;
curr = pred->next_;
}
}
void DeleteNode(T data) {
Node* pred;
Node* curr;
pred = &head_;
curr = pred->next_;
while (true) {
if (curr->data_ == data) {
pred->next_ = curr->next_;
delete curr;
break;
}
pred = pred->next_;
curr = pred->next_;
}
}
void DisplayNode() {
Node* curr = head_.next_;
while (curr != nullptr) {
std::cout << curr->data_ << "-->";
curr = curr->next_;
}
std::cout << "\n";
}
};
|
후기
연결 리스트를 구현해보았다. 다른 자료구조에 비해 늦게 구현한 감이 있는대 그래프 자료구조에 사용할 연결 리스트가 없어서 간단한 연결 리스트 구현을 하였다.
출처 및 레퍼런스
Wiki: https://ko.wikipedia.org/wiki/연결_리스트
Book: 윤성우의 열혈 자료구조
그림: 본인