Unity3D

오늘은 C언어 연결리스트에 대해서 포스팅을 해보려고 한다.

내가 자료구조라는 것을 처음 접한 대학교 2학년 때 난 이 연결리스트라는 놈을 도저히 이해할 수가 없었다.
왜 이놈들은 함수가 끝나도 계속 메모리에 남아있는 걸까? 라는게 가장 큰 의문점이었고
두번째는 그냥 적당한 라이브러리 쓰면 되는데 왜 굳이 이런걸 만들어야 하는걸까?
라는게 두번째 의문점이었다.

첫번째 의문점은 후에 "다시 체계적으로 배우는 C언어 포인터" 라는 책을 정독한 후에 풀렸고
두번째 의문점은.. 아직도 미스테리다.
다만 우리가 전산학과 학생으로서 이런 것들을 구현해보고 원리를 파악할 수 있다는 이유로 대충 이해하고 넘어가자.



사족이 길었는데..
연결리스트란 무엇인가?
리스트는 자료를 순차적으로 정리해놓은 것을 말한다.
이것들이 메모리상에서 연결되어 있다는 뜻이다.


배열 리스트 같은 경우 리스트의 크기를 미리 크게 정해놓고 그 범위 안에서만 자료의 관리가 가능하기 때문에 
메모리 낭비가 심하다고 볼수 있는데 
연결리스트의 경우는 자료가 입력 될 때마다 동적할당으로 새로운 메모리 주소에 값을 할당하고 
이전 자료와 연결해주기 때문에 메모리 관리가 용이하다.



자료 하나를 담고있는 녀석을 보통 "노드(node)" 라고 부른다.
연결 리스트에 아무것도 없는 상태에서 100이라는 값을 가진 노드를 추가한다고 생각해보자.

노드는 자기 자신의 값과 다음 노드를 가리키는 노드 포인터로 구성된다.
여기서 첫번째 노드는 100이라는 값을 갖고 있으며 다음 노드는 없으므로 NULL 포인터를 가리킨다.
위에 Head라는 노드포인터도 있는데 이것은 연결리스트라는 자료구조에서 일종의 시작점을 알려준다.
배열 리스트 처럼 인덱스를 이용한 간편한 접근이 불가능하므로 첫 노드를 Head 포인터로 가르켜주고
그 Head 포인터를 이용해 다음 노드, 다음 노드 이런 식으로 다른 노드에 접근할 수 있다.

101이라는 값을 갖고 있는 두번째 노드를 삽입하면 이렇게 된다. (과정은 잠시 후에 설명)
기존에 NULL 포인터를 가리키고 있던 첫번째 노드(100이라는 값을 가진 노드)는 이제 다음 노드로 새로 추가된 노드를 가리키고 두번째이자 마지막 노드가 된 101이라는 값을 가진 노드는 다음 노드로 NULL 포인터를 가리킨다.
연결 리스트는 이와 같은 구조로 자료들을 쭈욱 연결해서 저장한다.

그럼 이제 100 노드와 101 노드 사이에 200이라는 값을 가진 노드를 삽입해보자.
우선 동적할당으로 노드 하나를 만들어주고 200이라는 값을 넣어준다.
이 노드의 다음 노드는 원래 100 노드가 다음 노드로 가리키던 노드를 가리키도록 해준 다음
100노드의 다음 노드를 200 노드로 설정하면 깔끔하게 삽입된다.



나도 공대생 인지라.. 이런 복잡한 그림보다 코드를 보는게 이해가 빠를것 같아서..
설명은 여기까지.





아래는 struct 와 함수 선언부분이다. (헤더파일로 쓸 수 있음)

node 는 정수형인 value 와 node*(노드포인터) 형인 next 라는 변수를 갖고 있다.
이 코드에서 우리는 node 보다는 node pointer를 많이 쓸것이므로 typedef를 이용해 nptr을 지정해줬다.
그다음은 list라는 struct를 정해서 head를 가리키는 노드포인터와 리스트에에 몇개의 노드가 있는지 알려주는 count라는 변수를 만들었다.
그 아래쪽 함수는 생각하는 그대로다. (순서대로 초기화, 삽입, 삭제, 검색, 수정, 출력)




연결 리스트 초기화 함수이다.

메인 함수에서 list를 만들고 그 주소를 init()에 넘겨주어 count와 head를 초기화시킨다.




노드 삽입 함수. 리스트형 포인터 변수와 값, 위치를 인수로 받는다.

처음 if 문은 position 값이 적절한지 체크하는 부분이다. 부적절하면 메시지를 출력하고 종료한다.
다음은 new_nptr 이라는 노드포인터에 node 사이즈만큼의 메모리를 동적할당하고 value변수를 설정해준다.
position이 1인 경우 head포인터가 바뀌어야 하므로 첫부분에서 따로 처리해줬고
그게 아닌 경우는 head 포인터의 값을 tmp라는 변수에 복사해서 for 문을 이용해 의도한 위치에 도달할 때까지 계속 next로 찾아간다.
적정 위치에 도달하면 삽입한 후 리스트의 카운터를 1 증가시킨다.




삭제 함수. 리스트형 포인터변수와 위치를 인수로 받는다.

