66. 연결 리스트(Linked List)

---

1. 키워드

• 연결 리스트(Linked List)
• 단일 연결 리스트(Singly Linked List)

2. 연결 리스트 구현하기

• 연결 리스트는 데이터가 담긴 노드(메모리 공간)를 일렬로 연결해놓았다고 해서 연결 리스트라고 부르며 특징은 다음과 같다.

1] 리스트의 중간 지점에 노드를 손쉽게 추가하거나 삭제할 수 있다.

2] 최악의 경우 특정 노드를 찾으려면 노드를 모두 검색해야 한다.

3] 크기가 고정되어 있지 않다.

• 다음은 다른 노드를 가리키는 포인터가 하나씩만 있는 단일 연결 리스트이다.

• 지금부터 구조체, 포인터, 함수, 메모리 할당을 사용하여 단일 연결 리스트를 구현하는 방법을 알아보자.

3. 연결 리스트 구조체 만들고 사용하기

• 먼저 연결 리스트의 구조체를 정의한다.
• 연결 리스트는 노드들의 집합이므로 실제로는 노드의 구조체만 정의하면 된다.

struct NODE // 연결 리스트의 노드 구조체
{
    struct NODE *next; // 다음 노드의 주소를 저장할 포인터
    int data;          // 데이터를 저장할 멤버
};

• NODE 구조체에서 가장 중요한 부분은 struct NODE *next;이다.
• next에는 NODE 구조체로 만든 다른 노드의 메모리 주소를 저장한다.
• NODE 구조체에서 데이터는 int 타입 하나만 저장했다.
• 실제로 사용할 때는 용도에 따라서 다양한 자료형으로 된 멤버 여러 개를 넣으면 된다.

• 이제 단일 연결 리스트에서 노드의 종류를 알아보자.
• 노드는 역할에 따라서 두 가지로 나뉜다.

1] 머리 노드(Head Node)

• 단일 연결 리스트의 기준점이며 헤드라고도 부른다.
• 머리 노드는 첫 번째 노드를 가리키는 용도이므로 데이터를 저장하지 않는다.

2] 노드(Node)

• 단일 연결 리스트에서 데이터가 저장되는 실제 노드이다.

• 이 두 종류의 노드는 역할만 다를 뿐 모두 NODE 구조체를 사용한다.

• 이제 NODE 구조체로 머리 노드를 만든 뒤 노드가 2개인 연결 리스트를 만들어보자.
• 그림으로 표현하면 다음과 같은 모양이다.

#include <stdio.h>
#include <stdlib.h> // malloc, free 함수가 선언된 헤더 파일

struct NODE // 연결 리스트의 노드 구조체
{
    struct NODE *next; // 다음 노드의 주소를 저장할 포인터
    int data;          // 데이터를 저장할 멤버
};

int main()
{
    struct NODE *head = malloc(sizeof(struct NODE)); // 머리 노드 생성
                                                     // 머리 노드는 데이터를 저장하지 않음

    struct NODE *node1 = malloc(sizeof(struct NODE)); // 첫 번째 노드 생성
    head->next = node1;                               // 머리 노드 다음은 첫 번째 노드
    node1->data = 10;                                 // 첫 번째 노드에 10 저장

    struct NODE *node2 = malloc(sizeof(struct NODE)); // 두 번째 노드 생성
    node1->next = node2;                              // 첫 번째 노드 다음은 두 번째 노드
    node2->data = 20;                                 // 두 번째 노드에 20 저장

    node2->next = NULL; // 두 번째 노드 다음은 노드가 없음(NULL)

    struct NODE *curr = head->next; // 연결 리스트 순회용 포인터에 첫 번째 노드의 주소 저장

    while (curr != NULL) // 포인터가 NULL이 아닐 때 계속 반복
    {
        printf("%d\n", curr->data); // 현재 노드의 데이터 출력
        curr = curr->next;          // 포인터에 다음 노드의 주소 저장
    }

    free(node2); // 노드 메모리 해제
    free(node1); // 노드 메모리 해제
    free(head);  // 머리 노드 메모리 해제

    return 0;
}

// 10
// 20

• 연결 리스트에서 노드를 추가하는 규칙은 간단하다.

1] 노드에 메모리 할당

2] next 멤버에 다음 노드의 메모리 주소 저장

3] data 멤버에 데이터 저장

4] 마지막 노드라면 next 멤버에 NULL 저장

• 먼저 머리 노드를 생성한다.
• 머리 노드는 연결 리스트의 기준점 역할만 하므로 데이터는 저장하지 않는다.

struct NODE *head = malloc(sizeof(struct NODE)); // 머리 노드 생성
                                                 // 머리 노드는 데이터를 저장하지 않음

