74.2 노드 추가 함수 만들기
연결 리스트의 노드를 생성해서 일일이 연결해주는 것은 아무래도 비효율적입니다. 이번에는 연결 리스트에 노드를 추가하는 함수를 만들어보겠습니다. 노드 추가는 두 노드 사이에 새 노드를 집어넣는 방식입니다.
다음 내용을 소스 코드 편집 창에 입력한 뒤 실행해보세요.
linked_list_add_first.c
#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); // 머리 노드 뒤에 새 노드 추가
즉, 다음과 같이 머리 노드 뒤에 새 노드가 계속 추가되므로 결과적으로 연결 리스트의 첫 부분에 노드가 계속 추가됩니다. 그래서 함수 이름이 addFirst인 것이지요.
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); // 머리 노드 메모리 해제