첫부분은 삽입과 마찬가지로 position의 처리 가능 범위를 체크한다. (단, 삽입의 경우 맨 뒤에도 삽입 가능하기 때문에 기존에 존재하는 노드들의 position만 받아야 하는 삭제 함수와는 범위가 1 차이 난다.)
삽입과 마찬가지로 head 포인터를 tmp로 받아준 다음 position이 1이면 head 노드를 바꿔주고 그게 아니라면 position 변수를 이용해 그 위치로 찾아가서 해당 노드의 연결을 해지시킨다.
삭제될 노드의 앞 노드를 tmp로 받고 그 다음 노드를 tmp2로 받아서 tmp2의 다음노드가 tmp의 다음 노드가 되도록 짰다.
삭제에서 주의할 점은 삭제된 노드가 메모리에서 지워질 수 있도록 free() 함수를 이용해줘야 한다는 것이다.
(이때문에 굳이 tmp2라는 노드 포인터 변수를 선언했다.)




검색 함수. 리스트형 포인터 변수와 값을 인수로 받는다.

값을 입력받아서 리스트를 순회하여 같은 값이 있는지 알아본다.
같은 값이 여러개 있다면 처음 나온 position을 리턴하고 없으면 0을 리턴한다.
테스트를 위해 적절한 printf() 함수를 사용했다.




수정 함수. 리스트형 포인터 변수와 값, 위치를 인수로 받는다.

삽입, 삭제와 비슷한데 다른 점은 head 포인터를 변경할 필요가 없다는 것이다.
해당 위치의 노드만 찾아서 값을 바꿔주면 된다.




출력 함수. 리스트형 포인터 변수를 인수로 받는다.

이건 테스트를 위해 만들어본 함수다.
리스트에 들어있는 값들과 count 값을 출력해준다.




메인 함수.

리스트형 포인터변수에 리스트 크기의 메모리를 동적할당 해주고 init(() 함수를 이용해 초기화시켜준다.
저 뒤에 여러가지 테스트 한다고 끄적거려 논거 있는데 너무 길어서 여기까지만 캡쳐.
그래서 뒤에 } 로 닫아줘야 함.



출처 : http://milvus.tistory.com/17

소스코드

/*

 * linkedlist.c

 *

 *  Created on: 2011. 4. 21.

 *      Author: Chwang

 */

#include <stdio.h>

#include <stdlib.h>

typedef struct _node{

int value;

struct _node* next;

}node;

typedef node* nptr;

typedef struct _list{

int count;

nptr head;

}list;

void init(list* lptr);

void insert(list* lptr,int value,int position);

void delete(list* lptr,int position);

int search(list* lptr,int value);

void modify(list* lptr,int value,int position);

void print_list(list* lptr);

void init(list* lptr){

//initialize the list

lptr->count=0;

lptr->head=NULL;

}

void insert(list* lptr,int value,int position){

//insert value to proper position

if(position<1 || position>(lptr->count)+1){

printf("Position Out of Bound\n");

return;

}

nptr new_nptr=(node*)malloc(sizeof(node));

new_nptr->value=value;

if(position==1){

new_nptr->next=lptr->head;

lptr->head=new_nptr;

}

else{

nptr tmp=lptr->head;

int i;

for(i=1;i<position-1;i++){

tmp=tmp->next;

}

new_nptr->next=tmp->next;

tmp->next=new_nptr;

}

lptr->count++;

}

void delete(list* lptr,int position){

//delete an item on the position

if(position<1 || position>(lptr->count)){

printf("Position Out of Bound\n");

return;

}

nptr tmp=lptr->head;

if(position==1){

lptr->head=tmp->next;

free(tmp);

}

else{

int i;

for(i=1;i<position-1;i++){

tmp=tmp->next;

}

nptr tmp2=tmp->next;

tmp->next=tmp2->next;

free(tmp2);

}

lptr->count--;

}

int search(list* lptr,int value){

//traverse the list and

//find the first position of the value (first from head)

//if not exist, return 0

nptr tmp=lptr->head;

int i=1;

while(tmp!=NULL){

if(value==tmp->value) break;

i++;

tmp=tmp->next;

}

if(i>lptr->count){

printf("The value %d is NOT exists\n",value);

return 0;

}

else{

printf("The value %d is at position %d in the list\n",value,i);

return i;

}

}

void modify(list* lptr,int value,int position){

if(position<1 || position>(lptr->count)){

printf("Position Out of Bound\n");

return;

}

nptr tmp=lptr->head;

int i;

for(i=1;i<position;i++){

tmp=tmp->next;

}

tmp->value=value;

}

void print_list(list* lptr){

nptr tmp=lptr->head;

printf("List value: ");

while(tmp!=NULL){

printf("%d ",tmp->value);

tmp=tmp->next;

}

printf("\n");

printf("Total: %d value(s)\n",lptr->count);

}

int main(){

list* mylist=(list*)malloc(sizeof(list));

init(mylist);

insert(mylist,3,1);

insert(mylist,4,2);

insert(mylist,5,3);

insert(mylist,6,4);

insert(mylist,7,5);

insert(mylist,8,6);

insert(mylist,9,7);

insert(mylist,3,3);

print_list(mylist);

delete(mylist,3);

delete(mylist,5);

print_list(mylist);

search(mylist,6);

search(mylist,9);

search(mylist,0);

modify(mylist,100,1);

modify(mylist,101,2);

print_list(mylist);

return 0;

}