[Algorithm] C/C++에서 단순 연결 리스트(Singly Linked List) 구현하기
업데이트(2019.02.03): 코드 일부 수정 및 개선
C++에서 단순 열결 리스트(Singly Linked List)를 구현해보자
환경
- C++
Singly Linked List란?
개념
- 아래처럼 하나의 노드에 필요한 정보를 담고 다음에 해당하는 노드를 가리키고 있는 자료구조로 포인터를 이용해 자료들을 선형으로 연결할 자료구조이다.
배열과 비교했을 때 추가 및 삭제가 쉽다는 장점이 있지만 접근할 때O(n)만큼 걸린다는 단점이 있습니다.
구현
공통
- 구현을 편리하게 하기위해 전역으로 하나의 리스트만 만들었습니다.
- 큰 틀은 아래와 같으면 추가, 삭제 그리고 순회의 경우에 필요한 부분들을 수정하면 됩니다.
list는 리스트의 처음을 가리킵니다.
#include <stdio.h>
#include <stdlib.h>
// Node
struct Node {
int data;
Node * next;
};
// Global list
Node * list;
추가/삭제 공통
- 추가와 삭제의 경우에 첫번째 노드인지 아닌지를 고려해주면 구현이 편합니다.
- 리스트의 중간에서 자료의 추가나 제거가 이루어질 때 현재 노드를 가리키는
cur와 이전 노드를 가리키는prev가 있으면 추가 및 삭제가 편합니다. - 삭제의 경우에 삭제하고자 하는 노드가 있으면
true를 반환하고 없다면false를 반환합니다. - 함수
ascending_order_add의 경우에는 오름차순으로 리스트를 생성하는 예제 함수입니다.
추가
- 아래처럼 추가하려는 노드의 위치를 찾은 후에 새 노드의 next를 다음 노드를 가리키고 이전 노드가 추가하려는 노드를 가리키게 합니다.
- 코드는 크게 3가지 방식이 있습니다.
add: 새로 추가하는 방법ascending_order_add: 중간에 추가하는 방법add_unique: 중복된 값 없이 추가하는 방법
// Add - one by one
void add(int key) {
Node * new_node = (Node*)malloc(sizeof(Node));
new_node->data = key;
new_node->next = NULL;
// Check first element
if (list == NULL) {
list = new_node;
}
else {
// Add new node to head
new_node->next = list;
list = new_node;
}
}
// Add - add ascending order
void ascending_order_add(int key) {
Node * new_node = (Node*)malloc(sizeof(Node));
new_node->data = key;
new_node->next = NULL;
if (list == NULL) {
list = new_node;
}
else {
Node * cur = list;
Node * prev = NULL;
// If first element is larger than key
if (cur->data > new_node->data) {
new_node->next = cur;
list = new_node;
}
// Other cases
else {
while (cur != NULL && cur->data < new_node->data) {
prev = cur;
cur = cur->next;
}
// Add in middle
if (cur != NULL) {
new_node->next = cur;
prev->next = new_node;
}
// Add to end
else {
prev->next = new_node;
}
}
}
}
// Add - add only unique value
void add_unique(int key) {
Node * new_node = (Node*)malloc(sizeof(Node));
new_node->data = key;
new_node->next = NULL;
if (list == NULL) {
list = new_node;
}
else {
Node * cur = list;
// Duplication check
while (cur != NULL) {
if (cur->data == key) {
return;
}
cur = cur->next;
}
new_node->next = list;
list = new_node;
}
}
삭제
- 아래처럼 삭제하려는 노드의 위치를 찾은 후에 이전노드가 삭제하려는 노드의 다음 노드를 가리키도록 하면 됩니다.
- 똑같이 처음을 주의해주고 쉽게 구현하기 위해
cur과prev을 이용합니다.
// Remove
bool remove(int key) {
if (list == NULL) {
return false;
}
if (list->data == key) {
Node * cur = list;
list = list->next;
free(cur);
return true;
}
else {
Node * cur = list->next;
Node * prev = list;
while (cur != NULL && cur->data != key) {
prev = cur;
cur = cur->next;
}
if (cur == NULL) return false;
prev->next = cur->next;
free(cur);
return true;
}
}
코드
#include <stdio.h>
#include <stdlib.h>
// Node
struct Node {
int data;
Node * next;
};
// Global list
Node * list;
// Init
void init() {
if (list == NULL) {
return;
}
else {
Node * cur;
cur = list;
while (cur != NULL) {
list = cur->next;
free(cur);
cur = list;
}
}
}
// Add - one by one
void add(int key) {
Node * new_node = (Node*)malloc(sizeof(Node));
new_node->data = key;
new_node->next = NULL;
// Check first element
if (list == NULL) {
list = new_node;
}
else {
// Add new node to head
new_node->next = list;
list = new_node;
}
}
// Add - add ascending order
void ascending_order_add(int key) {
Node * new_node = (Node*)malloc(sizeof(Node));
new_node->data = key;
new_node->next = NULL;
if (list == NULL) {
list = new_node;
}
else {
Node * cur = list;
Node * prev = NULL;
// If first element is larger than key
if (cur->data > new_node->data) {
new_node->next = cur;
list = new_node;
}
// Other cases
else {
while (cur != NULL && cur->data < new_node->data) {
prev = cur;
cur = cur->next;
}
// Add in middle
if (cur != NULL) {
new_node->next = cur;
prev->next = new_node;
}
// Add to end
else {
prev->next = new_node;
}
}
}
}
// Add - add only unique value
void add_unique(int key) {
Node * new_node = (Node*)malloc(sizeof(Node));
new_node->data = key;
new_node->next = NULL;
if (list == NULL) {
list = new_node;
}
else {
Node * cur = list;
// Duplication check
while (cur != NULL) {
if (cur->data == key) {
return;
}
cur = cur->next;
}
new_node->next = list;
list = new_node;
}
}
// Remove
bool remove(int key) {
if (list == NULL) {
return false;
}
if (list->data == key) {
Node * cur = list;
list = list->next;
free(cur);
return true;
}
else {
Node * cur = list->next;
Node * prev = list;
while (cur != NULL && cur->data != key) {
prev = cur;
cur = cur->next;
}
if (cur == NULL) return false;
prev->next = cur->next;
free(cur);
return true;
}
}
// Traverse
void traverse() {
Node * cur = list;
while (cur != NULL) {
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
int main() {
int arr[9] = { 2, 4, 6, 8, 1, 3, 5, 7, 9 };
int arr_duplicated[18] = { 8, 1, 3, 2, 4, 6, 8, 1, 3, 5, 7, 9, 2, 4, 6, 5, 7, 9 };
int arr_rmv[4] = { 2, 9, 8, 100 };
// Add to list 1
init();
for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); ++i) {
add(arr[i]);
}
printf("After add(normal): ");
traverse();
// Add to list 2
init();
for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); ++i) {
ascending_order_add(arr[i]);
}
printf("After add(ascending): ");
traverse();
// Add to list 3
init();
for (int i = 0; i < sizeof(arr_duplicated) / sizeof(arr_duplicated[0]); ++i) {
add_unique(arr_duplicated[i]);
}
printf("After add(unique): ");
traverse();
// Remove specific values in list
for (int i = 0; i < sizeof(arr_rmv) / sizeof(arr_rmv[0]); ++i) {
remove(arr_rmv[i]);
}
printf("After remove: ");
traverse();
return 0;
}
실행결과
After add(normal): 9 7 5 3 1 8 6 4 2
After add(ascending): 1 2 3 4 5 6 7 8 9
After add(unique): 9 7 5 6 4 2 3 1 8
After remove: 7 5 6 4 3 1