[C 프로그래밍] 동적 메모리_4.실습_연결리스트1(Linked List)

▶1 계획단계 : 연결리스트를 구현해보자. 먼저 노드 구현부터 계획하자.
– 노드의 구현은 자기 참조 구조체 이용 
– Node 라는 구조체를 정의하고, 그 안에 데이터와 구조체 Node의 주소를 저장할 수 
있는 변수 선언
- 각 노드는 정수 하나를 입력 받아 저장하도록 한다.

struct Node
{
	int n;
	struct Node* next;
};

▶2 정의한 구조체 Node의 포인터 변수이자 연결 리스트의 시작과 끝을 의미하는 head, last를 만들자.

struct Node *head;
struct Node *Last;

▶3 기능을 구현할 함수를 미리 계획해보자. 

//메인 메뉴를 보여주는 함수
void showMenu(); 
//만들어진 연결 리스트를 순환하며 출력하는 함수
void printNodes(struct Node* head); 
//연결 리스트를 순환하며 모든 노드의 메모리를 해제하는 함수
void freeNodes(struct Node* head);

▶4 실습단계 
- 헤더파일을 참조하고 사용할 구조체와 함수 원형을 선언하자

※개인적으로 가독성이 좋게하려고 pragma warning(disable 4996)를 썼지만, 직접 연습하실 때에는 scanf_s로 하시는 걸 추천합니다.

#pragma warning(disable 4996) //착한 개발자라면 가능하면 쓰지말자
#include <stdio.h>
#include <stdlib.h>

struct Node
{
	int n;
	struct Node *next;
};

void showMenu();
void printNodes(struct Node* p);
void freeNodes(struct Node* p);

▶5 메인함수 작성

void main(){
	// 메인함수에서 사용할 기본 변수 선언 
	int flag = 1;
	int input;
	
	struct Node *head;//연결 리스트의 첫 원소를 저장할 포인터 변수 head
	struct Node *last;//마지막 원소의 주소를 저장할 last 변수
	struct Node *node;//추가될 노드의 주소를 임시로 저장할 포인터 변수 node 
	
	//아직 추가된 노드가 없기 때문에, Head 와 last 의 초기값을 NULL 로 설정
	head = NULL;
	last = NULL;
	
	//사용자 입력이 0 이 될 때까지, 반복 수행
	while(flag){
		//메뉴를 출력 후, 사용자의 입력을 input 변수에 저장
		showMenu();
		scanf("%d", &input);
		
		//사용자 입력이 0이면, flag 값을 0으로 바꾸고, while 반복문을 종료
		if(input ==0){
			flag = 0;
		}else{//사용자 입력이 0이 아니면, 노드를 연결 리스트에 추가
			
			//Node 구조체를 동적 할당
			node = (struct Node*)malloc(sizeof(struct Node));
			
			//생성된 Node 구조체에 값을 설정
			node->n = input;
			node->next = NULL;
			
			//연결 리스트가 비어있을 경우, head에 생성된 node 의 주소를 저장
			if(head == NULL){
				head = node;
			}else{ //연결 리스트가 비어있지 않을 경우, 마지막 노드의 next에 생성된 node의 주소를 저장
				last->next=node;
			}
			
			//연결 리스트에 추가된 node의 주소를 last에 저장
			last = node;
		}
	}
	
	//연결 리스트에 저장된 값을 화면에 출력하고, 사용된 동적 메모리를 모두 해제
	printNodes(head);
	freeNodes(head);
}

▶6 주요 함수 구현_1. showMenu()

void showMenu(){
	printf("저장할 정수를 입력/종료:0 : ");
}

▶7 주요 함수 구현_2. printNodes()

void printNodes(struct Node* p){
	//p가 NULL 아닌 경우 = 마지막 노드가 아닌 경우
	while(p!=NULL){
		//노드에 저장된 값을 출력하고, 다음 노드로 이동
		printf("%d\n",p->n);
		p = p->next;
	}
}

▶8 주요 함수 구현_3. freeNodes()

void freeNodes(struct Node* p){
	struct Node *temp;//다음 노드의 주소를 임시 저장할 temp 변수
	while(p!=NULL){//연결 리스트의 끝 까지 반복
		temp = p;//지울 노드를 임시변수에 저장
		p = p->next;//다음 노드로 이동
		free(temp);//임시변수에 저장된 이전 노드를 해제
	}
}

▶9. 전체코드 : ideone에서 확인하기 

※null과 NULL을 조심하자.

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

struct Node
{
	int n;
	struct Node *next;
};

void showMenu();
void printNodes(struct Node* p);
void freeNodes(struct Node* p);

void main(){
	// 메인함수에서 사용할 기본 변수 선언 
	int flag = 1;
	int input;
	
	struct Node *head;//연결 리스트의 첫 원소를 저장할 포인터 변수 head
	struct Node *last;//마지막 원소의 주소를 저장할 last 변수
	struct Node *node;//추가될 노드의 주소를 임시로 저장할 포인터 변수 node 
	
	//아직 추가된 노드가 없기 때문에, Head 와 last 의 초기값을 NULL 로 설정
	head = NULL;
	last = NULL;
	
	//사용자 입력이 0 이 될 때까지, 반복 수행
	while(flag){
		//메뉴를 출력 후, 사용자의 입력을 input 변수에 저장
		showMenu();
		scanf("%d", &input);
		
		//사용자 입력이 0이면, flag 값을 0으로 바꾸고, while 반복문을 종료
		if(input ==0){
			flag = 0;
		}else{//사용자 입력이 0이 아니면, 노드를 연결 리스트에 추가
			
			//Node 구조체를 동적 할당
			node = (struct Node*)malloc(sizeof(struct Node));
			
			//생성된 Node 구조체에 값을 설정
			node->n = input;
			node->next = NULL;
			
			//연결 리스트가 비어있을 경우, head에 생성된 node 의 주소를 저장
			if(head == NULL){
				head = node;
			}else{ //연결 리스트가 비어있지 않을 경우, 마지막 노드의 next에 생성된 node의 주소를 저장
				last->next=node;
			}
			
			//연결 리스트에 추가된 node의 주소를 last에 저장
			last = node;
		}
	}
	
	//연결 리스트에 저장된 값을 화면에 출력하고, 사용된 동적 메모리를 모두 해제
	printNodes(head);
	freeNodes(head);
}

void showMenu(){
	printf("저장할 정수를 입력/종료:0 : ");
}

void printNodes(struct Node* p){
	//p가 NULL 아닌 경우 = 마지막 노드가 아닌 경우
	while(p!=NULL){
		//노드에 저장된 값을 출력하고, 다음 노드로 이동
		printf("%d\n",p->n);
		p = p->next;
	}
}

void freeNodes(struct Node* p){
	struct Node *temp;//다음 노드의 주소를 임시 저장할 temp 변수
	while(p!=NULL){//연결 리스트의 끝 까지 반복
		temp = p;//지울 노드를 임시변수에 저장
		p = p->next;//다음 노드로 이동
		free(temp);//임시변수에 저장된 이전 노드를 해제
	}
}