링크드 리스트에대해 아주 상세히 설명햇습니다

직접공부하면서 

왜그렇게되는데? 왜그래야되는데?

라는질문을 끝없이 던지며

그에맞는답을찾고 완벽한 이해가 되도록 노력햇습니다.


저처럼 기본에 충실하고싶으신 분들에게 도움이 됬으면 하는 바램입니다.


<h2>링크드 리스트란</h2>


링크드리스트랑 배열과 비슷한 자료구조의 한형태로


일정한단위의 자료들이 하나의 개체로 묶여져잇는 상태를말합니다.




<h3>배열과의차이점</h3>


배열은 메모리의 주소가 순차적으로 부여되여지고

링크드리스트는 메모리의주소가 순차적이지않지않습니다


<h3 style=\"font-family: Gulim; line-height: normal;\">링크드 리스트의 필요성</h3>

컴파일후 사용자의 편의에따라 자료구조의 크기를 늘려야할 상황이올떄

배열구조를 사용해 프로그래밍햇다면

자료의크기가 증가될떄마다 일일히 컴파일을 다시해줘야할것입니다.


<h4 style=\"font-family: Gulim; font-size: medium; line-height: normal;\">배열을 컴파일후 추가로 늘릴수없는이유</h4>


배열은 컴파일시 메모리의 스택 영역에 올라가게됩니다.

이렇게 스택영역에올라간 배열에 추가로 배열을 덧붙이는 작업을 해야할상황에

<u>배열뒤의 메모리영역이 안씌여지고있다는 확신을 컴퓨터는 할수없습니다</u>.

스택영역은 실시간으로 메모리가 부여되고 사라지는 공간이기떄문에

선언햇던배열의 뒷부분의 활용여부가 비확실하다는점이지요.


그렇기때문에 링크드 리스트란 자료구조가 필요하게됬습니다.


<h2 style=\"font-family: Gulim; line-height: normal;\">링크드리스트란?</h2>

배열처럼 c언어에서 기본으로 제공되는 함수를 사용하면 될것같지만

c언어에서 기본적으로 제공되는 함수가 아닙니다.


사용자의 편의로 임의생성한 자료구조입니다.


그럼 링크드리스트의 기본 형식을 알아봅시다.


<h3 style=\"font-family: Gulim; line-height: normal;\">링크드리스트의 기본형식</h3>


알아보기전에 배열의 자료구조 접근 방식에대해 알아봅시다

그후 어떻해 링크드스트를 구현해야할지 생각해봅시다.


<h4 style=\"font-family: Gulim; font-size: medium; line-height: normal;\">배열의 자료 접근 방식</h4>


int a[5];


int 형식의 배열 이선언됫습니다


5개의 int크기의 메모리가 부여됬습니다

(8byte*5)-> 40byte)


이제 컴퓨터는 a라는 이름만가지고 모든 자료에 접근을합니다


여기서 a란 포인트주소로


a[0]의 주소를 나타내는 역활과

a[0]~a[4]까지의 배열을 나타는 역활

2가지를 담당합니다

 배열자료 생성시 자료구조의 이름은 0부터 시작합니다

<blockquote class=\"tr_bq\" style=\"font-family: Gulim; font-size: medium; line-height: normal;\">

5개의 배열을 구성하엿다면 이름은

0~4

10개의 배열을 구성햇다면 이름은

0~9

까지가됩니다

</blockquote>



#include <stdio.h>


int main()

{

int a[5];

a=1;

}



컴파일시

오류 1 error C2440: \'=\' : \'int\'에서 \'int [5]\'(으)로 변환할 수 없습니다.



전에설명시 a는 a[0]의 시작주소를 나타난다고 하엿습니다


헌데왜 a값이 대입이 안되는것일까요?


그이유는 a가 2가지의 역활을 담당하고있기떄문입니다.


a가 한가지의역활 (a의 시작주소) 만 가지고있다면


컴파일은 정상적으로 될것입니다


하지만 a라는 이름의 변수는 a[0]의 시작주소와 a[0]~a[4]까지의 자료구조를


나타내고있기떄문에 int[5]!= int 오류가 나는것입니다.


이 오류를 고치기위해선


#include <stdio.h>


int main()

{

int a[5];

a[0]=1;

}


이렇게 변경해주면 컴파일은 정상적으로 작동합니다.


