C로 Linked List 구현하기

C로 Linked List 구현하기

정글 참여한지 5주차에 접어들었습니다. 지금까지는 파이썬으로 백준 문제들을 풀면서 주요 자료구조와 알고리즘에 대한 개념을 익히는 시간이었습니다. 6주차에서 8주차까지는 C언어와 친해지면서 크게 3가지 프로젝트를 진행하게 됩니다.

6주차에서는 RB-Tree 자료구조를 직접 만드는 프로젝트를 진행합니다.(그게 먼데.....) RB-Tree 개념이 안그래도 어려운데 할줄도 모르는 C언어로 짜라고 하니 도저히 엄두가 나지 않았습니다. 어떻게 할지 몰라 갈팡질팡하다 팀원 제안으로 상대적으로 간단한 자료구조인 Linked List와 RB-Tree의 상위 개념인 Binary Search Tree를 C로 구현해 보고 RB-Tree 구현에 들어가기로 했습니다. 이 글에서는 그 중 Linked List를 소개하려고 합니다.

Linked List

링크드리스트는 일반적인 배열과 다른 자료구조입니다. 배열의 경우 한번 크기가 정해지면 크기를 변경할 수 없는데 반해, 링크드리스트는 삭제와 삽입이 다소 자유롭습니다. 다만, 배열은 인덱스를 통해 바로 데이터에 접근할 수 있지만, 링크드리스트는 처음부터 하나씩 올라가면서 접근해야 하므로 특정 데이터를 찾는데 있어서는 배열 의성능이 훨씬 좋다고 할 수 있습니다.

구현하고자 하는 함수는 총 7가지입니다. 혹시 링크드리스트로 또 구현할만한 함수가 있으면 댓글 남겨주시면 감사하겠습니다.

• delete_list: 이 함수는 해당 리스트를 삭제하는 함수입니다. malloc 함수를 사용하여 필요한 메모리를 할당받는 방식으로 구현하기 때문에, 프로그램 종료전에 할당받은 메모리를 돌려주어야 합니다. 리스트에 할당된 메모리를 전부 돌려주는 역할을 하는 함수입니다.
• print_list: 리스트의 모든 값들을 출력하는 함수입니다. 처음 head부터 시작해 NULL이 나올때까지 노드들에 저장된 값을 출력해줍니다.
• append: 리스트의 끝에 노드를 붙여주는 함수입니다.
• unshift: 리스트 앞에 노드를 붙여주는 함수입니다.
• shift: 맨 앞에 있는 노드를 빼서 반환해주는 함수입니다.
• pop: 맨 뒤에 있는 노드를 빼서 반환해줍니다.
• remove_by_index: 특정 index에 있는 노드를 빼서 반환해줍니다.

우선 node의 기본적인 구성요소는 이렇게 되어 있습니다.

typedef struct node {
	int val;
	struct node *next;
} node_t;

typedef를 활용하여 새로운 타입인 node_t를 만들었습니다. 기본적으로 구조체이며 값을 받기 위한 val 변수와 다음 노드를 가리키기 위한 next 포인터 변수를 담았습니다.

main

int main() {
    node_t *head = NULL;

    append(&head, 1);
    append(&head, 2);
    append(&head, 3);
    unshift(&head, 4);
    unshift(&head, 5);

    printf("나온 숫자: %d\n", shift(&head));
    printf("나온 숫자: %d\n", remove_by_index(&head, 0));
    printf("나온 숫자: %d\n", remove_by_index(&head, 1));
    print_list(head);
    printf("나온 숫자: %d\n", pop(&head));
    
    print_list(head);

    delete_list(&head);
}

main함수 구성입니다. 우선 첫 head는 NULL로 설정했습니다. 다른 예시를 보면, head에 노드를 연결하고 시작하는 코드도 있는데 이 경우 함수의 일관성이 깨지는 것 같아 처음에는 NULL로 설정하고 함수에서 head가 NULL인 경우를 포함해 코드를 짰습니다. 이제 본격적으로 함수를 하나 하나 확인해 보겠습니다.

delete_list

void delete_list(node_t **ptr_head) {
    node_t *current = *ptr_head;
    *ptr_head = NULL;

    while (current != NULL) {
        free(current);
        current = current->next;
    }
}

delete_list 함수 코드입니다. 여기서 ptr_head라는 변수를 주목해주시기 바랍니다. ptr_head 변수의 타입을 node_t **로 설정했습니다. 이는 node_t *를 가리키는 포인터, 즉 node_t 변수를 가리키는 포인터를 가리키는 포인터라는 의미입니다. 이중 포인터죠. 여기서 의문이 드실 수 있습니다. "아니, 포인터 변수를 넘겨서 처리하면 되는거 아닌가? 왜 헷갈리게 이중 포인터를 넘기는 거지?"

