Linked List
linked list는 데이터를 저장하는 구조 중 하나로 여러 개의 노드가 포인터로 연결된 선형 데이터 구조이다.
해당 자료구조는 구조체(혹은 클래스) 안에 저장할 데이터와 노드를 갖고 있다.
Linked List vs Array
linked list는 array와 비교했을 때 장단점이 존재한다.
먼저 장점으로는
특정 데이터를 제거하거나 저장하려고 하면 array는 항상 O(n)의 시간복잡도를 갖지만 linked list는 O(n-k)의 시간복잡도를 갖기 때문에 해당 작업에서 빠른 속도를 보인다. (최악의 경우에는 동일하다)
이때 특히 맨 앞의 데이터를 삽입하거나 제거하려고 할 때 linked list는 O(1)의 시간복잡도를 갖는다.
단점으로는
특정한 위치의 데이터에 접근하려고 할 때의 linked list의 시간복잡도는 O(n-k)이지만 array의 시간복잡도는 O(1)이다.
node
linked list에서 node는 연결된 구조체가 있는 위치를 가르키는 포인터이다.
따라서 만약 class node를 선언했다면 해당 클래스에서 노드는 *node 타입으로 사용할 수 있다.
class node {
private:
node* link_field; // 노드
};
다음 클래스의 위치를 가리켜야하기 때문에 노드의 데이터 타입은 node* 일 수 밖에 없는 것이다.
여기에 저장할 데이터 자료형을 추가하면 아래 코드처럼 작성할 수 있다.
#include <iostream>
class node {
private:
typedef double value_type;
value_type data_field;
node* link_field;
public:
node(const value_type& init_data = value_type(), node* init_link = nullptr)
:data_field(init_data), link_field(init_link) { }
};
캡슐화
private로 선언된 필드에 접근하는 메서드를 구현함으로써 캡슐화를 통해 안정성을 높일 수 있다.
void set_data(const value_type& new_data) {
data_field = new_data;
}
void set_link(node* new_link) {
link_field = new_link;
}
value_type data() const {
return data_field;
}
node* link() const {
return link_field;
}
length
linked list에서 length를 구하는 방법은 아래 코드와 같다.
size_t list_length(const node* header) {
size_t answer = 0;
const node* cursor = nullptr;
for (cursor = header; cursor != nullptr; cursor = cursor->link())
answer++;
return answer;
}
for문을 통해서 모든 노드를 순회하며 루프가 진행되는 동안 cursor가 계속 다음 노드를 가리키게 한다.
마지막 노드는 nullptr을 가리키고 있기 때문에 cursor가 nullptr을 가리키면 마지막 노드까지 도착한 것이고
이때 answer를 통해 반복된 횟수, 즉 linked list의 length를 반환하는 것이다.
head_insert
linked list의 맨 앞에 데이터를 추가하는 경우 새로 추가할 노드가 현재 맨 앞의 노드를 가리키기만 하면 된다.
따라서 head_insert 는 다음과 같이 구현할 수 있다.
void list_head_insert(node*& head_ptr, const value_type& entry) {
head_ptr = new node(entry, head_ptr);
}
insert
특정 위치에 데이터를 삽입하고 싶을 때에는 해당 위치의 이전 노드가 필요하다.
새로운 노드를 만들고 입력하고 싶은 데이터를 저장한 후 이전 노드가 새로운 노드를 가리키게 하고 이전 노드가 가리키고 있던 노드를 새로운 노드가 가리키면 된다.
따라서 다음과 같이 구현할 수 있다.
void list_insert(node* previous_ptr, const value_type& entry) {
node* nodeindex = new node(entry, previous_ptr->link());
previous_ptr->set_link(nodeindex);
}
이를 축약하여 다음과 같이 사용할 수 있다.
void list_insert(node* previous_ptr, const value_type& entry) {
previous_ptr->set_link(new node(entry, previous_ptr->link()));
}
search
Linked list는 특정 값에 바로 접근할 수 없기 때문에 데이터를 검색하고 싶다면 해당 위치까지 노드를 따라서 순회해야 한다.
따라서 Linked list의 search는 아래와 같이 구현할 수 있다.
node* list_search(node* head_ptr, const value_type& target) {
node* cursor;
for (cursor = head_ptr; cursor != nullptr; cursor = cursor->link_field)
if (target == cursor->data_field)
return cursor;
return nullptr;
}
locate
lcoate는 특정 위치의 노드를 반환하는 역할을 한다.
search와 마찬가지로 해당 위치까지 노드를 따라서 순회해야 한다.
따라서 Linked list의 locate는 아래와 같이 구현할 수 있다.
node* list_locate(node* head_ptr, size_t position) {
node* cursor = head_ptr;
for (int i = 0; cursor != nullptr && i < position; i++)
cursor = cursor->link_field;
return cursor;
}
copy
두 개의 노드를 입력받아 하나는 복사받을 노드의 시작점으로 사용하고 다른 하나는 복사할 노드에서 복사받을 노드로 데이터를 옮기는 용도로 사용할 수 있다.
이때 복사받을 노드를 옮기는 용도로 사용한 노드는 tail node로 사용할 수 있다.
따라서 Linked list의 copy는 아래코드처럼 구현할 수 있다.
void list_copy(const node* source_ptr, node*& head_ptr, node*& tail_ptr) {
head_ptr = nullptr;
tail_ptr = nullptr;
if (source_ptr == nullptr)
return;
list_head_insert(head_ptr, source_ptr->data());
tail_ptr = head_ptr;
source_ptr = source_ptr->link_field;
while (source_ptr != nullptr) {
list_insert(tail_ptr, source_ptr->data_field);
tail_ptr = tail_ptr->link_field;
source_ptr = source_ptr->link_field;
}
}
먼저 head_ptr과 tail_ptr을 초기화해주고 복사할 값이 있는지 확인해 준다.
이후 head_insert()를 통해 head_ptr에 첫 번째 데이터를 입력해 주고 source_ptr은 다음 값을 가리키도록 한다.
이때 source_ptr은 참조자가 없기 때문에 복사본을 생성하여 가져오므로 원본 데이터의 손실 가능성은 없다.
이후 while문에서 list_insert()에 nullptr을 가리키는 노드는 들어갈 수 없기 때문에 tail_ptr = head_ptr; 을 통해 head_ptr이 nullptr을 가리키는 것을 막고 있다.
또한 tail_ptr은 복사된 source_ptr의 다음 노드의 주소값에도 접근하여야 하기 때문에 tail_ptr = head_ptr; 은 필수적이다.
마지막으로 while문에서 tail_ptr에 source_ptr의 값을 복사해 오고 tail_ptr은 다음 노드를 가리키도록 한다.
그럼 head_ptr의 node는 복사된 source_ptr의 2번째 node를 가리키고 있었는데
이제 tail_ptr이 2번째 node가 되고 3번째 node를 가리키고 있게 된다.
그리고 source_ptr의 다음 노드에 접근하고 위 과정을 반복해 준다.
그럼 tail_ptr에는 이제 3번째 node가 들어가고 4번째 node를 가리키고 있게 되는 것이다.
이런 식으로 tail_ptr은 계속 지나가면서 node의 주소값의 체인을 만들어주는 역할을 하게 되는 것이다.
(발자국을 남기는 듯한?)
head_remove
head_remove는 가장 첫 노드의 데이터를 제거하는 역할을 한다.
가장 첫 번째 노드의 데이터를 제거하려면 두 번째 노드를 head node로 만들어주면 된다.
따라서 빈 노드인 remove_ptr을 생성해 주고 해당 노드에 head node를 넣고 head_ptr에는 두 번째 노드를 넣는다.
이후 사용하지 않는 remove_ptr의 메모리를 해제해 주면 된다.
따라서 아래 코드처럼 구현하여 사용할 수 있다.
void list_head_remove(node*& head_ptr) {
node* remove_ptr;
remove_ptr = head_ptr;
head_ptr = remove_ptr->link();
delete remove_ptr;
}
remove
remove는 특정 위치의 노드의 데이터를 제거하는 역할을 한다.
이때에도 insert처럼 해당 위치의 이전노드를 인자로 요구한다.
원리는 head_remove와 동일한데 임시 노드에 제거할 노드를 저장하고 이전 노드는 제거할 노드의 다음 노드를 가리키면 된다.
이후 사용하지 않는 임시 노드는 메모리 해제해 준다.
따라서 아래 코드처럼 구현하여 사용할 수 있다.
void list_remove(node* previous_ptr) {
node* remove_ptr;
remove_ptr = previous_ptr->link();
previous_ptr->set_link(remove_ptr->link());
delete remove_ptr;
}
clear
clear는 head_remove를 사용하여 가장 앞의 노드를 계속 제거해 주면 된다.
따라서 아래 코드처럼 작성하여 모든 메모리를 반환할 수 있다.
void list_clear(node*& head_ptr) {
while (head_ptr != nullptr)
list_head_remove(head_ptr);
}
최종 코드
Linked List를 구현한 코드는 아래와 같다.
class node {
private:
typedef double value_type;
value_type data_field;
node* link_field;
public:
node(const value_type& init_data = value_type(), node* init_link = nullptr) {
data_field = init_data;
link_field = init_link;
}
void set_data(const value_type& new_data) {
data_field = new_data;
}
void set_link(node* new_link) {
link_field = new_link;
}
value_type data() const {
return data_field;
}
node* link() const {
return link_field;
}
size_t list_length(const node* header) {
size_t answer = 0;
const node* cursor = nullptr;
for (cursor = header; cursor != nullptr; cursor = cursor->link())
answer++;
return answer;
}
void list_head_insert(node*& head_ptr, const value_type& entry) {
head_ptr = new node(entry, head_ptr);
}
void list_insert(node* previous_ptr, const value_type& entry) {
previous_ptr->set_link(new node(entry, previous_ptr->link()));
}
node* list_search(node* head_ptr, const value_type& target) {
node* cursor;
for (cursor = head_ptr; cursor != nullptr; cursor = cursor->link_field)
if (target == cursor->data_field)
return cursor;
return nullptr;
}
node* list_locate(node* head_ptr, size_t position) {
node* cursor = head_ptr;
for (int i = 0; cursor != nullptr && i < position; i++)
cursor = cursor->link_field;
return cursor;
}
void list_copy(const node* source_ptr, node*& head_ptr, node*& tail_ptr) {
head_ptr = nullptr;
tail_ptr = nullptr;
if (source_ptr == nullptr)
return;
list_head_insert(head_ptr, source_ptr->data());
tail_ptr = head_ptr;
source_ptr = source_ptr->link_field;
while (source_ptr != nullptr) {
list_insert(tail_ptr, source_ptr->data_field);
tail_ptr = tail_ptr->link_field;
source_ptr = source_ptr->link_field;
}
}
void list_head_remove(node*& head_ptr) {
node* remove_ptr;
remove_ptr = head_ptr;
head_ptr =remove_ptr->link();
delete remove_ptr;
}
void list_remove(node* previous_ptr) {
node* remove_ptr;
remove_ptr = previous_ptr->link();
previous_ptr->set_link(remove_ptr->link());
delete remove_ptr;
}
void list_clear(node*& head_ptr) {
while (head_ptr != nullptr)
list_head_remove(head_ptr);
}
};