74.3 노드 삭제 함수 만들기
이번에는 연결 리스트의 첫 노드를 삭제하는 함수를 만들어보겠습니다. 노드 삭제는 특정 노드를 삭제하고 남은 노드를 서로 연결해주는 방식입니다.
다음 내용을 소스 코드 편집 창에 입력한 뒤 실행해보세요.
linked_list_remove_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; // 기준 노드의 다음 노드에 새 노드를 지정 } 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에 삭제할 노드의 다음 노드 removNode->next를 지정합니다. 노드간 연결을 정리했다면 free 함수로 삭제할 노드 removeNode의 메모리를 해제해줍니다.
void removeFirst(struct NODE *target) // 기준 노드의 다음 노드를 삭제하는 함수 { struct NODE *removeNode = target->next; // 기준 노드의 다음 노드 주소를 저장 target->next = removeNode->next; // 기준 노드의 다음 노드에 삭제할 노드의 다음 노드를 지정 free(removeNode); // 노드 메모리 해제 }
이제 노드 3개를 생성한 뒤 removeFirst 함수로 노드를 삭제해보겠습니다. 머리 노드를 생성하고 addFirst 함수로 노드 3개를 추가하면 30 → 20 → 10 모양이 됩니다. 이때 removeFirst 함수에 머리 노드 head를 넣으면 head의 다음 노드가 삭제되므로 30이 삭제됩니다.
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인지 검사해야 합니다. 예제에서는 코드를 간단하게 만들기 위해 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); // 노드 메모리 해제 }
지금까지 단일 연결 리스트에 대해 배웠는데 포인터 처리 방법이 상당히 헷갈리고 어려웠습니다. 연결 리스트 구현은 초보자들뿐만 아니라 경력이 어느 정도 되는 프로그래머들도 까다로워하는 부분입니다. 그러다 보니 회사 면접 문제로 자주 나오는데 소프트웨어 분야로 취업하고자 한다면 연결 리스트를 완벽히 익히는 것이 좋습니다.