연결리스트

해당 게시물은 김성엽님 유튜브 강의 내용을 포함하고 있습니다.

 스스로 공부하고 정리하기 위한 목적으로 올리는 것입니다.

---

해당 게시물은 단일 연결리스트의 기본틀에 대한 소스입니다.

 

1단계 기본틀

#include <stdio.h>

typedef struct node {
	int num; //숫자를 저장할 변수
	struct node* p_next; //다음 노드를 가리킬 포인터
} NODE;

void Addnub(NODE** pp_head, int data) { //pp_head -> p_head ->NULL
	NODE* p;	//현재 표시를 위해 선언함
	if (NULL != *pp_head) { //값이 있을 경우
		p = *pp_head; //현재 표시를 위해 p에 첫주소가 가르키는 값을 넣어줌
		while (NULL != p->p_next) { //끝부분을 찾기 위한 반복문
			p = p -> p_next; //null일때(끝부분)까지 노드 하나씩 이동
		}
		p->p_next = (NODE*)malloc(sizeof(NODE)); //끝부분에서 동적할당을 해서 값 넣을 곳 생성
		p = p->p_next; //마지막 부분을 넣어줌
	}
	else { //첫부분일 경우
		*pp_head = (NODE*)malloc(sizeof(NODE)); //p_head에 malloc 동적할당
		p = *pp_head; //진행사항 표시하는 것
	}
	p->num = data; //data입력
	p->p_next = NULL; //끝부분 표시를 위한 NULL값을 넣어줌
}

void main() {
	NODE* p_head = NULL; //첫부분으로, 초기화로 NULL값을 줌
	Addnub(&p_head, 15); //p_head의 주소값과 넣을 데이터를 함수에 넘겨줌
}

 

2단계 while문 대신 tail_point 사용

• 노드가 추가될 때마다 마지막 노드를 찾기 위해 탐색하면 노드가 많을 수록 수행시간은 길어진다.

• 따라서, 마지막 노드의 값을 기억하는 테일 포인터(tail pointer)를 사용한다.

#include <stdio.h>

typedef struct node {
	int num; //숫자를 저장할 변수
	struct node* p_next; //다음 노드를 가리킬 포인터
} NODE;

void Addnub(NODE** pp_head, NODE**pp_tail, int data) { 
	NODE* p;	//현재 표시를 위해 선언함
	if (NULL != *pp_head) { //값이 있을 경우
		(*pp_tail)->p_next = (NODE*)malloc(sizeof(NODE)); //새 값을 넣을 공간 할당
		*pp_tail = (*pp_tail)->p_next; //끝부분 표시
	}
	else { //첫부분일 경우
		*pp_head = (NODE*)malloc(sizeof(NODE)); //p_head에 malloc 동적할당
		*pp_tail = *pp_head; //끝부분 표시
	}
	(*pp_tail)->num = data; //data입력
	(*pp_tail)->p_next = NULL; //끝부분 표시를 위한 NULL값을 넣어줌
}

void main() {
	NODE* p_head = NULL; //첫부분으로, 초기화로 NULL값을 줌
	NODE* p_tail = NULL; //마지막부분으로, 초기화 NULL값을 줌
	Addnub(&p_head, &p_tail, 15); //p_head, p_tail의 주소와 넣을 데이터를 함수에 넘겨줌
}

 

3단계 연결리스트의 전체 노드 제거하기

• 프로그램 끝날 때 동적으로 할당된 노드를 모두 제거해야한다.

• 연결 리스트를 구성하는 노드를 탐색하여 하나씩 노드 제거한다.

NODE* p = p_head, * p_save;
	while (NULL != p) {
		p_save = p->p_next; //다음 노드의 주소를 p_save에 저장해둠
		free(p); //p가 가르키고 있는 노드를 삭제함
		p = p_save; //저장해둔 다음 노드로 이동함
	}
	p_head = p_tail = NULL; //연결 리스트의 시작과 끝 초기화

 

4단계 총정리

#include <stdio.h>

typedef struct node {
	int num; //숫자를 저장할 변수
	struct node* p_next; //다음 노드를 가리킬 포인터
} NODE;

void Addnub(NODE** pp_head, NODE** pp_tail, int data) {
	if (NULL != *pp_head) { //값이 있을 경우
		(*pp_tail)->p_next = (NODE*)malloc(sizeof(NODE)); //새 값을 넣을 공간 할당
		*pp_tail = (*pp_tail)->p_next; //끝부분 표시
	}
	else { //첫부분일 경우
		*pp_head = (NODE*)malloc(sizeof(NODE)); //p_head에 malloc 동적할당
		*pp_tail = *pp_head; //끝부분 표시
	}
	(*pp_tail)->num = data; //data입력
	(*pp_tail)->p_next = NULL; //끝부분 표시를 위한 NULL값을 넣어줌
}


void main() {
	NODE* p_head = NULL; //첫부분으로, 초기화로 NULL값을 줌
	NODE* p_tail = NULL; //마지막부분으로, 초기화 NULL값을 줌
	Addnub(&p_head, &p_tail, 15); //p_head, p_tail의 주소와 넣을 데이터를 함수에 넘겨줌
	NODE* p = p_head, * p_save;
	while (NULL != p) {
		p_save = p->p_next; //다음 노드의 주소를 p_save에 저장해둠
		free(p); //p가 가르키고 있는 노드를 삭제함
		p = p_save; //저장해둔 다음 노드로 이동함
	}
	p_head = p_tail = NULL; //연결 리스트의 시작과 끝 초기화
}