My Study/C, C++

단순 연결 리스트(Linked List)

연결 리스트를 들어가기 전에 자신 스스로에게 물어보자.

1. 동적 할당을 자유롭게 할 수 있는가??(malloc 함수)

2. 구조체를 자유롭게 사용 할 수 있는가??(struct)


글쓴이는 위 2가지가 부족하여 이해하는데 어려워서 공부를 하고 연결 리스트를 공부하였다.


연결 리스트란 무엇일까? 자료구조 종류 중 하나로 어떤 데이터(앞으로 노드 Node)를 저장할 때 다음 자료가 있는 위치를 포함시키는 방식으로 자료를 저장하며, 동적 할당을 이용하여 필요할 때마다 길이를 늘리고 줄일 수있다. 글로 읽으면 딱딱하고 이해가 어려울 수가 있으니 그림으로도 살펴보자.



[노드에 자료와 다음 자료가 있는 위치를 포함한다.]



여기서 궁금증이 떠오를 수가 있을 것이다. 배열로 하면 간단하지 않는가? 물론 자료 길이가 정해져 있으면 배열로 정의하여 사용할 수 있을 것이다. 하지만 자료 길이가 어느 정도로 필요한지 모르고, 알고 있다해도 다음에 확장을 할 때마다 프로그램을 고칠것인가? 또한 확장성을 위해서 10 정도의 길이를 100 길이로 미리 정의 해놓으면 90 이란 공간이 사용 되지 않고 공간만 차지하고 있는 비효율적인 코딩이 될 것이다.


이제 연결 리스트를 하나씩 구현해보자. 제일 먼저 main 함수를 만들자.


