이현구의 공부방

[자료구조] C언어 Linked List 주소록 만들기 본문

C언어를해보자/기본기

[자료구조] C언어 Linked List 주소록 만들기

이현구 2023. 3. 14. 11:10

자료구조에 대표적인 단방향 링크드 리스트를 만들어 보겠습니다.

 

링크드 리스트는 위의 그림과 같이 노드가 다음 노드를 가르켜 서로 연결된 형태입니다.  때문에 list라고 불립니다.

그렇다면 리스트도 데이터들이 순차적으로 연결되고 배열도 데이터들을 순차적으로 연결되어있다고 볼수 있을텐데요.

 

배열과 Linked List는 아래와 같은 공통점이 있습니다.

  • 공통점
    • 데이터 순서를 유지한다. 
    • 특정 인덱스나 데이터 위치를 빠르게 접근할 수 있다.
    • 메모리를 효율적으로 사용할 수 있다.

 

배열과 Linked List는 구현방식이 다르며, 동작 방식에도 차이가 있습니다.

 

배열의 경우 연속된 메모리 공간에 데이터를 저장하고 데이터에 접근을 하기 위해 인덱스를 사용하여 접근합니다.

 

Linked List의 경우는 메모리 공간의 어느 위치에든 저장 될 수 있습니다.
배열과 달리 데이터 추가, 삭제 등이 용이하고 동적으로 크기 변경이 가능합니다.

 

1. 구조체 정의

typedef struct Data {
	int index;
	char name[15];
	char phone[18];
	char address[50];

	struct Data *link;
}data;

 

C언어에는 구조체(struct)라는게 있습니다. 

구조체는 여러 데이터(변수)를 하나로 묶어서 새로운 타입으로 정의하여 사용하는 데이터 집합체 입니다.

 

위의 코드에서도 주소록의 데이터를 담고 있는 Data 타입으로 struct 를 만들었고 그안에 사용할 데이터들을
선언하였습니다.

  • index : 주소록 데이터의 번호 
  • name : 이름
  • phone : 전화번호
  • address : 주소 
  • link : 포인터는 주소를 저장하는 타입입니다. 여기서 link는 노드의 주소를 저장하는 것으로 사용됩니다. 
    struct Data 타입의 데이터의 주소를 담는것으로 이해하시면 됩니다. 

2. main 문

void main()
{
	data *head = (data*)malloc(sizeof(data));
	int choice;

	initdata(head);

	do {
		printf("\n\n");
		printf("****** 주소록 ******\n\n\n");
		printf("--------------------\n\n");
		printf("현재 등록된 주소의 수 %d", data_count);
		printf("\n\n--------------------\n\n");

		printf("1. 추가 \n\n");
		printf("2. 보기 \n\n");
		printf("3. 삭제 \n\n");
		printf("4. 검색 \n\n");
		printf("5. 종료 \n\n");

		printf("\n 입력 : ");
		choice = getchar();

		while (getchar() != '\n');

		fflush(stdin);

		printf("\n\n");
		switch (choice)
		{
		case '1':
			if (addData(head)){
			printf("\n\n성공\n\n");
			}
			else
			{
				printf("\n\n실패\n\n");
			}
			break;
		case '2':
			Display(head);
			break;
		case '3':
			DeleteData(head);
			break;
		case '4':
			SearchData(head);
			break;
		case '5':
			printf("종료\n");
			break;
		default:
			printf("잘못입력 \n");
			break;
		}
	} while (choice != '5');
}

Linked List는 노드가 노드와 연결되어 있기때문에 첫번째 노드를 가리키는 용도로 head를 만들어 줍니다.

 

head를 동적할당하여 만들게 되면  아래와 같이 head 노드 하나가 생성 된 것입니다.

 

 

 

head는 데이터를 담지 않고 첫번째 노드만을 가리키는 용도로 사용됩니다.

그 이유는 노드 삽입, 삭제, 검색등을 수행할 때 효율적인 처리를 위함입니다.

 

 

3. 노드 삽입