만약 delete_list 코드가 아래와 같다고 해보죠.

void delete_list(node_t *ptr_head) {
    node_t *current = ptr_head;
     ptr_head = NULL;

    while (current != NULL) {
        free(current);
        current = current->next;
    }
}

얼핏 보면 문제가 없는 코드입니다. ptr_head 포인터를 가리키는 곳을 current 포인터가 바라보고 NULL이 될때까지 계속 업데이트 해주면서 해당 포인터가 가리키는 메모리를 계속 돌려주는 문제 없는 코드로 보입니다.

처음 delete_list 함수가 실행되는 순간, 이 함수 스택에서 ptr_head 변수가 생성됩니다. 단순히 주소를 넘겼을 경우 그 주소값을 가지는 또 다른 변수가 생성되는 거죠.

위와 같은 그림이 됩니다. 따라서 실제 head 포인터의 값은 그대로 유지됩니다. 이렇게 인자로 받은 값을 복사해서 처리하는 것을 Call by value(값에 의한 호출), 인자로 받은 값의 주소를 참조하여 값에 영향을 미치는 것을 Call by reference(참조에 의한 호출) 라합니다. 이렇게 call by value를 하면, head 포인터에 있는 주소 값을 복사해 새로운 ptr_head 포인터에 그 값을 넣습니다.

head 포인터의 값을 NULL로 바꾸어 주어야 하기에 아래와 같이 call by reference를 합니다.

void delete_list(node_t **ptr_head) {
    node_t *current = *ptr_head;
    *ptr_head = NULL;

    while (current != NULL) {
        free(current);
        current = current->next;
    }
}

근데 사실 이 코드는 call by value 하든 call by reference 하든 사실 크게 문제가 되지 않습니다. 결국 메모리를 free하기에 최종적인 문제가 head 포인터가 free된 메모리 위치를 가리키고 있다는 건데, delete_list 함수를 호출한 후 head포인터를 참조하지 않으면 됩니다. main 함수 콜 스택이 종료되면 head 포인터도 결국 사라지기 되죠.

print_list

void print_list(node_t *head) {
    node_t *current = head;

    while (current != NULL) {
        printf("{%d} -> ", current->val);
        current = current->next;
    }
    printf("NULL");
    printf("\n");
}

print_list 함수에서는 이중포인터가 아닌 head 포인터가 가리키는 주소를 넘겼습니다. print_list는 이중포인터를 사용하지 않아도 됩니다. 왜냐하면 head 포인터를 업데이트하지 않아도 되기 때문입니다. 역으로 head 포인터를 업데이트해서는 안됩니다. 따라서 call by value로 head가 담고 있는 주소를 넘겨줍니다. 그 뒤에 current라는 포인터 변수를 만들어 head에 담겨 있는 주소를 넣고 current 변수가 NULL이 될 때까지 current 포인터를 업데이트 해가며 요소를 출력합니다.

append

void append(node_t **ptr_head, int val) {
    if (*ptr_head == NULL){
        *ptr_head = (node_t *)malloc(sizeof(node_t));
        (*ptr_head)->val = val;
        (*ptr_head)->next = NULL;
        return;
    }

    node_t *current = *ptr_head;
    while (current->next != NULL)
        current = current->next;

    current->next = (node_t *)malloc(sizeof(node_t));
    current->next->val = val;
    current->next->next = NULL;
}

append 함수는 보다시피 이중포인터를 가지고 있습니다. 많은 분들이 "어? append는 리스트 끝에다 노드를 넣어주는 함수인데 그럼 head를 업데이트할 필요가 없으니 이중포인터가 필요 없지않나?" 의문을 가질 수 있습니다.

한가지 간과하고 있는 것은 head가 NULL값을 가지고 있는 경우입니다. 리스트에 아무런 노드가 없는 경우죠. 이 경우에는 head 포인터를 들어온 요소에 맞게 업데이트해야 합니다. 따라서 call by reference로 이중포인터를 받았습니다.

unshift

void unshift(node_t **ptr_head, int val){
    node_t *new_node;
    new_node = (node_t *)malloc(sizeof(node_t));

    new_node->val = val;
    new_node->next = *ptr_head;
    *ptr_head = new_node;
}

unshift함수는 이중포인터를 받습니다. 왜냐하면 맨 앞에 노드를 넣기 에 어떤 상황이든 head가 업데이트되기 때문입니다. 이제 좀 명확해졌나요? 노드를 맨 앞에 넣고 head값을 해당 노드로 업데이트 하면 됩니다.