void main() { List list; //포인터 변수 int data; //데이터 int i; NodeInit(&list); //포인터 변수 초기화 NodeInsert(&list, 1); //새로운 노드 추가 NodeInsert(&list, 2); NodeInsert(&list, 3); NodeInsert(&list, 4); //연결 리스트 출력 if (CurFirst(&list, &data)) //커서를 처음으로 이동시키는 함수 { printf("%d ", data); while (CurNext(&list, &data)) //커서를 다음으로 이동시키는 함수 printf("%d ", data); } //메모리에서 제거 if (CurFirst(&list, &data)) { NodeRemove(&list, &data); //노드를 제거하는 함수 printf("삭제 : %d ", data); for (i = 0; i < list.num;) { NodeRemove(&list, &data); printf("%d ", data); } } }


위에서 나오는 함수들을 살펴보자.


NodeInit

포인터 변수를 초기화 시켜주는 함수로서 초기화하면 처음에 쓰레기 값을 방지하는 함수이다.

NodeInsert

노드를 추가시키는 함수로서 동적 할당 함수(malloc)를 사용하여 메모리에 노드를 삽입할 것이다.
CurFirst

커서를 처음부분으로 옮기는 함수이다. 여기선 데이터를 출력 및 삭제할 때 사용할 것이다.

CurNext

커서를 다음부분으로 옮기는 함수이다. 여기선 데이터를 출력 및 삭제할 때 사용할 것이다.

NodeRemove

동적 할당이 된 노드를 제거해주는 함수(free)를 사용하여 필요가 없어진 노드를 메모리에서 삭제 시킬 것이다.


메인 함수 다음으로 연결 리스트의 노드를 생성해보자.


typedef struct _node
{
	int data;  //자료
	struct _node *next; //다음 자료 위치를 저장할 곳
}node;


이것을 그림으로 표현하자면 아래와 같이 데이터가 들어갈 공간을 만든것이다.


다음은 연결 리스트에서 주요한 역할을 하는 포인터 변수를 선언해보자. 


typedef struct _list { node *head; //처음을 가리키는 포인터 node *tail; //마지막을 가리키는 포인터 node *cur; //위치를 가리키는 포인터 int num; //노드 갯수 }List;


포인터 변수는 아래 그림과 같이 사용될 것이다.




이제 드디어 main 함수에서 사용된 함수들을 만들어보자. 먼저 포인터 변수를 초기화 시키는 함수이다.


void NodeInit(List *plist) { plist->head = NULL; plist->tail = NULL; plist->cur = NULL; plist->num = 0; }


포인터 변수들을 전부 NULL 로 초기화 함으로서 쓰레기 값을 없애준다. 


이번엔 노드를 동적할당 하는 부분으로서 여기서는 천천히 읽으며 그림을 그려보는 것을 추천한다.


void NodeInsert(List *plist, int data)
{
	//새로운 노드를 추가 
	node *newnode = (node*)malloc(sizeof(node));
	newnode->data = data; //데이터
	newnode->next = NULL; //다음 위치 초기화

	//처음이면 머리는 새로운 노드
	if (plist->head == NULL)
		plist->head = newnode;
	//두번째부터 앞 노드와 연결하는 부분
	else
		plist->tail->next = newnode;
	
	//마지막은 항상 꼬리
	plist->tail = newnode;
	//노드가 추가 됬으니 num 증가
	(plist->num)++;
}


위 함수를 하나씩 살펴보자. 먼저 새로운 노드를 추가시킨다.


[새로운 노드]

그리고 데이터를 입력받는다.



그 다음 위치를 가리키는 포인터는 NULL로 초기화.



처음으로 생성한 새로운 노드니 이 노드는 머리가 된다.



그리고 생성된 노드가 한개 뿐이니 처음이자 마지막이 된다.



노드가 추가 되었으니 num은 증가.


새로운 노드가 추가가 된다.



그리고  데이터를 입력받는다.



그 다음 위치를 가리키는 포인터는 NULL로 초기화.



이제부터 처음 노드와 살짝 달라진다. 여기서 생각해야하는 것은 마지막을 가리키는 꼬리는 바뀌지 않고 처음부분을 가리키게 된다. 그러니 꼬리의 위치 데이터는 새로운 노드를 가리키게 되니 머리 노드와 새로운 노드를 연결이 된다.



새로운 노드와 처음 노드가 연결이 된 뒤에 꼬리는 새로운 노드를 가리키게 된다.



이것이 계속 반복이 되는 것이다.

연속 그림으로 봐보자.


생성도 했으니 이번엔 화면에 출력하기 위하여 커서를 위치를 변경하는 함수를 만들어보자.


int CurFirst(List *plist, int *data) { if (plist->head == NULL) return FALSE; plist->cur = plist->head; *data = plist->cur->data; return TRUE; }


만약 노드가 비어 있으면 출력할 것이 없기에 FALSE(0) 을 반환하고 노드가 존재하면 위치를 처음으로 선언하기 위해서 머리 부분인 head를 가리킨다. 그리고 출력을 위해서 메인 함수에서 불러온 data에 현재 위치 data를 넣어 준다.


처음을 가리키고 이제 다음으로 커서를 움직이는 함수이다.


int CurNext(List *plist, int *data)
{
	if (plist->cur->next == NULL)
		return FALSE;

	plist->cur = plist->cur->next;

	*data = plist->cur->data;

	return TRUE;

}


이 함수에선 다음으로 가리키는 함수가 없으면 FALSE를 반환하고 노드가 존재하면 커서는 다음 노드를 가리키게 된다.



여기까지만 구현을 하고 정상적으로 작동하는지 컴파일을 해보겠다.

[물론 하나의 함수를 구현하고 실행하여 문제가 발생하는지 확인을 하는 것이 좋은 습관이라고 생각한다.]


[main 함수에서 메모리를 제거하는 부분을 주석처리를 한 뒤에 실행을 시켰다.]


노드들이 정상적으로 연결이 되었으며 마지막 노드까지 출력을 했기에 위치를 가리키는 cur이 4번째 데이터를 가리키고 있다. 여기까지 했으면 이제 제일 중요한것이 남았다. 그것은 바로 메모리에서 제거해주는 일이다.


마지막 함수인 노드 제거 함수를 살펴보자.


void NodeRemove(List *plist, int *data)
{
	//임시 버프
	node *buf = plist->cur;
	int nbuf = plist->cur->data;

	plist->cur = plist->cur->next;

	*data = nbuf;
	free(buf);

	(plist->num)--;
}


제거를 할 때 주의할 점은 cur 자체를 해제하는 것이 아닌 임시 버프를 만들어서 임시 버프를 free를 이용하여 제거한다는 것이다. 또한 커서를 옮기지 않고 제거하면 커서가 다음 위치가 어디인지 모르기 때문에 옮긴 뒤 삭제를 해야한다. 마지막으로는 노드 수가 감소 했으니 num도 감소 시켜준다.


여기까지 해서 컴파일을 하였으면 메모리까지 제거가 완료된것이다.



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

#define TRUE 1;
#define FALSE 0;

typedef struct _node
{
	int data;
	struct _node *next;
}node;

typedef struct _list
{
	node *head; //처음을 가리키는 포인터
	node *tail; //마지막을 가리키는 포인터
	node *curbefore;  //이전 위치 를 가리키는 포인터
	node *cur; //위치를 가리키는 포인터
	int num;	//갯수
}List;


//초기화
void NodeInit(List *plist)
{
	plist->head = NULL;
	plist->tail = NULL;
	plist->curbefore = NULL;
	plist->cur = NULL;
	plist->num = 0;
}

//동적 할당
void NodeInsert(List *plist, int data)
{
	//새로운 노드를 추가 
	node *newnode = (node*)malloc(sizeof(node));
	newnode->data = data; //데이터
	newnode->next = NULL; //다음 위치 초기화

	//처음이면 머리는 새로운 노드
	if (plist->head == NULL)
		plist->head = newnode;
	//두번째부터 앞 노드와 연결하는 부분
	else
		plist->tail->next = newnode;

	//마지막은 항상 꼬리
	plist->tail = newnode;
	//노드가 추가 됬으니 num 증가
	(plist->num)++;
}

//메모리 제거
void NodeRemove(List *plist, int *data)
{
	//임시 버프
	node *buf = plist->cur;
	int nbuf = plist->cur->data;

	plist->cur = plist->cur->next;

	*data = nbuf;
	free(buf);

	(plist->num)--;
}

//위치를 처음으로 이동
int CurFirst(List *plist, int *data)
{
	if (plist->head == NULL)
		return FALSE;

	plist->cur = plist->head;

	*data = plist->cur->data;

	return TRUE;
}

//위치를 다음 위치로 이동
int CurNext(List *plist, int *data)
{
	if (plist->cur->next == NULL)
		return FALSE;

	plist->cur = plist->cur->next;

	*data = plist->cur->data;

	return TRUE;

}

void main()
{
	List list; //포인터 변수
	int data;  //데이터
	int i;

	NodeInit(&list); //포인터 변수 초기화

	NodeInsert(&list, 1); //새로운 노드 추가
	NodeInsert(&list, 2);
	NodeInsert(&list, 3);
	NodeInsert(&list, 4);


	//프린트
	if (CurFirst(&list, &data)) //커서를 처음으로 이동시키는 함수
	{
		printf("%d ", data);

		while (CurNext(&list, &data)) //커서를 다음으로 이동시키는 함수
			printf("%d ", data);

	}

	puts("");

	if (CurFirst(&list, &data))
	{

		NodeRemove(&list, &data); //노드를 제거하는 함수
		printf("삭제 : %d ", data);

		for (i = 0; i < list.num;)
		{
			NodeRemove(&list, &data);
			printf("%d ", data);
		}
	}
	
}


지금은 설명을 위해서 코드를 한 파일에 담았지만 아래와 같이 파일을 분리 하는것이 좋은 습관이다.


Linked List.h

#ifndef __LINKED_LIST_H__
#define __LINKED_LIST_H__

#define TRUE 1;
#define FALSE 0;

typedef struct _node
{
	int data;
	struct _node *next;
}node;

typedef struct _list
{
	node *head; //처음을 가리키는 포인터
	node *tail; //마지막을 가리키는 포인터
	node *curbefore;  //이전 위치 를 가리키는 포인터
	node *cur; //위치를 가리키는 포인터
	int num;	//갯수
}List;

void NodeInit(List *plist);

void NodeInsert(List *plist, int data);
void NodeRemove(List *plist, int *data);

int CurFirst(List *plist, int *data);
int CurNext(List *plist, int *data);

#endif


Linked List.c

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

//초기화
void NodeInit(List *plist)
{
	plist->head = NULL;
	plist->tail = NULL;
	plist->curbefore = NULL;
	plist->cur = NULL;
	plist->num = 0;
}

//동적 할당
void NodeInsert(List *plist, int data)
{
	//새로운 노드를 추가 
	node *newnode = (node*)malloc(sizeof(node));
	newnode->data = data; //데이터
	newnode->next = NULL; //다음 위치 초기화

	//처음이면 머리는 새로운 노드
	if (plist->head == NULL)
		plist->head = newnode;
	//두번째부터 앞 노드와 연결하는 부분
	else
		plist->tail->next = newnode;

	//마지막은 항상 꼬리
	plist->tail = newnode;
	//노드가 추가 됬으니 num 증가
	(plist->num)++;
}

//메모리 제거
void NodeRemove(List *plist, int *data)
{
	//임시 버프
	node *buf = plist->cur;
	int nbuf = plist->cur->data;

	plist->cur = plist->cur->next;

	*data = nbuf;
	free(buf);

	(plist->num)--;
}

//위치를 처음으로 이동
int CurFirst(List *plist, int *data)
{
	if (plist->head == NULL)
		return FALSE;

	plist->cur = plist->head;

	*data = plist->cur->data;

	return TRUE;
}

//위치를 다음 위치로 이동
int CurNext(List *plist, int *data)
{
	if (plist->cur->next == NULL)
		return FALSE;

	plist->cur = plist->cur->next;

	*data = plist->cur->data;

	return TRUE;

}


Linked List Main.c

#include<stdio.h>
#include"test.h"

void main()
{
	List list; //포인터 변수
	int data;  //데이터
	int i;

	NodeInit(&list); //포인터 변수 초기화

	NodeInsert(&list, 1); //새로운 노드 추가
	NodeInsert(&list, 2);
	NodeInsert(&list, 3);
	NodeInsert(&list, 4);


	//프린트
	if (CurFirst(&list, &data)) //커서를 처음으로 이동시키는 함수
	{
		printf("%d ", data);

		while (CurNext(&list, &data)) //커서를 다음으로 이동시키는 함수
			printf("%d ", data);

	}

	puts("");

	if (CurFirst(&list, &data))
	{

		NodeRemove(&list, &data); //노드를 제거하는 함수
		printf("삭제 : %d ", data);

		for (i = 0; i < list.num;)
		{
			NodeRemove(&list, &data);
			printf("%d ", data);
		}
	}

}


'My Study > C, C++' 카테고리의 다른 글

WMI C++  (0) 2016.06.23
윈도우 콘솔 프로그램 숨기기(??)  (0) 2016.06.22
디렉토리 탐색 함수  (0) 2016.06.22
단순 연결 리스트(Linked List)  (0) 2015.02.25

최근 트랙백

알림

이 블로그는 구글에서 제공한 크롬에 최적화 되어있고, 네이버에서 제공한 나눔글꼴이 적용되어 있습니다.