데이터 구조에 대표적인 단방향 링크 목록을 만듭니다.
링크 목록은 위 그림과 같이 노드가 다음 노드를 가리키도록 서로 연결되어 있는 형식입니다.
그래서 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');
}링크 목록은 노드가 노드와 연관되어 있기 때문에 첫 번째 노드를 가리키기 위해 헤드를 만듭니다.
head 를 동적으로 할당해 작성하면, 다음과 같이 head 노드 1 개가 생성된 것입니다.
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)) 는 터미널 노드 링크(다음 노드)에 동적 할당으로 노드를 생성합니다.
동적 할당이 실패하면 작업 실패를 반환합니다.
만약 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');
}
잘못된 정보와 수정이 필요한 경우 댓글을 달아 주셔서 감사합니다 🙂