컴퓨터/C
자료구조인 List의 개념이 익숙하지 않거나 모르신다면 개념을 익히고 보는 것을 추천드립니다.
본문에서는 연결 리스트 자료구조를 C언어를 통해 구현해보도록 하겠습니다.
C언에 문법을 가지고 크게 아래와 같은 기능을 사용하여 구현할 예정입니다.
우선 C언어의 구조체를 이용하여 Node를 만들어 보도록 하겠습니다.
Node에는 관리할 데이터와 다음 노트의 위치정보를 알려줄 두 가지가 필요합니다.
우선 담을 데이터를 만들어야 되기 때문에 이름과 나이를 저장할 수 있는 구조체 하나를 정의하겠습니다.
//Data의 구조체 정의
typedef struct _Data
{
char name[100];
int age;
}DATA,Data;
이제 데이터를 정의했으니 데이터와 위지 정보를 담을 수 있는 Node 구조체를 정의하겠습니다.
//다음 노드의 위치 정보를 알수 있는 Node 구조체 정의
typedef struct _Node
{
Data* data;
struct _Node* next_node;
}NODE,Node;
Node 구조체 안의 변수들은 동적 메모리 할당을 통해 이용함으로 포인터 변수를 이용했습니다.
위처럼 선언된 구조체 안에 동일한 타입의 자료가 들어가는 것 또한 가능합니다.
싱글링크 리스트는 각각의 노드들이 연결되어 있는 구조입니다. 그렇다면 각각의 노드를 구현하기 위해 함수를 하나 만들어 봅시다.
// 노드 생성 함수 반환 값 : 노드의 포인터 값
// 인자 : Data구조체의 이름과 나이
Node* CreateNode(char* name,int age) {
Node* newNode = (Node*)malloc(sizeof(Node)); // 노드 동적 할당
newNode->data = (Data*)malloc(sizeof(Data)); // 노드 안의 데이터 동적 할당
newNode->next_node = NULL; // 다음 노드는 아직 존재하지 않음으로 NULL 로 초기화
strcpy(newNode->data->name, name); // 인자 이름을 문자열 복사 함수로 저장
newNode->data->age = age; // 인자 나이를 저장
return newNode; // 생성된 포인터 타입의 노드를 반환
}
위의 함수처럼 노드를 생성하고 반환하는 함수를 만들었습니다. 이제 메인 문에서 한번 첫 번째 노드를 실행해 봅시다.
int main() {
// 처음 노드를 생성 및 데이터 주입
Node* List = CreateNode( "홍길동", 24);
printf("%s\n", List->data->name);
printf("%d\n", List->data->age);
return 0;
}
음 일단 싱글 리스트를 구현하는 가장 첫 번째 노드를 완성하고 실행해 봤습니다. 잘 작동하는 것 같습니다.
이제 가장 마지막 노드에 이어 붙이기 위한 구현을 한번 해보도록 하겠습니다.
우리가 생성한 첫 번째 노드 안에 값은 지금 다음과 같이 되어있습니다
이어 붙이기 (Append)를 하기 위해서 우리가 만든 List(싱글 링크드 리스트 첫 번째) 변수로부터 계속해서 next_node를 추가해 나가면 됩니다.
추가해 나가기 위해 추가할 List의 값 그리고 데이터인 이름과 나이를 인자로 하는 함수를 구현해 보도록 하겠습니다.
// 이어붙이기 구현 반환값 : 없음
// 함수 인자 : 이어 붙일 리스트 , 데이터의 이름 , 나이
// 이어붙일 리스트의 경우 포인터로 선언되어있어 2차 포인터를 이용하여 받아옴
void AppendNode(Node** List,char* name, int age) {
//만약 받아온 포인터가 값이 없다면 처음 노드를 생성하기위해 진행
if ((*List) == NULL) {
List = CreateNode(name, age);
}
//만약 받아온 포인터의 값이 있다면 마지막 노드를 찾기위해 탐색
else {
// 탐색하기 위한 임시 변수 생성 및 가지고온 List의 시작 노드 대입
Node* Node_tail = (*List);
while (Node_tail->next_node != NULL) {
// 계속해서 이어진 노드가 NULL이 될때까지 탐색
Node_tail = Node_tail->next_node;
}
// 탐색이 완료됬다면 마지막 노드의 next_node가 NULL에게 새로운 노드 부여
Node_tail->next_node = CreateNode(name, age);
}
}
기존에 만든 Node 생성 함수와 혼합하여 생성하는 연결 리스트에 가장 마지막에 노드를 추가 생성할 수 있도록 구현했습니다.
메인 함수 안에서 실행과 결과를 확인해 보겠습니다.
int main() {
Node* List = CreateNode( "홍길동", 24); // 싱글링크리스트의 첫번쨰 노드 생성
AppendNode(&List, "이순신", 28); // 2번째 노드 생성
AppendNode(&List, "허준", 38); // 3번째 노드 생성
// 임시 변수와 while문을 활용해서 싱글 링크드 리스트 출력해보기
Node* Temp = List;
while (1) {
printf("%s\n", Temp->data->name);
printf("%d\n", Temp->data->age);
Temp = Temp->next_node;
if (Temp == NULL) break;
}
return 0;
}
잘 이어지고 있는 것이 확인됩니다. 전체 출력 또한 함수화 해보도록 하겠습니다.
void PrintListAll(Node** List) {
Node* Temp = (*List);
while (1) {
printf("%s\n", Temp->data->name);
printf("%d\n", Temp->data->age);
Temp = Temp->next_node;
if (Temp == NULL) break;
}
}
이제 리스트를 만들어서 특정 위치에 데이터를 삽입 또는 삭제를 하려면 우선 리스트의 전체 길이를 알아야 될 것입니다. 전체 길이를 알아보는 함수를 만들어 보도록 하겠습니다.
// 리스트의 길이를 반환하는 함수
int ListLength(Node** List) {
int count = 0;
Node* Temp = (*List);
while (1) {
count++;
Temp = Temp->next_node;
if (Temp == NULL) break;
}
return count;
}
int main() {
Node* List = CreateNode( "홍길동", 24); // 싱글링크리스트의 첫번쨰 노드 생성
AppendNode(&List, "이순신", 28); // 2번째 노드 생성
AppendNode(&List, "허준", 38); // 3번째 노드 생성
printf("리스트의 전체 길이 : %d\n", ListLength(&List));
PrintListAll(&List);
return 0;
}
잘 동작하는 것을 확인할 수 있었습니다. 이제 길이를 확인할 수 있으니 특정 위치에 값을 삽입하는 구현을 해보도록 하겠습니다.
특정위치에 값을 삽입하기 위해서 아래와 같은 기능들이 필요할 것입니다.
함수 구현을 해보도록 합시다.
void InsertNode(Node** List, int pos, char* name, int age) {
// 노드 정보를 받아옴
Node* targetpoint = (*List);
// 노드 정보를 임시로 저장할 공간 마련
Node* temp = NULL;
for (int i = 1; i < pos; i++) {
// 위치만큼 돌면서 삽입할 위치 전단의 노드 정보를 받아옴
targetpoint = targetpoint->next_node;
}
//해당 위치의 노드가 가지고 있는 다음 노드 정보 임시 저장
temp = targetpoint->next_node;
//삽입할 위치의 다음 노드를 새로운 노드 연결
targetpoint->next_node = CreateNode(name, age);
//기존에 있던 노드정보를 삽입한 노드의 뒤에 연결
targetpoint->next_node->next_node = temp;
}
int main() {
Node* List = CreateNode( "홍길동", 24); // 싱글링크리스트의 첫번쨰 노드 생성
AppendNode(&List, "이순신", 28); // 2번째 노드 생성
AppendNode(&List, "허준", 38); // 3번째 노드 생성
InsertNode(&List, 1, "세종대왕", 40);
printf("리스트의 전체 길이 : %d\n", ListLength(&List));
PrintListAll(&List);
return 0;
}
원하는 위치로 접근하여 다음 위치에 연결 리스트를 연결한 것을 확인할 수 있습니다.
void DeleteNode(Node** List, int pos) {
//지울 노드를 찾기위한 변수 저장
Node* targetpoint = (*List);
Node* temp = NULL;
for (int i = 1; i < pos; i++) {
temp = targetpoint;
// 위치만큼 돌면서 삽입할 위치 전단의 노드 정보를 받아옴
targetpoint = targetpoint->next_node;
}
// 지우기 전단의 후단의 노드를 연결
temp->next_node = targetpoint->next_node;
// 지운 노드의 메모리 할당 제거
free(targetpoint->data);
free(targetpoint);
}
int main() {
Node* List = CreateNode("홍길동", 24); // 싱글링크리스트의 첫번쨰 노드 생성
AppendNode(&List, "이순신", 28); // 2번째 노드 생성
AppendNode(&List, "허준", 38); // 3번째 노드 생성
InsertNode(&List, 1, "세종대왕", 40);
DeleteNode(&List, 2);
printf("리스트의 전체 길이 : %d\n", ListLength(&List));
PrintListAll(&List);
return 0;
}
특정 위치의 데이터를 받기 위한 함수를 만들겠습니다.
void Searchindex(Node** List, int index) {
Node* Temp = (*List);
for (int i = 1; i < index; i++) {
Temp = Temp->next_node;
}
printf("리스트 %d번째 노드 데이터의 이름은 %s 나이는 %d입니다.\n", index,Temp->data->name,Temp->data->age);
}
void SearchName(Node** List, char* name) {
Node* Temp = (*List);
int count = 0;
for (int i = 1; i < ListLength(*List); i++) {
if (strcmp(Temp->data->name, name) == 0) {
count = i;
break;
}
Temp = Temp->next_node;
}
printf("%s는 리스트 중 %d번 째에 있습니다.\n", Temp->data->name, count);
}
int main() {
Node* List = CreateNode("홍길동", 24); // 싱글링크리스트의 첫번쨰 노드 생성
AppendNode(&List, "이순신", 28); // 2번째 노드 생성
AppendNode(&List, "허준", 38); // 3번째 노드 생성
InsertNode(&List, 1, "세종대왕", 40);
DeleteNode(&List, 2);
printf("리스트의 전체 길이 : %d\n", ListLength(&List));
PrintListAll(&List);
Searchindex(&List, 3);
SearchName(&List,"홍길동");
return 0;
}
마무리로 전체 소스 코드를 올리며 싱글 링크드 리스트 구현을 마치겠습니다.
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<malloc.h>
#include<string.h>
typedef struct _Data
{
char name[100];
int age;
}DATA, Data;
typedef struct _Node
{
Data* data;
struct _Node* next_node;
}NODE, Node;
// 노드 생성 함수 반환 값 : 노드의 포인터 값
// 인자 : Data구조체의 이름과 나이
Node* CreateNode(char* name, int age) {
Node* newNode = (Node*)malloc(sizeof(Node)); // 노드 동적 할당
newNode->data = (Data*)malloc(sizeof(Data)); // 노드 안의 데이터 동적 할당
newNode->next_node = NULL; // 다음 노드는 아직 존재하지 않음으로 NULL 로 초기화
strcpy(newNode->data->name, name); // 인자 이름을 문자열 복사 함수로 저장
newNode->data->age = age; // 인자 나이를 저장
return newNode; // 생성된 포인터 타입의 노드를 반환
}
void AppendNode(Node** List, char* name, int age) {
if ((*List) == NULL) {
List = CreateNode(name, age);
}
else {
Node* Node_tail = (*List);
while (Node_tail->next_node != NULL) {
Node_tail = Node_tail->next_node;
}
Node_tail->next_node = CreateNode(name, age);
}
}
void InsertNode(Node** List, int pos, char* name, int age) {
// 헤더 노드의 변경시 pos == 0
if (pos == 0) {
Node* temp = (*List);
*List = CreateNode(name, age);
(*List)->next_node = temp;
return 0;
}
// 노드 정보를 받아옴
Node* targetpoint = (*List);
// 노드 정보를 임시로 저장할 공간 마련
Node* temp = NULL;
for (int i = 1; i < pos; i++) {
// 위치만큼 돌면서 삽입할 위치 전단의 노드 정보를 받아옴
targetpoint = targetpoint->next_node;
}
//해당 위치의 노드가 가지고 있는 다음 노드 정보 임시 저장
temp = targetpoint->next_node;
//삽입할 위치의 다음 노드를 새로운 노드 연결
targetpoint->next_node = CreateNode(name, age);
//기존에 있던 노드정보를 삽입한 노드의 뒤에 연결
targetpoint->next_node->next_node = temp;
}
void DeleteNode(Node** List, int pos) {
//지울 노드를 찾기위한 변수 저장
Node* targetpoint = (*List);
Node* temp = NULL;
for (int i = 1; i < pos; i++) {
temp = targetpoint;
// 위치만큼 돌면서 삽입할 위치 전단의 노드 정보를 받아옴
targetpoint = targetpoint->next_node;
}
// 지우기 전단의 후단의 노드를 연결
temp->next_node = targetpoint->next_node;
// 지운 노드의 메모리 할당 제거
free(targetpoint->data);
free(targetpoint);
}
void PrintListAll(Node** List) {
Node* Temp = (*List);
while (1) {
printf("%s\n", Temp->data->name);
printf("%d\n", Temp->data->age);
Temp = Temp->next_node;
if (Temp == NULL) break;
}
}
void Searchindex(Node** List, int index) {
Node* Temp = (*List);
for (int i = 1; i < index; i++) {
Temp = Temp->next_node;
}
printf("리스트 %d번째 노드 데이터의 이름은 %s 나이는 %d입니다.\n", index,Temp->data->name,Temp->data->age);
}
void SearchName(Node** List, char* name) {
Node* Temp = (*List);
int count = 0;
for (int i = 1; i < ListLength(*List); i++) {
if (strcmp(Temp->data->name, name) == 0) {
count = i;
break;
}
Temp = Temp->next_node;
}
printf("%s는 리스트 중 %d번 째에 있습니다.\n", Temp->data->name, count);
}
int ListLength(Node** List) {
int count = 0;
Node* Temp = (*List);
while (1) {
count++;
Temp = Temp->next_node;
if (Temp == NULL) break;
}
return count;
}
int main() {
Node* List = CreateNode("홍길동", 24); // 싱글링크리스트의 첫번쨰 노드 생성
AppendNode(&List, "이순신", 28); // 2번째 노드 생성
AppendNode(&List, "허준", 38); // 3번째 노드 생성
InsertNode(&List, 1, "세종대왕", 40);
DeleteNode(&List, 2);
printf("리스트의 전체 길이 : %d\n", ListLength(&List));
PrintListAll(&List);
Searchindex(&List, 3);
SearchName(&List,"홍길동");
return 0;
}
C 언어 - 거품정렬 구현해보기 (0) | 2021.09.27 |
---|---|
C 언어 - 난수의 생성(랜덤 번호) (0) | 2021.09.19 |
C 언어 - 배열의 한계 (선언과 동시에 크기의 불변) (0) | 2021.09.05 |
C 언어 - 실습 - 학생관리 프로그램Ver.4.2(파일 불러오기) (0) | 2021.08.05 |
C 언어 - 라이브러리 만들어보기 (모사 해보기) (0) | 2021.08.03 |
91년생 공학엔지니어의 개발일지
TODAY :
YESTER DAY :
TOTAL :
Commnet