[C] 단일 연결 리스트(Single linked list) 구현

연결 리스트란, 하나의 노드가 값과 다음 노드를 가르키는 노드로 이루어진 자료구조이다. 그림으로 정리하면 다음과 같다.

출처: 유튜브 생활코딩

이때, node가 다음 노드만을 가르키기 때문에, 단일 연결 리스트라고 한다.

 

그런데 우리는 이미 배열(array)이 있는데, 왜 이것을 사용해야 하는지 의문이 들 것이다. 필자도 연결리스트가 "노드로 이루어진 구조이다"라는 것만 어렴풋이 알고 있었을 때 이 생각을 했었다. 그 이유는 생각보다 간단했다. 왜냐하면 배열과 연결리스트는 trade-off 관계이기 때문이다. trade-off란 한 특성이 좋아진다면, 다른 특성이 안좋아지는데, 이 둘의 관계가 이러한 특성을 갖기 때문이다.

 

배열의 경우, 원소에 접근하는 것은 효율적이지만, 데이터를 추가하거나 삭제하기 위해서는, 그 위치의 요소를 삭제한 다음에 그 뒤에 있는 모든 원소를 움직여야 한다. 따라서 원소를 추가하거나 삭제하는데에는 비효율적이다.

 

하지만 연결리스트의 경우, head노드에서 시작하여 순차적으로 접근해야하기 때문에 원소를 탐색하는데에는 비효율적이다. 하지만 데이터를 추가하거나 삽입하는데에는 단순히 포인터값만 바꾸면 되기 때문에 효율적이다. 이를 시각적으로 나타내면 다음과 같다.

 

출처: 유튜브 생활코딩

그렇다면 이러한 의문이 들 수도 있다(사실은 내가 들었던 의문). 연결 리스트에서 데이터를 추가하거나 삭제하는 경우, 결국 그 인덱스만큼 이동해야하는데, 그렇다면 연결리스트의 추가, 삭제하는 것도 시간적인 면에서 비효율적인 것이 되는게 아닌가? 라는 의문이었다. 

 

배열의 경우 중앙의 값을 추가/삭제하는 경우, 그 뒤의 요소들을 전부 움직여야 하는데, 이때 깊은 복사가 일어나게 된다. 문제는 깊은 복사는 무거운 연산이기 때문에 시간적으로 오래걸린다. 하지만 연결리스트에서 이동할 때에도 포인터값의 복사를 하면서 이동하지만, 이때의 복사는 얕은 복사이기 때문에 이 차이점으로 인해 연결리스트가 추가, 삭제하는 부분에서 배열보다 효율적이게 된다.

 

이제 단일 연결 리스트를 구현해보자. 구현할 함수는 삽입(insert_node), 삭제(delete_node), 탐색(search), 데이터 얻어오기(get_data), 길이구하기(size), 출력하기(print_ll)이다.

 

연결리스트를 시각화하고, 의사코드를 보여주는 사이트를 참조해보는 것도 좋다.

https://visualgo.net/en/list

Linked List (Single, Doubly), Stack, Queue, Deque - VisuAlgo

 

우선은 node가 필요하다. node는 다음 node를 가리킬 포인터와 데이터로 구성된다. 필자는 int형 데이터를 담지만, 어떻게 바꿔도 상관 없다.

typedef struct Node{
    int data;
    struct Node* next;
}node;

 

이때 node는 다음 node를 가르키는 포인터이다. 자기 자신을 참조하는 포인터라고 하여 "자기참조구조체 포인터" 라고는 하지만, 용어가 중요하진 않으니 패스.

 

head노드를 동적할당으로 생성하자. head노드는 데이터가 들어있지는 않고, 단지 다음 노드를 가르키는 연결리스트의 중심과 같은 노드이다.

node* head = (node* )malloc(sizeof(node));
head->data = 0;
head->next = NULL;

 

선언해준 후에, data는 그냥 0으로 넣고, 다음 node를 NULL로 초기화 해주자.

 

이제 함수들을 구현해보자. 우선 삽입(insert)부터 시작해보자. 연결리스트에서 데이터를 추가하는 방식은 다음과 같다.

