6. C/C++ 연결리스트

1. 연결 리스트(Linked List)란

- 각 데이터를 포인터로 연결하여 관리하는 자료구조이다.

- 노드(node) : 각 노드는 데이터를 저장하는 영역을 의미하는 데이터 필드(data field)와 다음 데이터가 저장된 노드를 가리키는 포인터 영역으로 구성된 링크 필드(link field)로 구분된다.

연결리스트 노드

 

2. 연결 리스트의 구조

- 연결 리스트는 첫 번째 노드를 가리키는 헤드 포인터부터 node1 → node2 → node3의 순서로 리스트를 진행한다.

- 연결 리스트는 포인터 영역에 NULL이 저장되어 있는 노드를 만나면 더 이상 연결된 노드가 없음을 의미하므로 연결 리스트 수행을 종료한다.

- 각 노드는 주기억 장치의 어디에 저장되어 있는지는 상관없이 각 노드가 포인터에 연결되어 있기만 하면 된다.

 

- 노드의 데이터 영역에는 한 개의 데이터가 들어 있지만 필요에 따라 여러 개의 데이터를 저장할 수도 있다.

- 아래 그림은 데이터 영역에 성명과 나이 데이터를 저장하는 연결 리스트의 형태를 보여준다.

 

- 연결 리스트의 노드는 메모리의 특정 위치에 저장해야 한다는 제약이 없다.

   < 메모리 공간 어디든지 위치할 수 있음 >

- 연결 리스트의 노드는 리스트의 순서와 동일하게 수행하지 않으므로 메모리에 연속된 공간을 확보하지 않아도 된다.

- 메모리가 필요할 때마다 노드를 동적으로 생성하여 연결하기만 하면 연결 리스트를 손쉽게 사용할 수 있다.

 

3. 자기 참조 구조체

- 연결 리스트와 자기 참조 구조체 

• 연결 리스트를 다루려면 먼저 자기 참조 구조체를 이해해야 합니다
• 자기 참조 구조체 : 구성 멤버 중에서 동일한 타입의 구조체를 가리키는 포인터가 존재하는 구조체이다
• 자기 참조 구조체는 다른 구조체와 쉽게 연결할 수 있습니다.
• 자기 참조 구조체의 선언 형식

자가 참조 구조체

• 프로그램을 구현할 때 항목의 개수를 예측하기 어려우면 자기 참조 구조체를 정의해 놓고 필요에 따라 동적으로 기억 장소를 할당 받으면 됩니다
• 노드를 포인터로 연결하는 자료구조를 구성해 놓으면 중간에 새로운 데이터를 삽입하기가 편리합니다.

 

- 연결 리스트 생성 절차 

• typedef를 이용하여 새로운 자료형으로 정의해서 사용하는 방법이 가장 보편적입니다.
• typedef를 사용하면 struct 키워드를 매번 선언해야 하는 번거로움을 줄일 수 있습니다.

 

- 노드의 구조 정의  

• 자기 참조 구조체를 사용하여 새로운 자료형 NODE를 생성하여 노드의 구조를 정의하기

 

- 노드 생성 

• 노드의 구조를 정의하였다면 노드를 사용할 수 있습니다.
• NODE 타입의 포인터 변수를 선언하고 malloc( ) 함수로 노드의 크기만큼 동적 메모리를 할당받아 사용하려면 다음과 같이 선언합니다.

• 동적 메모리가 1000번지에 할당된다고 가정할 때 노드는 다음 그림과 같이 생성됩니다.

 

- 노드의 데이터 필드와 링크 필드 생성 

• 새롭게 생성된 노드의 데이터 필드에는 데이터 10을 저장하고 링크 필드에는 NULL 값을 설정하기

• 노드의 데이터 필드와 링크 필드에 값을 대입하기

 

- 연결 리스트 생성 

• 여러 개의 노드로 연결된 리스트를 생성하기 위해 노드를 생성한 것과 동일한 방법으로 새로운 노드를 추가로 생성
• p_next 데이터 필드에는 20을 저장하고 링크 필드에는 NULL 값을 설정한 다음 p_head의 링크 필드에는 p_next를 대입하기

 

• 연결 리스트 생성

연결 리스트 생성

 

- 할당된 동적 메모리 반납 

• 연결 리스트 생성 과정을 필요한 수만큼 반복하여 노드 추가합니다.
• 노드를 생성하기 위해 사용한 동적 메모리는 사용이 끝나면 반드시 반납해야 합니다.
• free( ) 함수를 사용하여 동적 메모리 사용 반납해야 합니다.

• 연결 리스트에 할당된 동적 메모리를 반납하면 연결 리스트는 다음과 같이 해제됩니다.

할당된 동적 메모리를 반납하면 연결리스트 해제

 

4. 연결 리스트 생성

- 이 프로그램은 노드에 저장할 데이터 항목은 성명, 나이 그리고 2개의 데이터를 저장하는 연결 리스트입니다.

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

#define SIZE 20

typedef struct NODE{
	char name[SIZE];
	int age;
	struct NODE *link;
}NODE;