• 이제 첫 번째 노드를 생성한 뒤 머리 노드의 next에 첫 번째 노드의 주소를 저장한다.
• 다시 두 번째 노드를 생성한 뒤 첫 번째 노드의 next에 두 번째 노드의 주소를 저장한다.
• 마지막으로 두 번째 노드의 다음에는 노드가 없으므로 NULL을 저장하면 된다.

struct NODE *node1 = malloc(sizeof(struct NODE)); // 첫 번째 노드 생성
head->next = node1;                               // 머리 노드 다음은 첫 번째 노드
node1->data = 10;                                 // 첫 번째 노드에 10 저장

struct NODE *node2 = malloc(sizeof(struct NODE)); // 두 번째 노드 생성
node1->next = node2;                              // 첫 번째 노드 다음은 두 번째 노드
node2->data = 20;                                 // 두 번째 노드에 20 저장

node2->next = NULL; // 두 번째 노드 다음은 노드가 없음(NULL)

• 이렇게 생성한 연결 리스트를 그림으로 표현하면 다음과 같은 모양이 된다.

• 이제 연결 리스트의 모든 노드를 순회하는 방법이다.
• 간단하게 연결 리스트에서 마지막 노드의 다음(next)은 NULL이라는 점을 이용한다.
• 먼저 연결 리스트 순회용 포인터 curr를 새로 생성해서 첫 번째 노드의 주소(head->next)를 저장한다.
• 그리고 curr가 NULL이 아닐 때까지 계속 반복한다.
• 반복문 안에서는 현재 노드의 데이터를 출력하고 curr에 curr->next를 저장하면 된다.
• 그럼 next를 계속 따라가다가 마지막에 다다르면 NULL이 나오므로 반복이 끝난다.

struct NODE *curr = head->next; // 연결 리스트 순회용 포인터에 첫 번째 노드의 주소 저장

while (curr != NULL) // 포인터가 NULL이 아닐 때 계속 반복
{
    printf("%d\n", curr->data); // 현재 노드의 데이터 출력
    curr = curr->next;          // 포인터에 다음 노드의 주소 저장
}

• 연결 리스트 사용이 끝났다면 free 함수로 일반 노드와 머리 노드의 메모리를 해제한다.

free(node2); // 노드 메모리 해제
free(node1); // 노드 메모리 해제
free(head);  // 머리 노드 메모리 해제

4. 노드 추가 함수 만들기

• 연결 리스트의 노드를 생성해서 일일이 연결해 주는 것은 비효율적이다.
• 이번에는 연결 리스트에 노드를 추가하는 함수를 만들어보자.
• 노드 추가는 두 노드 사이에 새 노드를 집어넣는 방식이다.

#include <stdio.h>
#include <stdlib.h> // malloc, free 함수가 선언된 헤더 파일

struct NODE // 연결 리스트의 노드 구조체
{
    struct NODE *next; // 다음 노드의 주소를 저장할 포인터
    int data;          // 데이터를 저장할 멤버
};

void addFirst(struct NODE *target, int data) // 기준 노드 뒤에 노드를 추가하는 함수
{
    struct NODE *newNode = malloc(sizeof(struct NODE)); // 새 노드 생성
    newNode->next = target->next;                       // 새 노드의 다음 노드에 기준 노드의 다음 노드를 지정
    newNode->data = data;                               // 데이터 저장

    target->next = newNode; // 기준 노드의 다음 노드에 새 노드를 지정
}

int main()
{
    struct NODE *head = malloc(sizeof(struct NODE)); // 머리 노드 생성
                                                     // 머리 노드는 데이터를 저장하지 않음

    head->next = NULL;

    addFirst(head, 10); // 머리 노드 뒤에 새 노드 추가
    addFirst(head, 20); // 머리 노드 뒤에 새 노드 추가
    addFirst(head, 30); // 머리 노드 뒤에 새 노드 추가

    struct NODE *curr = head->next; // 연결 리스트 순회용 포인터에 첫 번째 노드의 주소 저장

    while (curr != NULL) // 포인터가 NULL이 아닐 때 계속 반복
    {
        printf("%d\n", curr->data); // 현재 노드의 데이터 출력
        curr = curr->next;          // 포인터에 다음 노드의 주소 저장
    }

    curr = head->next; // 연결 리스트 순회용 포인터에 첫 번째 노드의 주소 저장

    while (curr != NULL) // 포인터가 NULL이 아닐 때 계속 반복
    {
        struct NODE *next = curr->next; // 현재 노드의 다음 노드 주소를 임시로 저장
        free(curr);                     // 현재 노드 메모리 해제
        curr = next;                    // 포인터에 다음 노드의 주소 저장
    }

    free(head); // 머리 노드 메모리 해제

    return 0;
}

// 30
// 20
// 10

• 다음과 같이 새 노드를 추가하는 함수는 기준 노드의 포인터 target과 새 노드에 저장할 데이터 data를 매개변수로 받는다.
• 여기서 새 노드는 기준 노드 뒤에 추가하도록 만든다.