1. 삽입하고자 하는 위치 바로 앞까지 간다. (4번째 index에 추가하고자 한다면, 3번째 index까지 간다는 뜻) 이때의 노드가 NULL이 아니라면, 이 노드를 임시로 저장한다. 이때의 노드를 a라고 하자.
2. 새로운 노드를 동적할당하여 생성한다. 이때의 노드를 b라고 하자
3. b에 데이터를 담고, 이 노드의 next를 a의 next로 저장한다.
4. a의 next를 b의 next로 바꾼다.

말로만 살펴보면 힘들수도 있으니 위의 시각화한 사이트를 통해 자세히 보자.

출처: https://visualgo.net/en/list

위와 같은 연결 리스트가 있다고 치자. 2번째 위치, 즉 원래 93이 있는 자리에 5라는 값이 들어있는 노드를 추가하려고 한다.

출처: https://visualgo.net/en/list

이렇게 93노드 바로 앞, 77노드를 임시로 저장한다.

출처: https://visualgo.net/en/list

새로운 노드인 5를 생성하고, 새로 생성한 노드가 77의 next인 93을 가르키게 한다.

출처: https://visualgo.net/en/list

그리고 77노드가 5를 가르키게 하면

출처: https://visualgo.net/en/list

무사히 추가가 된다.

 

이 과정을 코드로 구현하면 된다.

void insert_node(node* head, const int index, const int data) {
    int k = index; // 인덱스를 저장한다.
    node* pre_node = head; // index-1번째 노드를 가르킬 임시 변수
    node* insert = (node*)malloc(sizeof(node)); // 추가할 노드를 동적할당으로 생성
    insert->data = data; // 데이터를 담는다.

    // index-1번째로 이동한다. 만약 index가 연결리스트 범위를 초과한다면(null) 반복을 멈춘다.
    while (k-- && pre_node != NULL)
        pre_node = pre_node->next; 
    
    if (pre_node == NULL) { // 만약 null이라면
        free(insert); // 동적할당을 해제하고
        return; // 돌아간다.
    } 

    insert->next = pre_node->next; // 새로 생성한 노드는 index-1번째 노드가 가르키던 노드를 가르키고
    pre_node->next = insert; // index-1번째 노드는 insert를 가르키게 한다.
}

 

연결리스트에서 노드를 삭제(delete_node)하는 과정은 다음과 같다.

1. 삭제하고자 하는 노드 바로 앞까지 이동한다. 이때 이 다음 노드가 NULL이 아니라면 이 노드를 임시로 저장한다. 이때의 노드를 a라고 하자.
2. 삭제할 노드는 저장한 노드의 다음 노드이다. 그 노드를 임시로 저장한다. 이때의 노드를 b라고 하자
3. b의 next를 a의 next에 저장한다.
4. b를 삭제한다.

역시 그림으로 자세히 보자.

 

아까의 그 연결리스트이다. 아까 5를 추가해봤으니, 이번에는 5를 다시 삭제해보자. 5의 index는 2이다.

출처: https://visualgo.net/en/list

이제 5노드 이전인 77노드로 이동한다.

출처: https://visualgo.net/en/list

77노드의 next를 5노드의 next인 93노드로 바꾼다.

출처: https://visualgo.net/en/list

5노드를 삭제한다.

출처: https://visualgo.net/en/list

이제 이 과정을 코드로 옮겨보자.

void delete_node(node* head, const int index) {
    int k = index; // 인덱스 저장
    node* temp = head; // index-1번째 노드를 가르킬 임시 변수
    node* garbage = NULL; // 삭제할 노드를 저장할 임시 변수

    while (k-- && temp != NULL)
        temp = temp->next; // index-1번째 노드로 이동 

    if (temp == NULL || temp->next == NULL) // 본인, 또는 다음 노드가 NULL이라면
        return; // 그냥 돌아간다.

    garbage = temp->next; // 삭제할 노드를 저장.
    temp->next = garbage->next; // 삭제할 노드의 다음 노드와 연결하고
    free(garbage); // 노드를 삭제
}

 

삽입할때와 달리 NULL체크를 본인 노드가 아닌 다음 노드도 체크하는데, 삽입할때의 경우, 다음 노드가 NULL이더라도, 본인이 NULL이 아니라면 추가가 가능하기 때문에 본인이 NULL인지 체크해야한다.

 

