[WEEK 05] C - 연결 리스트

신호정 벨로그·2021년 9월 5일

Today I Learned

목록 보기

21/89

연결 리스트 (Linked List)

1. 연결 리스트 노드 구조체 생성

먼저 연결 리스트 구조체 정의한다. 연결 리스트는 노드들의 집합이므로 노드들의 구조체를 정의한다.

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

단일 연결 리스트에서 노드의 종류

머리 노드(head node): 단일 연결 리스트의 기준점이며 헤드라고 부른다. 첫번째 노드를 가리키는 용도이며 데이터를 저장하지 않는다.
노드(node): 단일 연결 리스트에서 데이터가 저장되는 실제 노드

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

#include <stdio.h>
#include <stdlib.h>

// 연결 리스트의 노드 구조체
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;
    // 첫번째 노드에 10을 저장
    node1 -> data = 10;

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

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

    // 연결 리스트 순회용 포인터에 첫번째 노드의 주소값 저장
    struct NODE *curr = head -> next;
    // 포인터가 NULL이 아니면 계속 반복
    while (curr != NULL) {
        // 현재 노드의 데이터 출력
        printf("%d \n", curr -> data);
        // 포인터에 다음 노드의 주소값 저장
        curr = curr -> next;
    }

    // 두번째 노드 메모리 해제
    free(node2);
    // 첫번째 노드 메모리 해제
    free(node1);
    // 머리 노드 메모리 해제
    free(head);
    
    return 0;
}

2. 연결 리스트 노드 추가 함수

새로운 노드를 추가하는 함수는 기준 노드의 포인터 target과 새로운 노드에 저장할 데이터 data를 매개변수로 받는다.

새로운 노드의 다음 노드에 기준 노드를 지정하고, 기준 노드의 다음 노드에 새로운 노드를 지정하면 새로운 노드가 추가된다.

addFirst 함수에 머리 노드 head와 저장할 데이터를 넣어서 머리 노드 뒤에 새로운 노드를 추가한다. 머리 노드 뒤에 새로운 노드가 계속 추가되므로 결과적으로 연결 리스트의 첫 부분에 노드가 계속 추가된다.

연결 리스트의 사용이 끝나면 free 함수로 각 노드의 메모리를 해제해야 하는데 머리 노드 포인터 head만 있고, 새롭게 추가한 노드들의 포인터는 저장하지 않았기 때문에 while 반복문으로 연결 리스트를 순회하며 각 노드의 메모리를 해제한다. curr -> next인데 curr를 먼저 해제하면 curr -> next에 접근할 수 없다. 그러므로 curr -> next를 다른 포인터에 임시로 저장한 후 curr를 해제한다.

#include <stdio.h>
#include <stdlib.h>

// 연결 리스트의 노드 구조체 생성
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;
    // 포인터가 NULL이 아니면 계속 반복
    while (curr != NULL) {
        // 현재 노드의 데이터 출력
        printf("%d \n", curr -> data);
        // 포인터에 다음 노드의 주소값 저장
        curr = curr -> next;
    }

    // 연결 리스트 순회용 포인터에 첫번째 노드의 주소값 저장
    curr = head -> next;
    // 포인터가 NULL이 아니면 계속 반복
    while (curr != NULL) {
        // 현재 노드의 다음 노드 주소값을 임시로 저장
        struct NODE *next = curr -> next;
        // 현재 노드 메모리 해제
        free(curr);
        // 포인터에 다음 노드의 주소값 저장
        curr = next;
    }
    // 머리 노드 메모리 해제
    free(head);

    return 0;
}

3. 연결 리스트 노드 삭제 함수

노드를 삭제하는 함수는 기준 노드의 포인터를 매개변수로 받는다.

하지만 삭제하는 노드는 기준 노드가 아닌 기준 노드의 다음 노드이기 때문에 기준 노드의 다음 노드 target -> next에 삭제할 노드의 다음 노드 removeNode -> next를 지정한다.

노드 간 연결을 정리하면 free 함수로 삭제할 노드 removeNode의 메모리를 해제한다.

#include <stdio.h>
#include <stdlib.h>

// 연결 리스트의 노드 구조체
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;
    // 포인터가 NULL이 아니면 계속 반복
    while (curr != NULL) {
        // 현재 노드의 데이터 출력
        printf("%d \n", curr -> data);
        // 포인터에 다음 노드의 주소값 저장
        curr = curr -> next;
    }

    // 연결 리스트 순회용 포인터에 첫번째 노드의 주소값 저장
    curr = head -> next;
    // 포인터가 NULL아 아니면 계속 반복
    while (curr != NULL) {
        // 현재 노드의 다음 노드 주소값 임시로 저장
        struct NODE *next = curr -> next;
        // 현재 노드의 메모리 해제
        free(curr);
        // 포인터에 다음 노드의 주소값 저장
        curr = next;
    }

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

    return 0;
}

4. 연결 리스트 노드 검색 함수

#include <stdio.h>
#include <stdlib.h>

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;
}

// 단일 연결 리스트는 특정 노드를 찾으려면 첫번째 노드부터 마지막 노드까지 차례대로 검색해야 한다.
struct NODE *findNode(struct NODE *node, int data) {
    if (node == NULL)
        return NULL;
    
    struct NODE *curr = node -> next;
    while (curr != NULL) {
        // 현재 노드의 데이터와 매개변수로 받은 데이터를 비교하여 같으면 현재 노드를 반환
        if (curr -> data == data)
            return curr;

        // 다르면 다음 노드로 넘어간다.
        curr = curr -> next;
    }

    // 값을 찾지 못했거나 처음부터 node가 NULL이라면 NULL을 반환
    return NULL;
}

int main() {
    struct NODE *head = malloc(sizeof(struct NODE));
    head -> next = NULL;

    addFirst(head, 10);
    addFirst(head, 20);
    addFirst(head, 30);

    struct NODE *found = findNode(head, 20);
    printf("%d \n", found -> data);

    struct NODE *curr = head -> next;
    while (curr != NULL) {
        struct NODE *next = curr -> next;
        free(curr);
        curr = next;
    }

    free(head);

    return 0;
}

신호정 벨로그

hello world

이전 포스트

[WEEK 05] C - 동적 메모리 할당

다음 포스트