이제 컴퓨터가 다음 메모리에 접근하는 방식에대해 알아봅시다


#include <stdio.h>


int main()

{

int a[5];

a[1]=2;

}


컴퓨터는 a라는 포인트 주소를가지고 자료의 위치를계산합니다


a의 메모리위치를 100이라 가정하면


2번쨰 배열에 접근하기위해서 컴퓨터는


100+4이라는 연산을통해


104번지의 메모리주소로 진입하게됩니다.


여기서 왜 101번지가 아니고 104번지가 됬을까요?


메모리의주소는 바이트마다 주소가 부여됩니다.


int 형식의 자료구조는 4byte이기때문에


다음배열의 주소가 104이 되는것입니다.


다음 예제를통해 증명이가능합니다


#include <stdio.h>


int main()

{

int a[5];

    printf(\"%p\\n\",a);

printf(\"%p\\n\",&a[0]);

printf(\"%p\\n\",&a[1]);

printf(\"%p\\n\",&a[2]);

printf(\"%p\\n\",&a[3]);

printf(\"%p\\n\",&a[4]);

}



이예제에서 %p란 포인트 주소를 나타내주는 반환문자로


메모리주소는 16진법으로 부여되기떄문에


16진으로 주소가 나타나게됩니다.


이 예제를 좀더 보기쉽게 만들려면


%d반환문자를 사용해도 문제없습니다


여기서 봐야할점은 a의 주소와 a[0]의 주소가 같다는점


전에 설명햇던부분을참조하여 이해하시면 될것같습니다.


위의 내용을통해 컴퓨터는


(a+(sizeof(int)*배열의번호)


를통해 위치를 연산한다는점을 알수있엇습니다.


이제 링크드리스트를 구현해보는 방법에대해 생각해봅시다




<h3>링크드리스트 구현</h3>


배열은 물리적인 메모리주소가 일정하기떄문에 배열의위치를


시작주소만가지고 배열의 위치를 연산할수잇엇습니다.


하지만 링크드리스트는 이 메모리주소가 일정하지않기때문에


다음 자료의 메모리주소의 정보를 따로 저장할 필요가있을것입니다.


또 무엇이 필요할까요?


일단 링크드리스트를 구현하는 목적자체가


데이터 저장에있습니다


데이터를 저장한 공간도 지정해 줘야할것입니다.



우선 이 두가지정도만 생각해주면 링크드 리스트가 구현될것같습니다.


두가지정보를 하나의 개체로묶고 생각하면 편리할것같네요


여기서 <u>구조체 </u>를 써봅시다.


struct Node{

node* next;

node* prev


void*data

};


여기서 노드란 링크드리스트에서 데이터정보와 주소의 정보를 가지고있는 개체를 말합니다.


node* next -->


노드형 데이터의 주소가 저장됩니다.(다음에올 노드주소) 


헌데


포인터의 주소는 int 형으로 다저장할수있는데

(메모리주소는 2^32 이하로 부여가됩니다 이부분이 궁금하시다면 

http://cappleblog.co.kr/554 를 참조하시면 될것같습니다.)


 왜


굳이 node형 으로 포인터주소를 저장해야할까요?


간단하게설명드리면


포인터주소는 시작주소만을 나타내고있습니다


이 주소의 시작부분은아는데 끝부분은 어떻해 알수있을까요?


(포인터주소가 100이라 가정할때 int = 100~103 ,double = 100~107);


컴퓨터가 그판단의 근거로 사용하는것이 바로 앞에붙어있는 자료의 형태입니다.


(이부분을 더 알고싶으신분들을 포인터 부분에대해 공부하시면됩니다.)


node* preb-->



전노드의 주소를 따로 지정해주는이유는


노드의 활용성을 높이기위해서입니다


노드의 원형구조와 관련있는데


뒤쪽부분에 설명해두엇습니다.


void* data -->


데이터의 포인터를 저장하는 부분입니다


헌데 데이터의 형식이 void입니다


왜 void형식으로 지정해줫을까요?


이렇게 지정해버린다면 앞에설명한대로 자료를 재대로 인식할수 없을텐데?


생각해봅시다.


자료의 형태를 노드를 선언할때 지정해버리게되면


여러가지의 데이터를 사용할수없게됩니다.


즉 이 노드의선언이 한번씌여지고 다른때 씌여질수없다는 문제가 생깁니다.


그래서 이부분은 void형태로 지정해주고


데이터를 사용해야할때 강제형변환을통해


데이터를 연산해주면 이문제가해결됩니다.


물론 자료의 형태를 지정해 사용해도 문제는없습니다.


다만 노드의 재활용성을위해 void형으로 선언했다고 말씀드리고싶습니다,


(이부분에 대해 자세히 알고싶으신분은 http://killernet.egloos.com/2378008

를 참조하시면 될것같습니다.)




그럼이제 이 노드를 어떻해 활용하면될까요?


일단 노드를생성해서 구조체 개체들에게 값을 지정해주는 일을 해야겠죠?


노드를 생성하는 함수를 구현해봅시다



<h3>노드생성 함수</h3>


일단 함수의 선언부분에대해 생각해봅시다.

이 함수는 리턴형태는 node 형태의 포인터 주소겟죠?

함수의 이름은 CreateNode 로짓겟습니다 



struct Node* CreateNode



이제 이함수는 무엇을 인자로 받아야할까요?


이 함수의 역활에대해 생각해봅시다


이함수는 노드를생성해 그 생성된노드의 주소를 반환해주면됩니다


함수구현에 무엇이필요할까요?


다음노드의주소


전노드의 주소


데이터의주소


여기서


다음노드의주소,전노드의주소는 노드를 연결하는 부분에서 지정해주면 될것입니다.


저장될 데이터의주소는 어떻해얻을수잇을까요?



이제 인자로 데이터의 주소를 넘겨받아봅시다


struct Node* CreateNode(void*  data)



이제 메모리 동적할당을통해 새로운 메모리를 부여받아봅시다.


이 메모리주소의 이름은 NewNode 라 짓겟습니다


struct Node *NewNode=(struct node *)malloc(sizeof(struct node));


이렇게 선언하면 NewNode 란이름에 노드크기로 메모리 주소가 들어가게됩니다.


이제 인자로 넘겨받은 데이터를 동적할당한 NewNode에 넣어줍시다


NewNode->data=data;


(여기서 -> 연산자는 참조연산자를 나타냅니다. NewNode.data=data; 로 사용해도

문제없이 컴파일됩니다.

간단히설명드리면 NewNode의 data개체를 참조해 그안에 값을 넣는다


로 이해하시면 될것같습니다.)


그리고 다음노드 주소는 아직 할당하지 않앗기떄문에 NULL값을 넣어줍시다

NewNode->next=NULL;


(여기서 NULL값이란 0으로 아무것도 없다는 뜻입니다 보통 데이터를 0으로 초기화해줄때 사용합니다. 


만약 NULL값을 지정해주지않으면 메모리상이 쓰레기값떄문에


오류가 발생할수잇습니다.)


그리고 전의 노드 주소를 저장할 변수를 선언해봅시다


struct Node* preb=NULL;


next와 마찬가지로 NULL 값을 지정해줍시다.



이제 함수의 기초구성이 완성된거같으니


리턴값에대해 생각해봅시다


리턴값은 새로할당한 노드의 주소가됩니다


그주소는 NewNode에 담겨져있습니다


이 NewNode를 리턴값으로 넘겨줍시다.


return NewNode;



이제 완성된 함수의 형태를 봅시다.


struct Node* CreateNode(void * data)

{

struct Node *NewNode=(struct Node*)melloc(sizeof(struct Node));

NewnNode->data=data;

NewNode->next=NULL;

NewNode->preb=NULL;

return NewNode;

}



이제 노드 한개를 생성할수잇는 함수가 구현됬습니다


이제 이 함수로 생성한 여러개의 노드를 연결할수잇는


함수를 구현해봅시다


<h3>노드 연결하기</h3>


일단 이함수에는 무엇이필요할까요?


연결할 두개의노드 가필요하겟지요?


하지만 생각해봅시다.


링크드리스트의 장점에대해


링크드리스트는 자료의 지속적인 추가와더불어


자료사이에 자료를 끼워 넣을수잇는 장점을 지니고 있습니다.

(혹은 그렇게 구현할수잇습니다.)



이 장점을 생각하여 함수 구현에 대해생각해보면


이 함수를 구현하는데 필요한 인자는 3가지입니다.


앞노드의 정보,새노드의 데이터정보,후노드의 정보