shift

int shift(node_t **ptr_head) {
    node_t *current = *ptr_head;
    if (current == NULL)
        return -1;
    *ptr_head = current->next;
    int retval = current->val;
    free(current);
    return retval;
}

shift 함수도 unshift 함수와 같은 이유로 이중포인터를 사용합니다. 맨 앞에 있는 노드를 삭제하므로 head를 다음 노드로 업데이트해야 되고 따라서 call by reference를 활용합니다. 다만 리스트에 어떤 노드도 없는 경우에는 뺄 것이 없으므로 그냥 -1을 반환합니다.

pop

int pop(node_t **ptr_head) {
    if (*ptr_head == NULL)
        return -1;
    node_t *current = *ptr_head;
    if (current->next == NULL) {
        *ptr_head = NULL;
        int retval = current->val;
        free(current);
        return retval;
    }
    node_t *before = *ptr_head;
    current = current->next;
    while (current->next != NULL){
        before = before->next;
        current = current->next;
    }
    before->next = NULL;
    int retval = current->val;
    free(current);
    return retval;
}

pop 함수는 다른 함수들보다 생각할 것들이 많습니다. 그 이유는 링크드리스트 특성에 기인합니다. 링크드리스트는 마지막이 어디인지 알 수 없습니다. 그냥 head에서 출발해 node->next가 NULL이 될때까지 움직일 뿐입니다.

위 그림처럼 마지막 요소를 제거하면 제거한 요소 전에 있던 요소가 제거한 요소가 가리키고 있던 다음 요소를 가리키게끔 해야합니다. 하지만 아무런 정보없이 그저 앞으로만 가는 링크드리스트 특성상 전 노드가 어떤 것인지 따로 저장하고 있어야 합니다. 따라서 before 포인터를 만들어 바로 전 노드를 계속 저장하고 있습니다. 또한, head를 변경하는 경우가 있습니다. 노드가 하나만 있는 경우 head를 NULL로 업데이트하므로 이중포인터를 넘겨줍니다.

remove_by_index

int remove_by_index(node_t **ptr_head, int index) {
    if (*ptr_head == NULL)
        return -1;

    if (index == 0)
        return shift(ptr_head);
    
    node_t *current = *ptr_head;
    node_t *before = *ptr_head;

    current = current->next;

    if (current == NULL)
        return -1;

    for (int i = 1; i < index; i++){
        current = current->next;
        before = before->next;
        if (current == NULL)
            return -1;
    }
    before->next = current->next;
    int retval = current->val;
    free(current);
    return retval;
}

remove_by_index도 다소 복잡합니다. 우선 0번째 노드를 삭제하라는 명령은 shift로 대체했습니다. 이렇게 함수 특징을 잘 생각해 코드를 작성하다보면 이미 만들어 놓은 코드로 대체할 수 있습니다. 이러면 DRY 법칙을 지키면서 효율적인 코드를 짤 수 있습니다.

위 그림처럼 특정 index 노드를 삭제할 경우, 해당 노드 바로 전 노드가 해당 노드 바로 다음 노드를 가리키게끔 해야합니다. 따라서 before 포인터를 만들었습니다. 그 다음, current 포인터를 바로 다음 노드로 설정했습니다.

if (current == NULL)
	return -1;

이 코드는 아래와 같은 경우를 대비한 코드입니다.

위 그림처럼 index 1 즉 1번째 (일반적인 숫자상으로는 2번째) 요소를 삭제하고자 했다면 리스트에 들어있는 요소가 적어도 2개 이상이어야 합니다. 하지만 노드가 1개 들어있는 경우를 위 코드에서 따지지 않습니다. 링크드리스트는 크기를 가지고 있지 않아, 실제 순회를 하기 전에는 노드가 몇개 있는지 알 수 없습니다. 만약에, 1번째 노드에서 그 다음 노드로 갔더니 해당 주소가 NULL이면 해당 리스트는 노드가 하나만 존재한다는 것을 의미합니다. 따라서 이 edge case를 다루기 위해 위와 같은 코드가 들어갔습니다.

그 다음, 현재 노드가 원하는 노드를 가리키기 위해 index - 1만큼 움직입니다. 하지만 그사이, current가 NULL이 되면 index값이 노드에 들어가 있는 수보다 크다는 것을 의미하므로 이 경우 바로 -1을 반환합니다.

for 문이 종료되면 current 포인터에 원하는 노드 주소값이 들어갔음을 의미하고, before 포인터의 노드가 current 포인터의 노드 그 다음 노드를 가리키게하고 현재 노드 메모리를 반환해줍니다.