Data Structure/C
[C] 연결 리스트 (Linked List) 개념 및 구현
- -
개념
연결 리스트는 각 노드가 선형적으로 연결되어 있는 자료 구조이다.
특징
- 연결 리스트는 맨 처음 삽입한 노드의 주소를 가지고 있다.
- 각각의 노드는 데이터와 다음 노드의 주소를 가지고 있다.
- 데이터가 추가될 때마다 새로 노드를 할당하기 때문에 노드끼리의 메모리는 불연속적이다.
- 요소의 삽입와 삭제는 O(1) 이며, 특정 원소 접근은 O(n) 이다.
장점
1. 동적인 크기의 데이터를 다루기에 좋다. 데이터를 삽입할 때마다 메모리를 추가로 할당하기 때문이다.
- 일반 배열은 크기를 늘릴 수 없음
- 동적 배열(vector, ArrayList 등)은 크기가 늘어날 때 재할당과 복사로 오버헤드 발생 O(N)
2. 각 요소 사이에 데이터를 추가하더라도 O(1) 로 굉장히 빠르다.
- 일반 배열과 동적 배열은 해당 구역의 뒷부분을 한 칸씩 밀어서 공간을 만들어 내며 오버헤드 발생 O(N)
단점
1. 각 노드가 다음 노드의 주소도 가지고있기 때문에 메모리가 비교적 많이 필요하다.
2. 특정 데이터에 접근할 때, 배열처럼 index로 접근하지 못하기 때문에 순회를 해야한다. O(N)
배열과의 차이
첫 번째 행은 자신의 주소, 두 번째 행은 데이터다.
배열은 요청한 크기 만큼을 한 번에 메모리에 할당해주기 때문에 위와 같이 메모리가 연속적으로 이루어져있다.
하지만 연결리스트는 데이터를 삽입할 때마다 할당하기 때문에 메모리가 불연속적이다.
그럼에도 불구하고 노드(데이터)끼리 연결되어있는 이유는 각 노드는 다음 노드의 주소를 가지고있기 때문이다.
상세 설명
따라서 위의 간단하게 표현한 리스트는 아래와 같은 정보들을 더 가지고 있다.
다음 노드로 이동할 수 있도록 다음 노드의 주소를 가지고 있으며, 마지막 노드는 NULL pointer를 가지고 있어야 한다.
필요에 따라 이전 노드의 주소 또한 가지고 있을 수 있다. (사진의 파란색 글씨)
이렇게 각 노드가 이전 노드의 주소도 가지고 있는 경우, 이중 연결 리스트(Double Linked List)라고 하며,
다음 노드만 가지고 있는 경우는 단일 연결 리스트(Single Linked List)라고 한다.
이중 연결 리스트는 이전 노드의 주소까지 가지고 있으므로 각 노드마다 약 4~8 byte의 메모리를 더 사용하지만,
구현과 사용에 굉장이 용이하다는 장점이 있다.
앞서 설명했던 것들은 모두 데이터를 담고 있는 각각의 "노드(Node)" 였지만 노드 자체를 리스트로 사용할 수도 있다.
어찌 됐건 맨 첫 노드만 기억하고 있다면, 각 노드는 연결되어있기 때문에 언제든지 접근할 수 있다.
하지만 이보다는 더욱 편리하게 사용해보자.
맨 처음 노드인 Head Node, 맨 마지막 노드인 Tail Node, 노드의 개수를 기억하는 Size를 담고있는 녀석이다.
연결 리스트의 특성상 맨 마지막에 데이터를 추가하려면 Head Node부터 끝까지 순회해야 하는데,
Tail Node를 기억하고 있다면, Tail의 다음 노드에 바로 추가하면 되기 때문에 굉장히 속도가 빠르다.
노드 마다 메모리를 추가로 필요로 하는 것도 아니기 때문에 부담도 훨씬 적다.
연결 리스트에 데이터를 삽입, 삭제할 때 어떻게 동작하는 지는 구현 파트에서 설명하도록 하겠다.
구현
필자는 이중 연결 리스트를 선호하기 때문에 이를 기준으로 구현했다.
설명에 앞서 참고해야할 사항 몇 가지
우선 연결 리스트(이하 리스트)의 할당과 해제는 프로그래머에게 맡긴다.
따라서 리스트는 이미 할당되어 있다는 가정을 한다.
또한 다음과 같은 사항은 코드의 가독성 문제 등으로 염려에 두지 않았다.
1. 함수의 리스트(list) 매개변수가 NULL pointer일 경우
2. malloc() 이 실패한 경우
3. free() 후 댕글링 포인터
4. size의 overflow
구조체
typedef struct node
{
struct node* prev;
struct node* next;
int data;
} node;
typedef struct list
{
node* head;
node* tail;
int size;
} list;앞서 말했다시피, 각 노드(node)는 이전 노드(prev)와 다음 노드(next)의 주소를 가지고 있으며,
당연히 데이터(data)도 가지고 있다.
초기화
void initialize(list* list)
{
list->head = NULL;
list->tail = NULL;
list->size = 0;
}이미 할당이 되어있다는 가정이기 때문에 list의 주소를 받아 NULL 또는 0으로 초기화만 해준다.
참고로 NULL은 <stdlib.h>에 define 되어있는 (void *)0 이다.
맨 뒤에 데이터 삽입
void push_back(list* list, int data)
{
node* new_node = (node*)malloc(sizeof(node));
new_node->data = data;
new_node->next = NULL;
if (list->size == 0)
{
list->head = new_node;
new_node->prev = NULL;
}
else
{
list->tail->next = new_node;
new_node->prev = list->tail;
}
list->tail = new_node;
++list->size;
}연결 리스트에서 삽입의 핵심은 각 노드가 가지고 있는 다음 노드(또는 이전 노드)의 주소 변경이다.
맨 마지막에 데이터를 삽입했기 때문에,
기존에 있던 tail의 next에 새 노드의 주소를 복사하고, 새 노드의 prev에 tail의 주소를 복사하는 것이다.
이후, list의 tail를 새 노드로 복사하면 끝이다.
만약 비어있는 list에 삽입하는 경우, list의 head와 tatil에 모두 새 노드의 주소를 복사한다.
list의 size를 하나 증가시켜준다.
맨 앞에 데이터 삽입
void push_front(list* list, int data)
{
node* new_node = (node*)malloc(sizeof(node));
new_node->data = data;
new_node->next = NULL;
if (list->size == 0)
{
list->tail = new_node;
new_node->prev = NULL;
}
else
{
list->head->prev = new_node;
new_node->next = list->head;
}
list->head = new_node;
++list->size;
}맨 뒤에 삽입하는 것과 똑같다.
기존 head의 prev에 새 노드의 주소를 복사하고, 새 노드의 next에 기존 head 주소를 복사한다.
이후, list의 head를 새 노드로 바꿔준다.
맨 뒤 데이터 삭제
void pop_back(list* list)
{
if (list->size == 0)
return;
node* temp = list->tail;
if (list->size == 1)
{
list->head = NULL;
list->tail = NULL;
}
else
{
list->tail->prev->next = NULL;
list->tail = list->tail->prev;
}
free(temp);
--list->size;
}list의 원소가 한 개였다면, head와 tail을 모두 NULL로 바꿔주고
아니라면, tail을 삭제하는 것이기 때문에 tail의 prev를 tail로 바꿔주는 작업을 한다.
이후 list의 size를 하나 감소시켜준다.
여기서 핵심은 미리 주소를 다 바꿔준 이후 tail을 해제하는 것이다.
해제부터 한다면 데이터를 모두 잃어버려서 노드를 이어주는 작업을 해줄 수 없다.
여기서 또 문제는 미리 바꿔줄 것 다 바꿔준다면, tail의 주소를 잃어버린다는 것이다.
따라서 미리 tail의 주소를 기억해두자.
맨 앞의 데이터 삭제
void pop_front(list* list)
{
if (list->size == 0)
return;
node* temp = list->head;
if (list->size == 1)
{
list->head = NULL;
list->tail = NULL;
}
else
{
list->head->next->prev = NULL;
list->head = list->head->next;
}
free(temp);
--list->size;
}맨 뒤의 데이터 삭제와 똑같으나, 이번엔 head의 next가 head가 되는 작업들을 해줘야 한다.
이하 생략
원소 찾기
node* find(list* list, node* target)
{
node* cur = list->head;
while (cur != NULL)
{
if (cur == target)
return cur;
cur = cur->next;
}
return NULL;
}이 뒤에 나올 함수들에 사용하려고 node의 주소를 매개변수로 주었지만,
필요에 따라서는 데이터 자체를 받아서 이를 찾는 함수로 변형시켜도 된다.
node의 주소로 찾는다면 메모리가 고유하기 때문에 중복에 염려가 없고,
데이터로 찾는다면 중복된 데이터가 있을 경우, 원하는 동작이 나오지 않을 수도 있다.
찾았다면, 찾은 node의 주소를 반환해주고
못 찾았다면, NULL을 반환해준다.
중간에 데이터 삽입
void insert(list* list, node* target, int data)
{
if (list->size == 0 || !find(list, target))
return;
node* new_node = (node*)malloc(sizeof(node));
new_node->data = data;
new_node->next = target;
new_node->prev = target->prev;
if (target->prev != NULL)
target->prev->next = new_node;
target->prev = new_node;
if (target == list->head)
list->head = new_node;
++list->size;
return;
}여기서부터 구현은 더욱 가지각색이겠지만, 필자는 C++ STL의 list의 구조를 참고하여 구현하였다.
먼저, 인자로 받은 target node가 인자로 받은 list에 존재하는 node인지 확인하는 과정을 거쳤다.
target의 이전에 인자로 받은 data를 가진 새 노드를 할당하여 삽입하는 과정이다.
백문이 불여일견.
이런 상태의 연결 리스트를
이런 상태로 만드는 것이다.
만약 target이 head였다면, head를 새 노드로 바꿔준다.
반면 target이 tail이었다고 해도, target의 이전에 추가하기 때문에 현재 로직에서는 tail을 바꿔줄 일은 없다.
역시 list의 size를 증가시켜준다.
중간 요소 삭제
node* erase(list* list, node* target)
{
if (list->size == 0 || !find(list, target))
return NULL;
node* next = target->next;
if (list->size == 1 || target == list->head)
pop_front(list);
else if (target == list->tail)
pop_back(list);
else
{
target->prev->next = target->next;
target->next->prev = target->prev;
free(target);
--list->size;
}
return next;
}이 역시 인자로 받은 target node가 인자로 받은 list에 존재하는 node인지 확인하는 과정을 거쳤다.
list의 요소 한 개이거나, target이 head라면, 미리 구현해두었던 pop_front() 함수를 호출한다.
target이 tail이라면 pop_back() 함수를 호출한다.
모두 아니라면 target이 정말 중간 요소인 경우인데, target의 양 옆 노드를 서로 이어주는 과정을 거친다.
이런 상태의 연결 리스트를
이런 상태로 바꾸는 것이다.
이후 list의 size를 감소시킨다.
모든 요소 삭제
void clear(list* list)
{
node* cur = list->head;
node* next;
while (cur != NULL)
{
next = cur->next;
free(cur);
cur = next;
}
initialize(list);
}모든 요소 삭제 함수는 재귀로 구현하면 쉽게 구현할 수 있지만,
재귀 함수는 메모리 사용 측면에서 좋지 않으므로 반복문으로 구현하는 것을 추천한다.
cur을 free하면 다음 노드로 갈 수 없기 때문에, 미리 next에 담아둔 뒤에 free를 진행해준다.
모든 node를 해제했다면, 구현했던 initialize()를 통해 list를 재사용 가능하게 한다.
참고용 재귀 함수 버전 (호출할 때 head node를 주면 된다.)
void clear(list* list, node* cur)
{
if (cur == NULL)
{
initialize(list);
return;
}
clear(list, cur->next);
free(cur);
}* list의 원소가 많을 수록 재귀의 호출 스택은 많아지기 때문에 매개변수 크기 만큼의 메모리 사용이 계속 누적된다.
최악의 경우 Stack overflow가 발생
테스트
리눅스 환경에서 여러 컴파일 옵션을 줘서 테스트했고
메모리 누수 포함 에러가 (아직은) 없는 것을 확인했다.
↓ 테스트 코드 확인하기
더보기
#include <stdio.h>
#include "LinkedList.h"
// Test for Linkedmy_list.c
void print_list(list* my_list)
{
node* cur = my_list->head;
printf("[size:%d] ", my_list->size);
while (cur != NULL)
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
int main()
{
list my_list;
printf("----- initialize -----\n");
initialize(&my_list);
print_list(&my_list);
printf("\n----- push_back -----\n");
push_back(&my_list, 1);
print_list(&my_list);
push_back(&my_list, 2);
print_list(&my_list);
push_back(&my_list, 3);
print_list(&my_list);
push_back(&my_list, 4);
print_list(&my_list);
printf("\n----- insert -----\n");
for (node* i = my_list.head; i != NULL; i = i->next)
{
if (i == my_list.head)
insert(&my_list, my_list.head, 10);
if (i->data == 3)
insert(&my_list, i, 20);
else
continue;
print_list(&my_list);
}
print_list(&my_list);
printf("\n----- pop_back -----\n");
pop_back(&my_list);
print_list(&my_list);
pop_back(&my_list);
print_list(&my_list);
printf("\n----- push_front -----\n");
push_front(&my_list, 5);
print_list(&my_list);
push_front(&my_list, 6);
print_list(&my_list);
push_front(&my_list, 7);
print_list(&my_list);
push_front(&my_list, 8);
print_list(&my_list);
printf("\n----- find -----\n");
node* find1 = my_list.head->next->next;
printf("%p\n", find(&my_list, find1));
node* find2 = (node*)malloc(sizeof(node));
printf("%p\n", find(&my_list, find2));
free(find2);
list test_list;
initialize(&test_list);
push_back(&test_list, 3);
node* find3 = test_list.head;
printf("%p\n", find(&my_list, find3));
pop_back(&test_list);
printf("\n----- pop_front -----\n");
pop_front(&my_list);
print_list(&my_list);
pop_front(&my_list);
print_list(&my_list);
printf("\n----- erase -----\n");
for (node* i = my_list.head; i != NULL; )
{
if (i->data == 10 || i->data == 20)
{
i = erase(&my_list, i);
print_list(&my_list);
}
else
i = i->next;
}
erase(&my_list, my_list.head);
print_list(&my_list);
erase(&my_list, my_list.tail);
print_list(&my_list);
printf("\n----- clear -----\n");
clear(&my_list);
print_list(&my_list);
printf("\n----- edge cases -----\n");
clear(&my_list); // double clear
pop_back(&my_list); // pop_back at empty list
pop_front(&my_list); // pop_front at empty list
insert(&my_list, NULL, 3); // insert 3 before "NULL" node
erase(&my_list, NULL); // erase "NULL" node at list
find(&my_list, NULL); // find "NULL" node at list
push_back(&my_list, 1); // use list after clear
print_list(&my_list);
pop_back(&my_list); // just pop
print_list(&my_list);
}
마무리
이로써 연결 리스트의 개념과 구현을 모두 마쳤다.
자료구조로서의 개념과 구현에 중점을 두었기에 C로 구현했는데,
C는 union을 사용하지 않으면 필요한 데이터의 자료형에 맞춰 계속해서 구현을 해야한다.
이 때, 함수 오버로딩도 안 되기 때문에 이름 충돌도 일어나서 불편함을 겪는다.
따라서 다음엔 C++ STL을 비슷하게 구현해보며
Generic Programming과 더불어 객체지향의 특징에 중점을 두어 포스팅 해볼 예정이다.
마지막으로 전체 코드 링크
https://github.com/SikPang/DataStructures/tree/main/C_LinkedList
개인 공부용 포스팅인 점을 참고하시고, 잘못된 부분이 있다면 댓글로 남겨주시면 감사드리겠습니다.
'Data Structure > C' 카테고리의 다른 글
| [C] 해시 테이블 (Hash Table) 개념 및 구현 (0) | 2023.03.30 |
|---|---|
| [C] 이진 탐색 트리 (Binary Search Tree) 개념 및 구현 (0) | 2023.03.27 |
| [C] 덱 (Deque) 개념 및 원형 덱 구현 (2) | 2023.03.23 |
| [C] 동적 배열 (Dynamic Array) 개념 및 구현 (0) | 2023.03.22 |
Contents
소중한 공감 감사합니다