int main()
{
	NODE *list = NULL;
	NODE *p_prev = NULL, *p, *p_next;
	char buffer[SIZE];
	int age;
	
	while(1)
	{
		printf("\n성명 입력(그냥 [Enter]를 치면 종료) : ");
		gets(buffer);
		if(buffer[0] == '\0') break;
		
		p = (NODE *)malloc(sizeof(NODE));
		strcpy(p -> name, buffer);
		printf("나이 입력 : ");
		gets(buffer);
		age = atoi(buffer);
		p -> age = age;
		
		if(list == NULL)
			list = p;
		else
			p_prev -> link = p;
			p -> link = NULL;
		p_prev = p;
	}
	p = list;
	while(p != NULL)
	{
		printf("[%s, %d]", p -> name, p -> age);
		p = p -> link;
		
		if(p != NULL)
			printf(" -> ");
	}
	
	p = list;
	while(p != NULL)
	{
		p_next = p -> link;
		free(p);
		p = p_next;
	}
	return 0;
}

 

- 사용자 정의 함수로 연결 리스트를 생성하는 프로그램  

• 새로운 노드를 생성하기 위해서는 사용자 정의 함수를 정의해 놓고 필요할 때마다 호출하는 것이 일반적인 연결 리스트 생성 방법입니다.
• 이러한 필요성을 충족하기 위해 다음 프로그램 예문에서는 사용자 정의 함수를 사용하여 연결 리스트를 생성하는 프로그램을 수행하였습니다.

에러발생 입력하지 마세요

#include<stdio.h>
#include<stdlib.h>

#define SIZE 20

typedef struct data{
	char name[SIZE];
	int sno;
}DATA;

typedef struct node{
	DATA data;
	struct node *link;
}NODE;

NODE *insert_node(NODE *p_list, NODE *pprev, DATA item);
void display_menu();
int get_selected_menu();
DATA get_input_students();
void deletee(NODE *pptr);
void print_list(NODE *p_list);
void destroy_nodes(NODE *p_list);
void end_display();

int main()
{
	NODE *p_list = NULL;
	int selected = 0;
	DATA d;
	
	while(selected != 3)
	{
		display_menu();
		selected = get_selected_menu();
		
		switch(selected)
		{
			case 1:
				d = get_input_students();
				p_list = insert_node(p_list, NULL, d);
				printf("학생 정보 입력 완료\n\n");
				break;
			case 2:
				deletee(p_list);
				printf("학생 정보 삭제 완료\n\n");
				break; 
			case 3:
				print_list(p_list);
				printf(">> 학생 정보 출력 완료\n\n");
				break;
			case 4:
				destroy_nodes(p_list);
				end_display();
				break;
		}
	}
	return 0;
}

NODE *insert_node(NODE *p_list, NODE *pprev, DATA item)
{
	NODE *pnew = NULL;
	if(!(pnew = (NODE *)malloc(sizeof(NODE))))
	{
		printf("메모리 동적 할당 오류 발생\n");
		exit(1);
	}
	
	pnew -> data = item;
	
	if(pprev == NULL)
	{
		pnew -> link = p_list;
		p_list = pnew;
	}
	else
	{
		pnew -> link = pprev -> link;
		pprev -> link = pnew;
	}
	return p_list;
}

void display_menu()
{
	printf("학생 정보 관리 메뉴\n");
	printf("1.학생 정보 추가\n");
	printf("2.학생 정보 삭제\n");
	printf("3.학생 정보 출력\n"); 
	printf("4.종료\n");
}

int get_selected_menu()
{
	int selmenu = 0;
	printf("번호 선택 : ");
	scanf("%d", &selmenu);
	getchar();
	return selmenu;
}

DATA get_input_students()
{
	DATA input;
	printf("\n학번 입력 : ");
	scanf("%d", &input.sno);
	getchar();
	printf("성명 입력 : ");
	gets(input.name);
	return input;
}

void deletee(NODE *pptr)
{
	NODE ptr,preptr;
	preptr = *pptr;
	int sno;
	printf("\n학번 입력 : ");
	scanf("%d", &sno);
	if(preptr->data.sno == NULL)
	{
		printf("No data\n");
		return;
	}
	else if(preptr->data.sno == sno)
	{
		*pptr = *pptr->link;
		return;
	}
	ptr = *pptr->link;
	while (ptr->data.sno != sno && ptr->link != NULL)
	{
		preptr = preptr->link;
		ptr = preptr->link;
	}
	if(ptr->data.sno == sno)
	{
		preptr->link = ptr->link;
		free(ptr);
	}
	else
	{
		printf("Not found\n");
	}
}

void print_list(NODE *p_list)
{
	NODE *ptr;
	for(ptr = p_list; ptr; ptr = ptr -> link)
	{
		printf("\n학번 : %d\n", ptr -> data.sno);
		printf("성명 : %s\n", ptr -> data.name);
	}
}

void destroy_nodes(NODE *p_list)
{
	NODE *temp;
	while (p_list)
	{
		temp = p_list;
		p_list = p_list -> link;
		free(temp);
	}
}

void end_display()
{
	printf("프로그램 종료\n");
}