연결리스트 소개
연결리스트란?
- 연결리스트란 노드가 연쇄적으로 연결되어 있는 구조로 각 노드는 데이터(data)와 다음 링크(next, 다음 노드의 주소)라는 두개의 필드를 가진다.
- data 필드는 리스트의 실제 요소를 가지고 next는 리스트의 다음 노드를 가리키는 주소를 가집니다. 그러므로 next 필드는 다음 노드에 대한 포인터가 된다.
- 전체 연결리스트는 제일 앞의 노드에 대한 포인터로 나타낼 수 있다. 즉 첫 번째 노드를 가리키는 변수 하나만 있으면 리스트 전체를 접근할 수 있다. 여기서는 그것을 head라고 부른다.
- 마지막 노드의 next는 NULL이라고 알려진 특수한 값을 가진다. 이것은 더이상 다음 노드가 없음을 나타내는 역할을 한다.
- 노드가 없는 리스트를 널 리스트라고 한다. 그 경우 head=NULL이 된다. 연결리스트는 처음에는 head=NULL로 초기화된다.
- 연결리스트는 동적인 자료구조다. 리스트의 노드가 수시로 추가 또는 삭제될 수 있고 전체 노드 개수는 계속 변화한다.
- 스택이나 큐처럼 연결리스트도 자료구조다. 각 노드의 data 필드가 리스트가 가져야 할 실제 데이터 값들을 가지고 있다. 대표적인 연산은 추가, 삭제와 리스트 전체 방문(traverse) 등이다.
연결리스트의 장점
- 동적인 자료구: 연결리스트는 동적인 자료구조여서 실행 중에 동적으로 메모리를 할당하여 얼마든지 길어지거나 줄어들 수 있다. 그러므로 초기에 크기를 정하고 메모리를 할당할 필요가 없다.
- 추가와 삭제: 노드의 추가와 삭제는 쉽고 빠르다. 배열에서는 요소를 추가나 삭제할 때 다른 요소들을 한칸씩 밀거나 당겨야 한다. 연결 리스트에서는 노드의 next 주소만 바꿈으로써 간단하게 추가 삭제를 처리할 수 있다.
- 메모리 낭비가 없다: 연결리스트의 크기는 실행 중에 얼마든지 늘어나거나 줄어들 수 있다. 그러므로 메모리의 낭비가 없다. 배열은 반면에 메모리 낭비가 많은데, 배열을 사이즈 10으로 선언하고 6개만 저장한다면 4칸의 메모리는 낭비된다. (이것을 10만과 6만으로 생각하면 좀더 이해가 잘 될 것이다.) 연결리스트에서는 언제든 필요할 때 메모리를 할당하므로 이런 문제가 없다.
- 구현의 편리성: 스택이나 큐 같은 자료구조도 연결리스트로 쉽게 구현할 수 있다. 예를 들어 연결리스트로 스택을 구현한다면 ERROR_STACK_FULL 은 절대 발생하지 않고 메모리도 낭비하지 않을 수 있다.
next를 노드마다 가지면 메모리가 더 많이 필요하지 않는가 라는 생각을 하게 되는데, 사실 data 필드가 단순 타입의 값 하나만 달랑 가진다면 굳이 고생해서 연결리스트를 만들 필요는 없다. 그러나 data는 보통은 큰 덩어리의 구조체나 배열 등을 가지고 있는 경우가 많고 그러한 데이터가 얼마든지 많아질 수 있는 가능성을 가지는 경우는 연결리스트를 사용하는 것이 매우 중요하다.
연결리스트는 다음과 같이 그림으로 나타내 볼 수 있다. 제일 앞의 노드가 head가 된다.
------------------------------ ------------------------------
| | | \ | | |
| DATA | NEXT |--------------| DATA | NEXT |
| | | / | | |
------------------------------ ------------------------------이제 연결리스트의 노드 구조체를 정의해 보자. 이 코드는 https://www.learn-c.org/en/Linked_lists에서 참고하였다.
typedef int elem_t;
typedef struct node {
elem_t data;
struct node* next;
} node_t;여기서 구조체가 재귀적으로 정의된 것을 잘 보아두어야 한다. C에서는 구조체가 자기 자신을 필드로 가지는 것을 허용한다. 그리고 그 구조체 타입의 이름은 node_t라고 붙였다. (사실 C는 이름에 관해서 snake style을 권장한다. 대문자를 쓰는 CamelStyle은 자바의 방식이고 C 언어는 필요하다면 밑줄로 연결한 이름을 사용하는 것이 더 C 스타일에 맞다고 할 수 있다. 일부 교재는 NodeType 이런 식의 이름을 쓰고 있는데, 이 사이트의 코딩스타일이 정석이다. 포인터 선언에서 * 앞뒤로 빈칸을 둔 것도 바람직한 스타일이므로 눈여겨 봐둘만 하다.)
(1) 연결리스트 생성
node_t * head = NULL;
head = (node_t *) malloc(sizeof(node_t));
if (head == NULL) {
return 1;
}
head->data = 1;
head->next = NULL;이제 리스트 하나를 만들었다. 1이라는 요소 하나를 가진 리스트이고 next 필드는 NULL을 가지고 있어 더 이상의 노드가 없음을 나타낸다. malloc 후에는 반드시 리턴값이 NULL인지를 확인해 주는 것이 필요하다. (이하에서는 지면상 생략함)
(2) 두번째 요소를 추가하기
node_t * head = NULL;
head = (node_t *) malloc(sizeof(node_t));
head->data = 1;
head->next = (node_t *) malloc(sizeof(node_t));
head->next->data = 2;
head->next->next = NULL;(3) 마지막에 요소를 추가하기
이런 방식으로 계속하게 되는데 여기서 중요한 것은 새로운 요소를 추가할 때 head에서 시작해서 마지막 요소를 만날 때까지 가야 한다는 점이다. next가 NULL이면 마지막 요소임을 알게 된다. 다음은 마지막 요소를 찾아가는 함수다.
참고로 리스트에서는 head, tail 이라는 용어를 쓰고 큐에서는 front, rear라고 하고 스택은 top을 가진다.
마지막 요소를 찾아가는 방법은 next가 NULL인 노드가 나올 때까지 다음 노드로 차례로 이동한다.
node_t* get_tail(node_t* head)
{
node_t* tail = head;
while (tail->next != NULL) {
tail = tail->next;
}
return tail;
}마지막 요소를 찾으면 끝에 노드를 새로 추가할 수 있다.
head가 바뀔 수 있으므로 node_t ** 타입임을 주의하라. (매개변수로 포인터 head를 변경하기 위한 방법이다. 호출부에서는 insert_tail(&head, n);이렇게 호출할 것이다.)
void insert_tail(node_t** head, elem_t n)
{
node_t* tail = get_tail(*head);
node_t* new_node = (node_t *)malloc(sizeof(node_t));
new_node->data = n;
new_node->next = NULL;
if (*head == NULL)
*head = new_node;
else
tail->next = new_node;
}(4) 제일 앞에 새로운 요소 추가하기
제일 앞에 새로운 요소를 추가하는 것은 push라고 볼 수 있다. 그러기 위해서는 다음과 같은 과정이 필요하다. 또한 head가 바뀌어야 하므로 head의 주소를 가지는 포인터를 받아서 변경시킨다.
- 새로운 노드를 생성하고 값을 설정한다.
- 새로운 노드의 next를 head로 설정한다.
- 새로운 노드가 head가 된다.
void push(node_t** head, elem_t n)
{
node_t* new_node = (node_t *) malloc(sizeof(node_t));
new_node->data = n;
new_node->next = *head;
*head = new_node;
}(5) 제일 앞에 있는 것을 삭제하기
제일 앞의 요소를 삭제하기 위해서는 head가 바뀌어야 하므로 역시 node_t ** 타입의 head를 받아야 한다.
- head의 next를 저장해 둔다.
- head를 free하고 그 값을 반환값으로 저장한다.
- head를 1에서 저장해 둔 노드로 바꾼다.
여기서 head가 NULL인 경우, 리스트에 노드가 head 한 개 밖에 없는 경우 등을 고려해야 한다.
elem_t pop(node_t ** head) {
elem_t retval = -1;
node_t * next_node = NULL;
if (*head == NULL)
return -1;
next_node = (*head)->next;
retval = (*head)->data;
free(*head);
*head = next_node;
return retval;
}(6) 마지막에 있는 것을 삭제하기
연결리스트의 마지막 요소를 삭제하는 것을 생각해 보자. 마지막 요소를 삭제하기 위해서는 마지막 직전 요소까지 이동해야 한다. 만약 연결리스트의 요소가 하나밖에 없다면 head 요소를 삭제하면 된다. 노드의 삭제는 해당 노드를 free하고 값을 반환한다. 또한 요소가 하나뿐인 리스트였다면 리스트가 비었으므로 head는 NULL이 되어야 한다.
- head가 마지막이면 head를 삭제하고 head를 NULL로 바꾸어야 한다.
- 아니면 마지막 직전 요소로 이동해서
- 마지막 요소를 free 하고 그 값을 리턴한다
- 마지막 직전 요소의 next를 NULL로 바꾼다.
elem_t remove_tail(node_t** head) {
elem_t retval = 0;
/* 연결리스트의 요소가 한 개인 경우 */
if ((*head)->next == NULL) {
retval = (*head)->data;
free(*head);
*head = NULL;
return retval;
}
/* 마지막 직전 노드까지 이동한다. */
node_t* current = *head;
while (current->next->next != NULL) {
current = current->next;
}
/* 이제 current가 마지막 직전 노드이므로 current->next를 삭제하면 된다. */
retval = current->next->data;
free(current->next);
current->next = NULL;
return retval;
}(7) n번째에 요소를 추가하기
n은 인덱스와 같아서 0부터 시작하는 번호다. n > 0인 경우는 n-1번째 노드에 찾아가서 그 다음에 새로운 노드를 추가해야 한다.
- n이 0이면 push로 추가한다.
- 새로운 노드를 만들고 요소를 val로 설정한다.
- n-1번째 노드로 이동한다.
- 새로운 노드의 next를 다음 노드로 지정한다.
- n-1번째 노드의 next를 새로운 노드로 지정한다.
n이 리스트의 요소 개수보다 크거나 같은 경우는 끝에 추가하는데, 이것은 위의 알고리듬에서 해결될 수 있다.
(8) n번째 요소를 삭제하기
n번째 요소를 삭제하기 위해서도 위와 비슷한 과정을 거치게 된다. 알고리듬은 다음과 같다.
- 우리가 삭제하고자 하는 노드의 이전 노드로 간다.
- 삭제할 노드를 다른 변수에 저장한다.
- 이전 노드의 next를 삭제할 노드의 next로 바꾼다.
- 삭제할 노드를 free하고 값은 반환한다.
여기서는 삭제할 노드가 제일 앞에 있는 것일 경우 pop으로 처리하면 된다. 그러므로 head가 바뀌는 것은 여기서는 신경쓰지 않아도 되지만 pop에서 head를 변경할 수 있으므로 역시 node_t ** head를 받아야 한다.
elem_t remove_by_index(node_t** head, int index) {
int i = 0;
element retval = -1;
node_t* current = *head;
node_t* temp_node = NULL;
if (index == 0) {
return pop(head);
}
for (i = 0; i < index - 1; i++) {
if (current->next == NULL) {
return -1;
}
current = current->next;
}
temp_node = current->next;
retval = temp_node->data;
current->next = temp_node->next;
free(temp_node);
return retval;
}(9) 값이 val인 첫번째 노드를 삭제하기
먼저 값이 val인 노드를 찾아가야 되는데, 이때도 삭제할 이전 노드까지 이동해야 한다. 또한 삭제할 노드가 첫번째인 경우도 고려해야 한다. 알고리듬은 다음과 같다.
- head의 값이 val과 같으면 pop을 이용해 삭제하고 그 반환값을 리턴한다.
- 값이 val인 노드의 직전 노드까지 이동한다. (다음 노드의 값이 val일 때까지)
- 삭제할 노드를 변수에 저장한다.
- 직전 노드의 next를 삭제할 노드의 다음 노드로 바꾼다.
- 삭제할 노드를 free하고 값은 반환한다.
- 값이 val인 노드가 없으면 -1을 반환한다.
elem_t remove_by_value(node_t ** head, elem_t val) {
elem_t retval = -1;
node_t * current = *head;
node_t * temp_node = NULL;
if ((*head)->data == val)
return pop(head);
while (current->next != NULL && current->next->data != val) {
current = current->next;
}
if (current->next == NULL)
return -1;
temp_node = current->next;
retval = temp_node->data;
current->next = temp_node->next;
free(temp_node);
return retval;
}