C언어 - Single linked list(단일 연결 리스트) 구현해보기

컴퓨터/C

728x90
반응형

시작하기 전에

자료구조인 List의 개념이 익숙하지 않거나 모르신다면 개념을 익히고 보는 것을 추천드립니다.

 

 

자료구조 - List(리스트)와 종류

List 개념 이해하기 자료구조 중 하나인 List는 배열의 한계를 극복할 수 있는 강력한 자료구조 중 하나이며 데이터를 단순하지만 효율적으로 다룰 수 있는 자료구조입니다. List는 Array처럼 어떠한

blog-of-gon.tistory.com

 

C 언어를 이용한 싱글 링크드 리스트를 구현해보자

본문에서는 연결 리스트 자료구조를 C언어를 통해 구현해보도록 하겠습니다. 

C언에 문법을 가지고 크게 아래와 같은 기능을 사용하여 구현할 예정입니다.

  • 노드 구현 - 구조체를 이용하여 만든다
  • 노드 안의 위치 정보 - 포인터를 이용
  • 노드의 생성 - 동적 메모리 할당을 이용
  • 삭제 / 탐색 / 삽입 등 기능 구현 - 함수화를 할 예정 

 

Node 설계하기

우선 C언어의 구조체를 이용하여 Node를 만들어 보도록 하겠습니다. 

Node에는 관리할 데이터와 다음 노트의 위치정보를 알려줄 두 가지가 필요합니다.

 

  • 데이터 구조 만들기

우선 담을 데이터를 만들어야 되기 때문에 이름과 나이를 저장할 수 있는 구조체 하나를 정의하겠습니다.

 

//Data의 구조체 정의
typedef struct _Data
{
	char	name[100];
	int		age;
}DATA,Data;
  • Node 구조 만들기

이제 데이터를 정의했으니 데이터와 위지 정보를 담을 수 있는 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;
}

음 일단 싱글 리스트를 구현하는 가장 첫 번째 노드를 완성하고 실행해 봤습니다. 잘 작동하는 것 같습니다. 

이제 가장 마지막 노드에 이어 붙이기 위한 구현을 한번 해보도록 하겠습니다.

 

  • 이어 붙이기 기능 구현하기

우리가 생성한 첫 번째 노드 안에 값은 지금 다음과 같이 되어있습니다

  • List->data->name = 홍길동
  • List->data->age   =  24
  • List->next_node = NULL;

이어 붙이기 (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;
}

잘 동작하는 것을 확인할 수 있었습니다. 이제 길이를 확인할 수 있으니 특정 위치에 값을 삽입하는 구현을 해보도록 하겠습니다.

 

  • 특정 위치에 값 삽입 구현하기 (Insert)

특정위치에 값을 삽입하기 위해서 아래와 같은 기능들이 필요할 것입니다.

  • 특정 위치의 노드에 접근한다.
  • 접근한 노드의 다음 위치 정보를 임시로 저장한다.
  • 접근한 노드 뒤에 새로운 노드를 추가한다.
  • 추가한 노드에 임시로 저장한 다음 노드를 이어준다.

함수 구현을 해보도록 합시다.

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

원하는 위치로 접근하여 다음 위치에 연결 리스트를 연결한 것을 확인할 수 있습니다.

 

  • 특정 위치의 값 지우기 구현하기 (Delete)
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;
}
728x90
반응형

Commnet

G91개발일지

Gon91(지구일)

91년생 공학엔지니어의 개발일지

TODAY :

YESTER DAY :

TOTAL :