void addFirst(struct NODE *target, int data) // 기준 노드 뒤에 노드를 추가하는 함수
{
    struct NODE *newNode = malloc(sizeof(struct NODE)); // 새 노드 생성
    newNode->next = target->next;                       // 새 노드의 다음 노드에 기준 노드의 다음 노드를 지정
    newNode->data = data;                               // 데이터 저장

    target->next = newNode; // 기준 노드의 다음 노드에 새 노드를 지정
}

• 즉, 새 노드의 다음 노드에 기준 노드를 지정하고, 기준 노드의 다음 노드에 새 노드를 지정하면 새 노드가 된다.

• 이제 addFirst 함수를 사용하여 노드를 추가해 보자.
• 먼저 연결 리스트의 머리 노드를 생성한다.
• 아직 머리 노드의 다음 노드는 없으므로 NULL을 지정한다.

struct NODE *head = malloc(sizeof(struct NODE)); // 머리 노드 생성
                                                 // 머리 노드는 데이터를 저장하지 않음

head->next = NULL;

• addFirst 함수에 머리 노드 head와 저장할 데이터를 넣어서 머리 노드 뒤에 새 노드를 추가한다.

addFirst(head, 10); // 머리 노드 뒤에 새 노드 추가
addFirst(head, 20); // 머리 노드 뒤에 새 노드 추가
addFirst(head, 30); // 머리 노드 뒤에 새 노드 추가

• 즉, 다음과 같이 머리 노드 뒤에 새 노드가 계속 추가되므로 결과적으로 연결 리스트의 첫 부분에 노드가 계속 추가된다.

• while 반복문으로 연결 리스트를 순회하면서 데이터를 출력해 보면 30 20 10이 출력된다.

struct NODE *curr = head->next; // 연결 리스트 순회용 포인터에 첫 번째 노드의 주소 저장

while (curr != NULL) // 포인터가 NULL이 아닐 때 계속 반복
{
    printf("%d\n", curr->data); // 현재 노드의 데이터 출력
    curr = curr->next;          // 포인터에 다음 노드의 주소 저장
}

• 연결 리스트의 사용이 끝났다면 free 함수로 각 노드를 해제해야 하는데 머리 노드 포인터 head만 있고, 이후 추가한 노드의 포인터는 따로 저장해놓지 않았다.
• 따라서 연결 리스트를 처음부터 순회하면서 각 노드를 해제해 주면 된다.
• 여기서 주의할 부분은 curr->next인데 curr를 먼저 해제하면 curr->next에 접근할 수 없게 된다.
• 그러므로 curr->next를 다른 포인터에 임시로 저장해놓은 뒤 curr를 해제한다.

curr = head->next; // 연결 리스트 순회용 포인터에 첫 번째 노드의 주소 저장

while (curr != NULL) // 포인터가 NULL이 아닐 때 계속 반복
{
    struct NODE *next = curr->next; // 현재 노드의 다음 노드 주소를 임시로 저장
    free(curr);                     // 현재 노드 메모리 해제
    curr = next;                    // 포인터에 다음 노드의 주소 저장
}

• 마지막으로 머리 노드 head의 메모리를 해제한다.

free(head); // 머리 노드 메모리 해제

5. 노드 삭제 함수 만들기

• 이번에는 연결 리스트의 첫 노드를 삭제하는 함수를 만들어보자.
• 노드 삭제는 특정 노드를 삭제하고 남은 노드를 서로 연결해 주는 방식이다.

#include <stdio.h>
#include <stdlib.h> // malloc, free 함수가 선언된 헤더 파일

struct NODE // 연결 리스트의 노드 구조체
{
    struct NODE *next; // 다음 노드의 주소를 저장할 포인터
    int data;          // 데이터를 저장할 멤버
};

void addFirst(struct NODE *target, int data) // 기준 노드 뒤에 노드를 추가하는 함수
{
    struct NODE *newNode = malloc(sizeof(struct NODE)); // 새 노드 생성
    newNode->next = target->next;                       // 새 노드의 다음 노드에 기준 노드의 다음 노드를 지정
    newNode->data = data;                               // 데이터 저장

    target->next = newNode; // 기준 노드의 다음 노드에 새 노드를 지정
}

void removeFirst(struct NODE *target) // 기준 노드의 다음 노드를 삭제하는 함수
{
    struct NODE *removeNode = target->next; // 기준 노드의 다음 노드 주소를 저장
    target->next = removeNode->next;        // 기준 노드의 다음 노드에 삭제할 노드의 다음 노드를 지정

    free(removeNode); // 노드 메모리 해제
}

