C 언어 단일 연결 리스트
1. 단일 연결 리스트 소개
단일 연결 리스트(Single Linked List)는 노드(Node)라는 구조체에 데이터와 다음 노드를 가리키는 포인터를 갖는 데이터 구조입니다. 각 노드는 데이터와 다음 노드를 가리키는 포인터를 가지고 있고, 마지막 노드는 다음 노드를 가리키는 포인터가 NULL이 됩니다. 이렇게 구성된 단일 연결 리스트는 리스트의 시작 또는 끝에서 데이터의 삽입과 삭제가 빠르다는 장점을 가지고 있습니다. 그러나 각 노드마다 '다음 노드를 가리키는 포인터'를 저장해야 하므로, 노드의 수에 비례하여 추가적인 메모리를 사용하는 단점이 있습니다.
그림: 단일 연결 리스트
다음과 같은 구조체로 단일 연결 리스트를 구현합니다. 이때, 동적 메모리 할당을 위해 malloc 함수를 사용합니다.
typedef struct Node
{
int data;
struct Node* next;
} Node;
단일 연결 리스트를 간단한 코드로 표현하면 다음과 같습니다.
이 코드에서 사용될 head 이름의 노드를 미리보기 그림으로 표현해 보면 다음과 같습니다.
그림: head 노드
코드: linked_list_intro.c
#include <stdio.h>
#include <stdlib.h>
// 노드 구조를 정의합니다.
struct Node
{
int data; // 노드가 저장할 데이터
struct Node* next; // 다음 노드를 가리키는 포인터(자기 참조 구조체)
};
int main(void)
{
// 링크드 리스트의 head를 선언하고 초기화합니다.
struct Node* head = NULL;
// head 노드에 대해 메모리를 동적으로 할당합니다.
head = (struct Node*)malloc(sizeof(struct Node));
// 할당된 메모리 공간에 접근이 가능한지 확인합니다.
if (head == NULL)
{
printf("head 노드 메모리 할당 실패.\n");
return -1;
}
// head 노드의 데이터를 설정하고, 다음 노드를 가리키는 포인터를 NULL로 설정합니다.
head->data = 1;
head->next = NULL;
// head 노드의 데이터를 출력합니다.
printf("head 노드의 데이터: %d\n", head->data);
// 메모리 해제
free(head);
return 0;
}
head 노드의 데이터: 1
위 코드는 단일 연결 리스트의 가장 간단한 예시입니다. head 포인터가 가리키는 노드가 단일 연결 리스트의 첫 번째 노드입니다. 첫 번째 노드의 데이터 값은 1이고, 다음 노드를 가리키는 포인터가 NULL입니다. 마지막 줄에서는 head 노드의 데이터를 출력하고 있습니다.
2. 단일 연결 리스트의 확장
이제 더 복잡한 단일 연결 리스트를 만들어 봅시다. 이번에는 세 개의 노드를 만들어 연결해보겠습니다. 아래 코드에서는 각 노드에 대한 메모리를 동적으로 할당하고, 각 노드의 데이터 부분에 값을 할당한 후, 각 노드를 연결합니다. 그리고 연결된 리스트의 노드를 순차적으로 출력합니다.
코드: simple_linked_list.c
#include <stdio.h>
#include <stdlib.h>
// 노드 구조를 정의합니다.
typedef struct Node
{
int data; // 노드의 데이터 부분
struct Node* next; // 다음 노드를 가리키는 포인터
} Node;
int main(void)
{
Node* firstNode = NULL; // 첫 번째 노드의 포인터를 초기화합니다.
Node* secondNode = NULL; // 두 번째 노드의 포인터를 초기화합니다.
Node* thirdNode = NULL; // 세 번째 노드의 포인터를 초기화합니다.
// 첫 번째 노드를 할당하고 데이터를 설정합니다.
firstNode = (Node*)malloc(sizeof(Node)); // 메모리를 동적으로 할당합니다.
if (firstNode == NULL)
{
printf("첫 번째 노드에 대한 메모리 할당 실패.\n");
return -1;
}
firstNode->data = 1; // 첫 번째 노드의 데이터 값을 설정합니다.
// 두 번째 노드를 할당하고 데이터를 설정합니다.
secondNode = (Node*)malloc(sizeof(Node)); // 메모리를 동적으로 할당합니다.
if (secondNode == NULL)
{
printf("두 번째 노드에 대한 메모리 할당 실패.\n");
return -1;
}
secondNode->data = 2; // 두 번째 노드의 데이터 값을 설정합니다.
// 세 번째 노드를 할당하고 데이터를 설정합니다.
thirdNode = (Node*)malloc(sizeof(Node)); // 메모리를 동적으로 할당합니다.
if (thirdNode == NULL)
{
printf("세 번째 노드에 대한 메모리 할당 실패.\n");
return -1;
}
thirdNode->data = 3; // 세 번째 노드의 데이터 값을 설정합니다.
// 노드를 연결합니다.
firstNode->next = secondNode; // 첫 번째 노드가 두 번째 노드를 가리키게 합니다.
secondNode->next = thirdNode; // 두 번째 노드가 세 번째 노드를 가리키게 합니다.
thirdNode->next = NULL; // 세 번째 노드가 마지막이므로, next는 NULL로 설정합니다.
// 링크드 리스트의 노드를 출력합니다.
Node* node = firstNode; // 첫 번째 노드에서 시작합니다.
while (node != NULL) // 노드가 NULL이 될 때까지(리스트의 끝) 반복합니다.
{
printf("%d\n", node->data); // 현재 노드의 데이터를 출력합니다.
node = node->next; // 다음 노드로 이동합니다.
}
// 링크드 리스트의 메모리를 해제합니다.
free(firstNode); // 첫 번째 노드의 메모리를 해제합니다.
free(secondNode); // 두 번째 노드의 메모리를 해제합니다.
free(thirdNode); // 세 번째 노드의 메모리를 해제합니다.
return 0;
}
1
2
3
위의 코드에서, Node* firstNode, Node* secondNode, Node* thirdNode 각각에 메모리를 동적으로 할당하여 첫 번째, 두 번째, 세 번째 노드를 생성합니다. 이때 각 노드의 데이터 부분에는 각각 1, 2, 3이라는 값이 저장됩니다.
그 다음에는 노드들을 연결합니다. firstNode->next는 secondNode를 가리키고, secondNode->next는 thirdNode를 가리킵니다. thirdNode는 리스트의 마지막 노드이므로, thirdNode->next는 NULL로 설정합니다.
마지막 부분에서는 링크드 리스트의 각 노드를 순회하며 노드의 데이터를 출력합니다. 순회는 firstNode에서 시작하여 node->next가 NULL이 될 때까지, 즉 리스트의 끝까지 이어집니다. 이 과정에서 각 노드의 데이터를 출력하게 됩니다.
이렇게 하면 세 개의 노드를 갖는 단일 연결 리스트가 완성됩니다. 이러한 단계를 반복하면 더 많은 노드를 갖는 리스트를 생성할 수 있습니다.
3. 정수 저장을 위한 링크드 리스트 사용하기
링크드 리스트는 노드들이 연결되어 있는 데이터 구조로, 배열과 달리 동적 메모리 할당을 사용해 데이터를 추가하거나 삭제하는 것이 가능합니다. 이는 데이터 크기가 변동성이 크거나 예측이 불가능한 경우에 유용하게 쓰입니다.
이번 예제에서는 링크드 리스트를 활용해 사용자로부터 입력받은 정수를 저장하고 출력하는 프로그램을 작성해보겠습니다. 해당 코드는 linked_list.c 파일에 작성되어 있습니다.
코드: linked_list.c
#define _CRT_SECURE_NO_WARNINGS // Visual Studio에서 안전하지 않은 함수 경고를 무시하도록 함
#include <stdio.h>
#include <stdlib.h>
// 노드 구조체 정의
typedef struct Node
{
int data; // 노드에 저장되는 정수 데이터
struct Node* next; // 다음 노드를 가리키는 포인터
} Node;
int main(void)
{
Node* head = NULL; // 연결 리스트의 헤드 노드 초기화
Node* new_node; // 새 노드 포인터 선언
Node* temp; // 임시 노드 포인터 선언
int num;
printf("정수를 입력하세요(0을 입력하면 종료): ");
while (scanf("%d", &num) && num != 0) // 0이 입력될 때까지 정수를 입력받음
{
// 새 노드 생성 및 초기화
new_node = (Node*)malloc(sizeof(Node));
if (new_node == NULL) // malloc이 NULL을 반환한 경우 예외 처리
{
printf("메모리 할당 실패\n");
return 1; // 메모리 할당에 실패했으므로 비정상 종료
}
new_node->data = num;
new_node->next = NULL;
// 연결 리스트에 새 노드 추가
if (head == NULL)
{
head = new_node; // 헤드 노드가 비어 있는 경우, 새 노드를 헤드 노드로 설정
}
else
{
// 헤드 노드부터 시작하여 노드를 순회하며 마지막 노드를 찾음
temp = head;
while (temp->next != NULL)
{
temp = temp->next;
}
temp->next = new_node; // 마지막 노드의 다음 노드로 새 노드 설정
}
printf("정수를 입력하세요(0을 입력하면 종료): ");
}
// 입력된 정수 출력
printf("입력된 정수 출력: ");
temp = head;
while (temp != NULL)
{
printf("%d ", temp->data); // 현재 노드의 데이터 출력
temp = temp->next; // 다음 노드로 이동
}
printf("\n");
// 연결 리스트의 메모리 해제
while (head != NULL)
{
temp = head; // 임시 포인터에 헤드 노드의 주소 저장
head = head->next; // 헤드 노드를 다음 노드로 이동
free(temp); // 임시 포인터가 가리키는 노드 메모리 해제
}
return 0;
}
정수를 입력하세요(0을 입력하면 종료): 1
정수를 입력하세요(0을 입력하면 종료): 2
정수를 입력하세요(0을 입력하면 종료): 3
정수를 입력하세요(0을 입력하면 종료): 0
입력된 정수 출력: 1 2 3
이 프로그램은 먼저 노드 구조체를 정의합니다. 이 노드 구조체는 정수 데이터와 다음 노드를 가리키는 포인터로 이루어져 있습니다. 또한, 연결 리스트의 헤드 노드를 초기화하며, 새 노드와 임시 노드의 포인터를 선언합니다.
프로그램은 사용자로부터 정수를 입력받습니다. 사용자가 0을 입력할 때까지 이 과정이 반복됩니다. 입력받은 정수는 새 노드를 생성하고 초기화하는 데 사용됩니다. 동적 메모리 할당을 통해 이 새 노드를 생성하며, 그 데이터 부분에는 입력받은 정수가 저장됩니다.
헤드 노드가 비어 있을 경우, 새로 생성한 노드가 헤드 노드가 됩니다. 만약 헤드 노드가 이미 존재하는 경우, 마지막 노드를 찾기 위해 헤드 노드부터 시작하여 리스트를 순회합니다. 그리고 마지막 노드의 '다음 노드' 포인터로 새 노드를 설정합니다.
이후, 입력받은 정수들을 출력하기 위해 헤드 노드부터 시작하여 리스트를 순회하며 각 노드의 데이터를 출력합니다. 마지막으로, 프로그램은 헤드 노드부터 시작하여 각 노드의 메모리를 해제하며, 리스트를 순회합니다.
이 예제를 통해, 사용자로부터 입력받은 정수를 저장하고 출력하는 데 링크드 리스트를 어떻게 활용할 수 있는지 살펴보았습니다. 링크드 리스트는 데이터 크기가 불규칙하거나 예측이 불가능한 경우에도 유연한 데이터 구조를 제공합니다.
4. 단일 연결 리스트의 예제
이 예제에서는 함수를 사용하여 단일 연결 리스트를 사용하여 정수를 저장하고 출력하는 방법을 알아보겠습니다.
코드: linked_list_example.c
#include <stdio.h>
#include <stdlib.h>
// 링크드 리스트의 노드를 표현하는 구조체
struct Node
{
int data;
struct Node* next;
};
// 주어진 데이터로 새 노드를 생성
struct Node* create_new_node(int data)
{
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
// 메모리 할당 확인
if (new_node == NULL)
{
printf("메모리 할당에 실패하였습니다.\n");
exit(0);
}
new_node->data = data; // 데이터 할당
new_node->next = NULL; // 다음 노드를 NULL로 설정
return new_node;
}
// 링크드 리스트의 모든 노드를 순회하며 데이터를 출력
void print_list(struct Node* n)
{
while (n != NULL)
{
printf("%d\n", n->data);
n = n->next;
}
}
// 프로그램의 진입점인 main 함수
int main(void)
{
struct Node* head = NULL;
struct Node* second = NULL;
struct Node* third = NULL;
// 노드 생성
head = create_new_node(1);
second = create_new_node(2);
third = create_new_node(3);
// 노드 연결
head->next = second;
second->next = third;
// 리스트 출력
printf("링크드 리스트의 내용:\n");
print_list(head);
// 메모리 해제
free(third);
free(second);
free(head);
return 0;
}
링크드 리스트의 내용:
1
2
3
위의 코드는 정수를 저장하고 출력하는 단일 연결 리스트의 예제입니다. create_new_node 함수는 주어진 데이터로 새로운 노드를 생성하는 역할을 합니다. 이 함수는 메모리 할당을 확인하고 데이터와 다음 노드를 설정한 후, 새로운 노드의 포인터를 반환합니다.
print_list 함수는 리스트의 모든 노드를 순회하며 데이터를 출력합니다. 주어진 노드부터 리스트의 끝까지 반복하여 각 노드의 데이터를 출력합니다.
main 함수에서는 세 개의 노드를 생성하고 이를 연결하여 단일 연결 리스트를 만듭니다. 각 노드에는 순서대로 1, 2, 3이라는 정수 데이터가 저장됩니다. 마지막으로 print_list 함수를 사용하여 리스트의 내용을 출력하고, 메모리를 해제합니다.
이 예제를 통해 단일 연결 리스트의 기본 개념과 메모리 관리의 중요성을 이해할 수 있습니다. 메모리를 할당하고 해제하는 과정을 적절하게 다루어 안정적인 프로그램을 작성할 수 있습니다.
5. 링크드 리스트의 구현과 활용: 노드의 생성, 삽입, 삭제
이번에는 링크드 리스트에 노드를 생성, 삽입, 삭제하는 함수를 만들고 사용해보겠습니다.
코드: linked_list_extended.c
#include <stdio.h>
#include <stdlib.h>
// typedef를 사용해 struct Node를 Node로 선언
typedef struct Node
{
int data;
struct Node* next;
} Node;
// create_node(): 노드를 생성하는 함수
Node* create_node(int data)
{
Node* new_node = (Node*)malloc(sizeof(Node));
// 메모리 할당 실패시 오류 메시지 출력 후 종료
if (new_node == NULL)
{
printf("메모리 할당 실패\n");
exit(0);
}
new_node->data = data; // 노드에 데이터 할당
new_node->next = NULL; // 다음 노드를 NULL로 설정
return new_node;
}
// insert_node(): 노드를 삽입하는 함수
void insert_node(Node** head_ref, int new_data)
{
// 새 노드 생성
Node* new_node = create_node(new_data);
// 새 노드를 리스트의 맨 앞에 삽입
new_node->next = *head_ref;
*head_ref = new_node;
}
// remove_node(): 노드를 삭제하는 함수
void remove_node(Node** head_ref, int key)
{
Node* temp = *head_ref;
Node* prev = NULL;
// 키가 헤드 노드의 데이터와 일치하는 경우
if (temp != NULL && temp->data == key)
{
*head_ref = temp->next;
free(temp);
return;
}
// 키와 일치하는 노드를 찾기 위해 리스트 순회
while (temp != NULL && temp->data != key)
{
prev = temp;
temp = temp->next;
}
// 키를 찾지 못한 경우
if (temp == NULL)
{
printf("주어진 키를 가진 노드를 찾지 못했습니다\n");
return;
}
// 노드 삭제
prev->next = temp->next;
free(temp);
}
// print_node(): 리스트의 모든 노드를 출력하는 함수
void print_node(Node* node)
{
while (node != NULL)
{
printf("%d\n", node->data);
node = node->next;
}
}
int main(void)
{
Node* head = NULL;
insert_node(&head, 1); // 노드 삽입
insert_node(&head, 2); // 노드 삽입
insert_node(&head, 3); // 노드 삽입
printf("초기 링크드 리스트: \n");
print_node(head); // 리스트 출력
remove_node(&head, 2); // 노드 삭제
printf("노드 삭제 후 링크드 리스트: \n");
print_node(head); // 리스트 출력
return 0;
}
초기 링크드 리스트:
3
2
1
노드 삭제 후 링크드 리스트:
3
1
typedef를 이용해 struct Node를 Node라는 이름으로 간단하게 사용할 수 있도록 하였습니다. 먼저 create_node() 함수를 통해 노드를 생성하고, insert_node() 함수를 이용해 리스트에 노드를 추가합니다. remove_node() 함수를 사용해 특정 값을 가진 노드를 삭제할 수 있으며, print_node() 함수를 통해 현재 리스트에 있는 모든 노드를 출력할 수 있습니다. 이런 방식으로 링크드 리스트는 동적으로 데이터를 관리하면서 효율적인 메모리 사용이 가능합니다.
6. 심사문제: 단일 연결 리스트 구현하기
이번 심사 문제에서는 단일 연결 리스트를 이용하여 직원 관리 시스템을 만들어봅시다.
시스템은 4개의 직원 정보를 표준 입력으로 받아 연결 리스트에 저장합니다. 그 중, 3번째로 입력된 노드를 삭제하는 기능을 구현해야 합니다. 이를 위해 delete_employee 함수를 완성해야 합니다. 단, 입력되는 직원의 id 값은 각각 유일해야 합니다.
테스트 케이스 예제
표준입력:
1 AAAA
2 BBBB
3 CCCC
4 DDDD
표준 출력:
ID: 4, Name: DDDD
ID: 3, Name: CCCC
ID: 2, Name: BBBB
ID: 1, Name: AAAA
ID: 4, Name: DDDD
ID: 2, Name: BBBB
ID: 1, Name: AAAA
코드: judge_linked_list.c
#define _CRT_SECURE_NO_WARNINGS // Visual Studio에서 안전하지 않은 함수 경고를 무시하도록 함
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// typedef를 사용해 struct Employee를 Employee로 선언
typedef struct Employee
{
int id;
char name[100];
struct Employee* next; // 다음 직원을 가리키는 포인터
} Employee;
// 전역 변수 head를 NULL로 초기화
Employee* head = NULL;
// create_employee(): 직원 노드를 생성하는 함수
Employee* create_employee(int id, char name[])
{
Employee* new_employee = (Employee*)malloc(sizeof(Employee));
// 메모리 할당 실패시 오류 메시지 출력 후 종료
if (new_employee == NULL)
{
printf("메모리 할당 실패\n");
exit(0);
}
new_employee->id = id; // 노드에 ID 할당
strcpy(new_employee->name, name); // 노드에 이름 할당
new_employee->next = NULL; // 다음 직원을 NULL로 설정
return new_employee;
}
// add_employee(): 직원 노드를 삽입하는 함수
void add_employee(int id, char name[])
{
// 새 직원 노드 생성
Employee* new_employee = create_employee(id, name);
// 새 직원 노드를 리스트의 맨 앞에 삽입
new_employee->next = head;
head = new_employee;
}
// print_employee(): 리스트의 모든 직원 노드를 출력하는 함수
void print_employee()
{
Employee* temp = head;
while (temp != NULL)
{
printf("ID: %d, Name: %s\n", temp->id, temp->name);
temp = temp->next;
}
}
// delete_employee(): 직원 노드를 삭제하는 함수
void delete_employee(int id)
{
Employee* temp = head;
Employee* prev = NULL;
// 키가 헤드 노드의 데이터와 일치하는 경우
if (temp != NULL && temp->id == id)
{
head = temp->next;
free(temp);
return;
}
// 키와 일치하는 노드를 찾기 위해 리스트 순회
while (temp != NULL && temp->id != id)
{
prev = temp;
temp = temp->next;
}
// 키를 찾지 못한 경우
if (temp == NULL)
{
printf("주어진 ID를 가진 직원을 찾지 못했습니다\n");
return;
}
// 노드 삭제
prev->next = temp->next;
free(temp);
}
int main(void)
{
int id[4];
char name[4][100];
for (int i = 0; i < 4; i++)
{
scanf("%d %s", &id[i], name[i]);
add_employee(id[i], name[i]);
}
print_employee();
delete_employee(id[2]); // 3번째 입력한 노드 삭제
print_employee();
return 0;
}
정답:
delete_employee 함수는 다음과 같이 작성됩니다.
void delete_employee(int id)
{
Employee* temp = head;
Employee* prev = NULL;
if (temp != NULL && temp->id == id)
{
head = temp->next;
free(temp);
return;
}
while (temp != NULL && temp->id != id)
{
prev = temp;
temp = temp->next;
}
if (temp == NULL)
{
printf("주어진 ID를 가진 직원을 찾지 못했습니다\n");
return;
}
prev->next = temp->next;
free(temp);
}
해설:
먼저, 아래와 같이 직원 정보를 담을 구조체를 선언하고, 관련 함수들을 작성합니다.
typedef struct Employee
{
int id;
char name[100];
struct Employee* next;
} Employee;
Employee* create_employee(int id, char name[]);
void add_employee(int id, char name[]);
void print_employee();
void delete_employee(int id);
이 함수들은 각각 새 직원 노드를 생성하고, 직원 노드를 리스트에 추가하고, 모든 직원 정보를 출력하며, 특정 ID를 가진 직원을 삭제하는 기능을 수행합니다.
다음으로, main() 함수에서 실제로 이러한 함수들을 활용하여 리스트에 노드를 추가하고 출력하고 삭제하는 동작을 실행합니다.
int main(void)
{
int id[4];
char name[4][100];
for (int i = 0; i < 4; i++)
{
scanf("%d %s", &id[i], name[i]);
add_employee(id[i], name[i]);
}
print_employee();
delete_employee(id[2]); // 3번째 입력한 노드 삭제
print_employee();
return 0;
}
위의 코드를 실행하면, 먼저 4명의 직원 정보를 입력받아 연결 리스트에 추가합니다. 그 다음, 리스트에 저장된 모든 직원 정보를 출력하고, 3번째로 입력된 직원 정보를 삭제한 후에 다시 모든 직원 정보를 출력합니다.
전체 소스코드는 아래와 같습니다.
코드: judge_linked_list.c
(생략: 위 소스 코드와 동일)
이제 아래와 같이 테스트를 해보겠습니다.
1 AAAA
2 BBBB
3 CCCC
4 DDDD
ID: 4, Name: DDDD
ID: 3, Name: CCCC
ID: 2, Name: BBBB
ID: 1, Name: AAAA
ID: 4, Name: DDDD
ID: 2, Name: BBBB
ID: 1, Name: AAAA
위의 프로그램을 실행해보면, 입력한 순서와 반대로 직원 정보가 출력되는 것을 확인할 수 있습니다. 이는 새로운 노드가 항상 리스트의 맨 앞에 추가되기 때문입니다. 또한, delete_employee() 함수를 통해 3번째로 입력한 직원이 제거된 것을 확인할 수 있습니다.
이렇게 연결 리스트를 활용하여 직원 관리 시스템을 구현해 보았습니다. 연결 리스트는 동적으로 데이터를 관리하면서 메모리 사용을 효율적으로 할 수 있습니다.