하지만, 삭제하는 경우, 본인이 NULL이면 while문 중간에서 조건이 false이기 때문에 반복을 멈출 뿐더러, 본인이 NULL이면 next도 NULL이기 때문이다. 또한 본인이 NULL이 아닌 경우, 다음 NULL노드는 지울수가 없기 때문에, 다음 노드가 NULL인지 체크하는 것이다.

 

이제 남은 함수인 탐색(search)과 데이터를 얻어오는(get_data)함수, 길이(size)를 반환하는 함수와 출력(print_ll)할 함수를 구현해보자.

 

연결리스트의 경우, 다음 노드로 접근하려면, 무조건 head에서부터 차례대로 가야하기 때문에, 선형탐색을 진행해야 한다. 따라서 head에서부터 출발하여야 한다. 그러므로 head에서부터 차례로 조건문을 통해 진행한다.

 

이를 코드로 구현해보았다.

int search(node* head, const int val) {
    if (head->next == NULL) return -1; // 다음 노드가 NULL이면 -1 return
    
    int index = 0;
    node* temp = head->next; // head는 기준이기만 할 뿐, index를 세는데에는 들어가면 안된다.
    
    while (temp->data != val) {
        ++index;
        temp = temp->next;

        if (temp == NULL) return -1; // 찾고자 하는 값이 없는 경우 -1 return
    }
    return index; // index return
}

int get_data(node* head, const int index) {
    if (head->next == NULL) return -1; // 다음 노드가 NULL이면 -1 return
    
    int k = index;
    node* temp = head->next;
    
    while(k--) temp = temp->next; // index로 이동
    return temp->data; // data return
}

int size(node* head){
    node* temp = head->next;
    int len = 0;
    while(temp != NULL) { // temp가 NULL이 아닐떄 까지
        ++len; // 길이 증가
        temp = temp->next; // 다음 노드로 이동
    }
    return len; // 길이 return
}

void print_ll(node* head) {
    if (head->next == NULL) return; // 다음 노드가 NULL이라면 return

    node* temp = head->next;
    while(temp != NULL) { // temp가 NULL이 아닐때 까지
        printf("%d ", temp->data); // 공백으로 구분하여 출력
        temp = temp->next; // 다음 노드로 이동
    }
    printf("\n"); // 개행
}

 

이렇게 구현하고자 한 6개의 함수를 모두 구현했다. 이제 제대로 작동하는지 확인해보자.

 

위에서 head를 할당했다면, 함수들을 실행시켜 보자.

int main() {
    node* head = (node* )malloc(sizeof(node));
    head->data = 0;
    head->next = NULL;

    insert_node(head, 0, 123);
    print_ll(head); // expect 123

    insert_node(head, 1, 10);
    print_ll(head); // expect 123 10

    insert_node(head, 2, 20);
    print_ll(head); // expect 123 10 20

    insert_node(head, 1, 11);
    print_ll(head); // expect 123 11 10 20
    
    insert_node(head, 5, 19); // 길이를 넘어서는 인덱스를 전달해본다.
    print_ll(head); // expect 123 11 10 20

    printf("%d\n", search(head, 20)); // expext 3
    printf("%d\n", search(head, 11)); // expext 1
    printf("%d\n", size(head)); // expext 4
    printf("%d\n", get_data(head, 3)); // expext 20

    delete_node(head, 0);
    print_ll(head); // expext 11 10 20
    
    delete_node(head, 4); // 길이를 넘어서는 인덱스를 전달해본다.
    print_ll(head); // expext 11 10 20
}

 

실행 결과

연결리스트, 그 중에서도 단일 연결리스트를 구현해보았다. 이번에는 C를 이용했지만, 기회가 된다면 이중 연결 리스트도 구현해보고자 한다. 이후에 C++의 클래스를 좀 더 익히고, templete기능을 통해 int형이 아닌 다양한 데이터 형태에 대해서도 구현해보고자 한다.

 

참고한 사이트

• https://opentutorials.org/module/1335/8821
• https://visualgo.net/en/list