int main()
{
    struct NODE *head = malloc(sizeof(struct NODE)); // 머리 노드 생성
                                                     // 머리 노드는 데이터를 저장하지 않음

    head->next = NULL;

    addFirst(head, 10); // 머리 노드 뒤에 새 노드 추가
    addFirst(head, 20); // 머리 노드 뒤에 새 노드 추가
    addFirst(head, 30); // 머리 노드 뒤에 새 노드 추가

    removeFirst(head); // 머리 노드 뒤에 있는 노드를 삭제

    struct NODE *curr = head->next; // 연결 리스트 순회용 포인터에 첫 번째 노드의 주소 저장

    while (curr != NULL) // 포인터가 NULL이 아닐 때 계속 반복
    {
        printf("%d\n", curr->data); // 현재 노드의 데이터 출력
        curr = curr->next;          // 포인터에 다음 노드의 주소 저장
    }

    curr = head->next; // 연결 리스트 순회용 포인터에 첫 번째 노드의 주소 저장

    while (curr != NULL) // 포인터가 NULL이 아닐 때 계속 반복
    {
        struct NODE *next = curr->next; // 현재 노드의 다음 노드 주소를 임시로 저장
        free(curr);                     // 현재 노드 메모리 해제
        curr = next;                    // 포인터에 다음 노드의 주소 저장
    }

    free(head); // 머리 노드 메모리 해제

    return 0;
}

// 20
// 10

• 노드를 삭제하는 함수는 기준 노드의 포인터를 매개변수로 받는다.
• 하지만 삭제하는 노드는 기준 노드가 아닌 기준 노드의 다음 노드이다.
• 따라서 기준 노드의 다음 노드 target->next에 삭제할 노드의 다음 노드 removeNode->next를 지정한다.
• 노드간 연결을 정리했다면 free 함수로 삭제할 노드 removeNode의 메모리를 해제해 준다.

void removeFirst(struct NODE *target) // 기준 노드의 다음 노드를 삭제하는 함수
{
    struct NODE *removeNode = target->next; // 기준 노드의 다음 노드 주소를 저장
    target->next = removeNode->next;        // 기준 노드의 다음 노드에 삭제할 노드의 다음 노드를 지정

    free(removeNode); // 노드 메모리 해제
}

• 이제 노드 3개를 생성한 뒤 removeFirst 함수로 노드를 삭제해 보자.

struct NODE *head = malloc(sizeof(struct NODE)); // 머리 노드 생성
                                                 // 머리 노드는 데이터를 저장하지 않음

head->next = NULL;

addFirst(head, 10); // 머리 노드 뒤에 새 노드 추가
addFirst(head, 20); // 머리 노드 뒤에 새 노드 추가
addFirst(head, 30); // 머리 노드 뒤에 새 노드 추가

removeFirst(head); // 머리 노드 뒤에 있는 노드를 삭제

• while 반복문으로 모든 노드의 데이터를 출력해 보면 20 10이 나온다.

struct NODE *curr = head->next; // 연결 리스트 순회용 포인터에 첫 번째 노드의 주소 저장

while (curr != NULL) // 포인터가 NULL이 아닐 때 계속 반복
{
    printf("%d\n", curr->data); // 현재 노드의 데이터 출력
    curr = curr->next;          // 포인터에 다음 노드의 주소 저장
}

노드가 NULL인지 검사

• 연결 리스트 함수를 구현할 때는 노드가 NULL인지 검사해야 한다.

void addFirst(struct NODE *target, int data) // 기준 노드 뒤에 노드를 추가하는 함수
{
    if (target == NULL) // 기준 노드가 NULL이면
        return;         // 함수를 끝냄

    struct NODE *newNode = malloc(sizeof(struct NODE)); // 새 노드 생성

    if (newNode == NULL) // 메모리 할당에 실패하면
        return;          // 함수를 끝냄

    newNode->next = target->next; // 새 노드의 다음 노드에 기준 노드의 다음 노드를 지정
    newNode->data = data;         // 데이터 저장

    target->next = newNode; // 기준 노드의 다음 노드에 새 노드를 지정
}

void removeFirst(struct NODE *target) // 기준 노드의 다음 노드를 삭제하는 함수
{
    if (target == NULL) // 기준 노드가 NULL이면
        return;         // 함수를 끝냄

    struct NODE *removeNode = target->next; // 기준 노드의 다음 노드 주소를 저장

    if (removeNode == NULL) // 삭제할 노드가 NULL이면
        return;             // 함수를 끝냄

    target->next = removeNode->next; // 기준 노드의 다음 노드에 삭제할 노드의 다음 노드를 지정

    free(removeNode); // 노드 메모리 해제
}

---

References

• https://dojang.io/mod/page/view.php?id=644
• https://dojang.io/mod/page/view.php?id=645
• https://dojang.io/mod/page/view.php?id=646
• https://dojang.io/mod/page/view.php?id=647