[자료구조] 1. Linked List
오늘은 Linked List에 대해 배웠다...
Linked List에 관하여
- Linked List는 연쇄반응처럼 어떤 node 하나가 다른 node를 가리키고 있는 것들의 집합을 말한다.
- 각 node에는 data field와 link field가 있다.
- 이 node들이 연결되어 하나의 list를 만드는데,
- 이 중 맨 처음의 node를 head라고 부르고 맨 마지막의 node를 tail이라고 부른다.
List에는 단일연결 List와 Double Linked List가 있다.
- 이 중 단일 연결 list같은 경우에는 link field에 오직 next node만을 가지고 있다. 이렇게 되면 어떤 node를 사용할 때 previous node에 접근하고 싶다면 다시 head node에서부터 그 node까지 가야만 한다.
- 이러한 문제점을 해결하기 위해 어느 훌륭하신 분이 double linked list를 고안하셨다.
- double linked list는 단일 연결 리스트와 다르게 link field에 자기 자신 직전과 직후의 address를 둘 다 저장하고 있다. 이러한 방법을 통해 각 node들에 좀 더 유연하고 자유롭게 access할 수 있다.
단일연결 List의 코드 분석
- 전체 코드
#include<iostream>
using namespace std;
class Node {
int elem;
Node* next;
friend class S_LinkedList;
};
class S_LinkedList {
public:
S_LinkedList();
int List_size();
bool Empty();
void Print();
void Append(int elem);
int Delete(int idx);
void insert(int idx, int elem);
private:
Node* head;
Node* tail;
};
S_LinkedList::S_LinkedList() {
head = new Node;
tail = new Node;
head = nullptr;
tail = NULL;
}
bool S_LinkedList::Empty() {
return(head == NULL && tail == NULL);
}
int S_LinkedList::List_size() {
int list_size = 0;
if (Empty()) return list_size;
else {
Node* cur_node = head;
while (cur_node->next != NULL) {
list_size++;
cur_node = cur_node->next;
}
list_size++;
return list_size;
}
}
void S_LinkedList::Print() {
if (Empty()) cout << "empty" << endl;
else {
Node* cur_node = head;
while (cur_node->next != NULL) {
cout << cur_node->elem << ' ';
cur_node = cur_node->next;
}
cout << cur_node->elem << endl;
}
}
void S_LinkedList::Append(int elem) {
Node* new_node = new Node;
new_node->elem = elem;
new_node->next = NULL;
if (Empty()) {
head = new_node;
tail = new_node;
}
else {
tail->next = new_node;
tail = tail->next;
}
}
int S_LinkedList::Delete(int idx) {
int removeNum = 0;
int cnt = 0;
Node* cur_node;
Node* pre_node;
if (Empty() || List_size() <= idx) return -1;
else if (idx == 0) {
if (List_size() == 1) {
removeNum = head->elem;
tail = NULL;
head = NULL;
}
else {
cur_node = head;
removeNum = cur_node->elem;
head = cur_node->next;
}
}
else {
pre_node = cur_node = head;
while (cnt != idx) {
pre_node = cur_node;
cur_node = cur_node->next;
cnt++;
}
removeNum = cur_node->elem;
pre_node->next = cur_node->next;
if (cur_node == tail) tail = pre_node;
}
return removeNum;
}
void S_LinkedList::insert(int idx, int elem) {
Node* new_node = new Node;
new_node->elem = elem;
Node* pre_node;
Node* cur_node;
int cur_idx = 0;
if (idx == 0) {
if (Empty()) {
head = new_node;
tail = new_node;
}
else {
new_node->next = head;
head = new_node;
}
}
else if (idx<0 || idx>List_size()) cout << "index Error" << endl;
else if (idx == List_size()) Append(elem);
else {
pre_node = cur_node = head;
while (cur_idx != idx) {
pre_node = cur_node;
cur_node = cur_node->next;
cur_idx++;
}
pre_node->next = new_node;
new_node->next = cur_node;
}
}
- 단일 연결 리스트의 코드 분석
#include<iostream>
using namespace std;
class Node {
int elem;
Node* next;
friend class S_LinkedList;
};
node라는 class를 만든다. 각 node에는 elem라는 data와 next라는 이름의 주소가 있다. next에는 다음 node의 주소가 담길 예정이다. S_LinkedList는 각 node들을 가지고 전체 list를 만들어 줄 class다. 여기에서 node들을 활용할 수 있도록 friend로 선언해 준다.
class S_LinkedList {
public:
S_LinkedList();
int List_size();
bool Empty();
void Print();
void Append(int elem);
int Delete(int idx);
void insert(int idx, int elem);
private:
Node* head;
Node* tail;
};
S_LinkedList는 각 node들을 가지고 전체 list를 만들어 줄 class다.
- private data로는 기본적으로 head node의 주소와 tail node의 주소를 가지고 있다.
- public에는 유용한 함수들을 만들어 줄 것이다.
- List_size(): 이 리스트 전체의 size를 return해 준다.
- Empty(): 이 리스트의 node가 한 개도 없을 경우 1, 아닐 경우 0을 return한다.
- Print(): 전체 node의 data들을 출력한다.
- Append(int elem): list의 맨 마지막에 node를 추가한다.
- Delete(int idx): idx번째의 node를 삭제한다. 삭제한 node의 data를 return한다.
- insert(int idx, int elem): list의 중간 idx번째에 data가 elem인 node를 삽입한다.
S_LinkedList::S_LinkedList() {
head = new Node;
tail = new Node;
head = nullptr;
tail = NULL;
}
S_LinkedList 클래스의 생성자이다. 인스턴스화시키는 순간 Node*형 변수인 head와 tail을 만들고, nullPtr로 초기화시킨다.
bool S_LinkedList::Empty() {
return(head == NULL && tail == NULL);
}
이 리스트가 비어있는지 아닌지 확인하는 함수이다. node가 한 개라도 있다면 0을 반환하고 아니라면 1을 반환한다. return이 1이 되는 경우는 head와 tail이 둘 다 NULL인 경우이다. head와 tail은 list를 만들 때 생성자에서 기본적으로 만들어주는 pointer들인데, 만들면서 NULL로 초기화시켜 두었다. 이 때 list에 node를 한 번도 추가하지 않았다면 head와 tail은 여전히 NULL로 남아 있을 것이다. node를 한 번도 추가하지 않았다==list에 node가 한 개도 없다. 1을 반환한다.
int S_LinkedList::List_size() {
int list_size = 0;
if (Empty()) return list_size;
else {
Node* cur_node = head;
while (cur_node->next != NULL) {
list_size++;
cur_node = cur_node->next;
}
list_size++;
return list_size;
}
}
이 리스트에 node가 몇 개 있는지를 반환하는 함수이다. 만약 Empty()가 true라면==이 list가 비어 있다면 0을 반환한다. 그렇지 않고 이 list에 node가 적어도 한 개 있는 게 확실하다면 다음의 과정을 통해 list의 size를 반환한다. 맨 먼저 cur_node라는 pointer가 head를 가리키도록 한다. 그 다음 cur_node가 가리키고 있는 node의 next가 NULL인지 확인한다. 만약 가리키고 있는 node의 next가 NULL이라면 cur_node의 다음 node는 tail이라는 것이고, 아니라면 tail이 아니라는 것이다. list_size는 일종의 counter다. 그 다음 node가 tail이 되기 전까지 쭉 1씩 늘리는 과정을 반복한다. 그리고 현재의 cur_node를 다음의 cur_node로 업데이트해준다. 업데이트는 그 cur_node의 next 멤버데이터를 사용해서 그 주소를 역참조해 할당해주는 방식으로 한다.
void S_LinkedList::Print() {
if (Empty()) cout << "empty" << endl;
else {
Node* cur_node = head;
while (cur_node->next != NULL) {
cout << cur_node->elem << ' ';
cur_node = cur_node->next;
}
cout << cur_node->elem << endl;
}
}
각 node들을 돌면서 data들을 출력하는 함수이다. Empty()가 true라면 당연히 empty를 출력한다. 아닐 경우에는 또 cur_node포인터를 만들어서 일단 head를 가리키게 한다. 그리고 다음 node가 tail이 아닌 한 그 node의 data를 출력하고, cur_node가 다음 node를 가리키도록 업데이트한다. 마지막엔 tail 전 node가 출력되었고, cur_node는 tail node를 가리키고 있을 것이다. cur_node가 가리키고 있는 tail node의 data를 출력하고 끝낸다.
