[ 특징 ]
NODE와 LINK로 구분된다.
NODE : 실제의 정보를 가지고 있는 하나의 단위
LINK : 가까운 노드에 대한 위치( 주소 )를 저장하고 있다.
링크리스트는 동적인 자료구조이며, 배열은 정적인 자료구조이다.
장점 : 메모리 공간을 가변적으로 잡아 메모리 효율이 높다. 삽입과 삭제가 용이하다.
단점 : 구현이 어렵다.

[ 형태 ]



[ 메모리 할당 ]
함수 : #include
기능 : size바이트만큼 메모리를 할당하는 기능.
리턴값 : 메모리 블록을 지시하는 포인터를 리턴한다.
할당한 메모리 공간이 없으면 NULL을 리턴한다.
- 사용예
char *name;
name = ( char * )malloc( sizeof ( char ) * 10 );

char형의 크기의 열배만큼을 캐스트연산자를 이용해서 네임에 할당합니다.

[ 노드 구조체 만들기 ]
typedef struct _node {
int data;
struct _node *next
}node;

data가 노드값이며, next는 링크입니다.
 
[ 예제소스 ]
#include
#include
#include
typedef struct _node {
int data;
struct _node *next;
}NODE;
NODE *head, *tail, *pre_node;
void init()
{
head = (NODE *)malloc( sizeof(NODE) );
tail = (NODE *)malloc( sizeof(NODE) );
head->next = tail;
tail->next = tail;
}

초기화를 시킵니다. head와 tail을 만들고 head와 tail의 링크를 tail로 하는거죠. 위의 그림에서 화살표.

void insert( int data )
{
NODE *insert_node = (NODE *)malloc( sizeof(NODE) ); 삽입할 노드를 만듭니다.
NODE *current_node = head;
//tail 바로 앞까지 올수 있도록 한다.
while( current_node->next != tail )
{
current_node = current_node->next;
}

current_node->next = insert_node;
insert_node->next = tail;
insert_node->data = data;
}

삽입은 tail 바로 앞에서 이루어집니다. 그래서 tail을 찾는 것이 필요한거죠. current_node는 포인터구조체이기에 head부터 주소를 받아서 tail까지 while문을 통해 찾아나갑니다. 그리고 current_node의 next가 tail이면 삽입이 이루어질 장소이겠죠. 장소를 찾았으니 tail 바로 앞의 노드가 새로 만든 노드를 next로 삼고, 새로 만든 노드의 next를 tail로 하는거죠. 그림으로 보시면 이와 같습니다.


NODE *find( int index )
{
int count = 0;
NODE *find_node;
pre_node = head;
find_node = pre_node->next;
while( (count != index ) && ( find_node != tail ) )
{
pre_node = pre_node->next;
find_node = pre_node->next;
count++;
}
if( ( find_node == tail ) || ( index != count ) )
find_node = NULL;
return find_node;
}

삭제를 원하는 노드를 위해 그 노드를 찾는 함수입니다. 이를 위해 각 노드는 인덱스번호를 가지게 되는데 이를 이용해 검색을 하죠. 미리 pre_node를 만들어놓고( 선언부에서 ) head부터 카운트를 세면서 카운트가 인덱스와 맞으면 그 노드가 찾으려던 노드가 되는 것입니다. 그리고 결국 카운트를 세도 인덱스를 찾지 못하거나 tail까지 find_node가 가버리면 검색이 안된것이라서 NULL값을 반환합니다.


void print()
{
NODE *print_node;
int count = 0;
print_node = head->next;

while( print_node != tail )
{
printf("%d : %d n", count, print_node->data );
print_node = print_node->next;
count++;
}
}

있는거 다 뱉어내는거죠 ㅡ_ㅡ;

void all_delete()
{
NODE *delete_node;
NODE *temp;

delete_node = head->next;
while( delete_node != tail )
{
temp = delete_node; 
delete_node = delete_node->next;
free( temp ); free함수는 메모리를 해제하는 것입니다.
}
free(head);
free(tail);
}

head 다음부터 tail 앞까지 while문을 돌아 모두 해제하고 마지막에 head와 tail도 해제합니다.

void _delete( int index )
{
NODE *delete_node;
delete_node = find( index );
if( delete_node == NULL )
printf("삭제할 노드가 없습니다n");
else
{
pre_node->next = delete_node->next;
free( delete_node );
printf("%d 노드를 삭제 하였습니다n", index);
}
}
원하는 노드를 삭제합니다.  delete_node에 find함수의 리턴값을 받아서 찾게되죠. 그 후에는 NULL값이 아니라면 free함수를 이용해 해제시키면 됩니다. 그리고 삭제되는 노드의 이전 노드를 삭제되는 노드의 이후 노드에 연결시켜줍니다. fine함수에서 pre_node는 이미 삭제되는 노드의 이전 노드로 설정되어 있죠. 그림으로 보시면 이러합니다.


void main()
{
NODE *temp; 
init();
insert(1);
insert(2);
insert(3);
insert(4);
insert(5);

temp = find(4);
if( temp == NULL )
printf("오버 프로로우n");
else
printf("찾은것 %dn", temp->data );
print();
_delete( 3 );
_delete(1);
_delete(7);
print();
insert(10);
print();
all_delete();
getch();
}

메인함수인데, 여러가지를 실행합니다. 1, 2, 3, 4, 5를 삽입하였고, 인덱스4번을 찾습니다.
인덱스는 0부터 시작하므로 5번째인 5를 찾겠죠. 그리고 3, 1을 삭제하고 7은 없어서 find함수에서 반환값이 NULL이겠죠. 그래서 삭제할 노드가 없다고 나오겠고, 10을 삽입하고 프린트합니다. 실제로 실행해보시면 결과가 이렇게 나올 것입니다. 그리고 all_delete를 이용해 모든 메모리를 해제하고 실행을 종료합니다.

아, 그리고 자료구조는 데이터를 처리하는 방식입니다 ㅡ_ㅡ;

[예제프로그램]    다른 이름으로 저장하세요.

공간이 이글루보다 약간 작아서 그림이 찌그러졌는데 눌러서보세요. 죄송합니다.