bool addData(data *ptr)
{
	while (ptr->link != NULL)
		ptr = ptr->link;

	ptr->link = (data*)malloc(sizeof(data));

	if (ptr->link == NULL)
	{
		printf("\n\n 시스템 메모리 부족으로 인하여 추가 작업이 실패하였습니다. \n\n");
		return false;
	}

....

노드를 추가하는 함수입니다.

main에서 전달된 head를 매개변수로 받아 처리하게 됩니다.

 

while문은 head에 link가  null 인지 아닌지 체크를 해서 null이 아니면 다음 노드로 넘어가 결국 맨 끝에 노드로 가기 위한 

로직입니다.

 

ptr->link = (data*)malloc(sizeof(data)) 은 맨끝 노드의 Link (다음노드)에 동적할당으로 노드를 생성하게 되고 

동적할당이 실패되면 작업 실패를 return 하게 됩니다.

 

만약 head만 존재하고 다른 노드가 없다면, head의 link 포인터 변수에 동적할당을 하여 노드를 생성하게 되는 것입니다.

 

4. List 출력

void Display(data *ptr)
{
	ptr = ptr->link;
	printf("****** 보기 ******\n\n\n");

	while (ptr != NULL)
	{
		printf("\n---------------------------------\n");
		printf("\n\n");
		printf("데이터 번호 : %d", ptr->index);
		printf("\n\n");
		printf(" 이름 : ");
		printf("%-s", ptr->name);
		printf("\n\n 전화 번호 :");
		printf("%-s", ptr->phone);
		printf("\n\n 주소 : ");
		printf("%-s", ptr->address);
		printf("\n\n");
		printf("\n---------------------------------\n");

		ptr = ptr->link;

		printf("\n");
	}

	printf("\n");
}

연결된 노드들을 보는 함수입니다.

head를 넘겨 받고 head에는 데이터를 저장하지 않고 오로지 첫번째 노드만을 가리키고 있기 때문에

ptr = ptr->link; 코드를 통해 head에 다음 노드로 이동 한 후,  while문을 통하여 연결된 노드들의 데이터들을 표출합니다.

 

 

5. 노드 삭제

void DeleteData(data *ptr)
{
	data *temp = NULL;
	char name[15];
	printf("****** 삭제 ******\n\n\n");
	printf("삭제 할 사람의 이름 : ");
	fgets(name, sizeof(name), stdin);
	name[strlen(name) - 1] = '\0';

	while (ptr->link != NULL)
	{
		temp = ptr;
		ptr = ptr->link;

		if (strcmp(name, ptr->name) == 0)
		{
			temp->link = ptr->link;
			free(ptr);

			printf("\n\n삭제 완료\n");
			data_count = data_count - 1;
			break;
		}

		if (ptr->link == NULL)
		{
			printf("\n %s로 등록된 데이터가 없습니다.\n", name);
		}
	}

	return;
}

노드 삭제 함수 입니다.

삭제는 여러 동작으로 구현 할 수 있습니다. 예를 들어 맨 첫번째 노드부터 삭제, 맨뒤에 노드를 삭제, 데이터를 입력하여

해당 데이터를 찾아서 삭제 등 설계하는 사람 마음대로 삭제 구현 할 수 있습니다.

 

저의 경우는 이름을 입력받아 해당 노드를 찾고 삭제하도록 구현하였습니다.

 

temp 포인터 변수는 삭제하는 노드의 이전 노드를 저장하고 있는 변수입니다.

아래 그림을 보면 temp에서 ptr 노드를 가리키는 것을 ptr->link를 가리키도록 되어있습니다.

그 후 삭제 시켜야하는 ptr 노드를 메모리 해제를 하였습니다.

 

6. 노드 검색

노드 검색은 삭제와 마찬가지로 검색할 키워드를 입력 받고 해당 노드를 찾는 함수입니다.

단방향 링크의 경우 원하는 데이터를 찾기 위해서는 수많은 노드들을 거쳐야합니다. 만약 1000개의 노드가 있고

아쉽게도 997 번째 노드를 삭제해야한다면 996번의 노드를 거쳐야 합니다.

때문에 연결 리스트가 커질수록 삭제 연산 및 검색 연산의 시간 복잡도가 증가 하게 되므로 효율적이지 못합니다.

때문에 index와 hash table등을 이용하는 효율적인 연산을 하도록 구현 할 수 있습니다.

 

 

7. 전체 코드

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

unsigned int data_count = 0;
unsigned int data_index = 0;

typedef struct Data {
	int index;
	char name[15];
	char phone[18];
	char address[50];

	struct Data *link;
}data;

void initdata(data *ptr)
{
	ptr->index = 0;
	strcpy_s(ptr->name, sizeof(ptr->name),"");
	strcpy_s(ptr->phone, sizeof(ptr->phone),"");
	strcpy_s(ptr->address, sizeof(ptr->address),"");
	ptr->link = NULL;
}

bool addData(data *ptr)
{
	while (ptr->link != NULL)
		ptr = ptr->link;

	ptr->link = (data*)malloc(sizeof(data));

	if (ptr->link == NULL)
	{
		printf("\n\n 시스템 메모리 부족으로 인하여 추가 작업이 실패하였습니다. \n\n");
		return false;
	}

	ptr = ptr->link;

	printf("****** 추가 ******\n\n\n");

	printf("이름 입력 : ");
	fgets(ptr->name, sizeof(ptr->name), stdin);
	ptr->name[strlen(ptr->name) - 1] = '\0';

	printf("전화번호 입력 :");
	fgets(ptr->phone, sizeof(ptr->phone), stdin);
	ptr->phone[strlen(ptr->phone) - 1] = '\0';

	printf("주소입력 :");
	fgets(ptr->address, sizeof(ptr->address), stdin);
	ptr->address[strlen(ptr->address) - 1] = '\0';

	ptr->link = NULL;

	data_count = data_count + 1;
	data_index = data_index + 1;
	ptr->index = data_index;

	return true;
}

void Display(data *ptr)
{
	ptr = ptr->link;
	printf("****** 보기 ******\n\n\n");

	while (ptr != NULL)
	{
		printf("\n---------------------------------\n");
		printf("\n\n");
		printf("데이터 번호 : %d", ptr->index);
		printf("\n\n");
		printf(" 이름 : ");
		printf("%-s", ptr->name);
		printf("\n\n 전화 번호 :");
		printf("%-s", ptr->phone);
		printf("\n\n 주소 : ");
		printf("%-s", ptr->address);
		printf("\n\n");
		printf("\n---------------------------------\n");

		ptr = ptr->link;

		printf("\n");
	}

	printf("\n");
}

void SearchData(data *ptr)
{
	char name[15];
	printf("****** 검색 ******\n\n\n");

	printf("검색할 사람의 이름 : ");
	fgets(name, sizeof(name), stdin);
	name[strlen(name) - 1] = '\0';

	while (ptr->link != NULL)
	{
		ptr = ptr->link;

		if (strcmp(ptr->name, name) == 0)
		{
			printf("\n ---- 검색 결과 ---- \n\n");
			printf("이름 : %s", ptr->name);
			printf("\n\n");
			printf("전화번호 : %s", ptr->phone);
			printf("\n\n");
			printf("주소 : %s", ptr->address);
			printf("\n\n");
			printf("-------------------------------------");
			printf("\n\n");
			break;
		}

		if (ptr->link == NULL)
		{
			printf("\n %s로 등록된 데이터가 없습니다.\n", name);
		}
	}

	return;
}

void DeleteData(data *ptr)
{
	data *temp = NULL;
	char name[15];
	printf("****** 삭제 ******\n\n\n");
	printf("삭제 할 사람의 이름 : ");
	fgets(name, sizeof(name), stdin);
	name[strlen(name) - 1] = '\0';

	while (ptr->link != NULL)
	{
		temp = ptr;
		ptr = ptr->link;

		if (strcmp(name, ptr->name) == 0)
		{
			temp->link = ptr->link;
			free(ptr);

			printf("\n\n삭제 완료\n");
			data_count = data_count - 1;
			break;
		}

		if (ptr->link == NULL)
		{
			printf("\n %s로 등록된 데이터가 없습니다.\n", name);
		}
	}

	return;
}


void main()
{
	data *head = (data*)malloc(sizeof(data));
	int choice;

	initdata(head);

	do {
		printf("\n\n");
		printf("****** 주소록 ******\n\n\n");
		printf("--------------------\n\n");
		printf("현재 등록된 주소의 수 %d", data_count);
		printf("\n\n--------------------\n\n");

		printf("1. 추가 \n\n");
		printf("2. 보기 \n\n");
		printf("3. 삭제 \n\n");
		printf("4. 검색 \n\n");
		printf("5. 종료 \n\n");

		printf("\n 입력 : ");
		choice = getchar();

		while (getchar() != '\n');

		fflush(stdin);

		printf("\n\n");
		switch (choice)
		{
		case '1':
			if (addData(head)){
			printf("\n\n성공\n\n");
			}
			else
			{
				printf("\n\n실패\n\n");
			}
			break;
		case '2':
			Display(head);
			break;
		case '3':
			DeleteData(head);
			break;
		case '4':
			SearchData(head);
			break;
		case '5':
			printf("종료\n");
			break;
		default:
			printf("잘못입력 \n");
			break;
		}
	} while (choice != '5');
}

 

잘못된 정보나 수정이 필요한 내용이 있다면 댓글 주시면 감사합니다 :)

Comments