- 연결리스트 -

쉽지만 어렵고도 이해하기 힘든것중에 하나 인것같다.

-단순 연결리스트
연결리스트와 동적배열은 완전히 용도가 같은 자료구조로서 서로 대체가능하지만 구성원리나 관리방법은
질적으로 다르다. 연결리스트의 대체 자료구조는 배열이 아니라 동적 배열이다.

연결리스트의 요소인 노드는 데이터 외에 연결상태에 대한 정보인 링크를 추가로 가져야 한다. 자기 다음의
요소가 누구인지를 스스로 기억하고 있어야 흩어져 있는 노드들의 순서를 알수 있는데 이 연결 정보를 저장하는
것이 바로 링크이다. 링크를 하나만 가지는 것을 단순 연결리스트라하고 두개의 링크를 가지는 것을 이중연결
리스트하고 한다. 노드를 구성하는 데이터와 링크는 타입이 다르기 때문에 노드는 이형타입의 집합체인
구조체로 정의 된다.

struct Node
{

int value; //데이터

Node *next; //링크

};

value멤버는 노드가 기억하는 정보의 실체인 데이터 이다. 배열요소 타입에 제한이 없는것처럼 연결 리스트가 저장
하는 정보의 종류에도 제한이 없으므로 노드의 데이터는 임의타입, 임의 개수로 정의할수 있다.

next멤버는 다음노드에 대한 포인터를 가지는 링크이다. Node구조체한에 다른 Node구조체의 번지정보가 포함되는데
자신에 대한 포인터를 멤버로 가지는 자기참조 구조체이므로 크기가 무한대가 되지 않는다.
이포인터가 가리키는 곳을 찾아가면 다름 노드가 저장된 곳을 알수 있다. 이런식으로 노드들이 링크를 통해 서로의
위치를 기억함으로써 물리적으로 흩어져 있어도 논리적으로는 한덩어리의 정보가 될수 있다는 것이다.

단, 어떤 노드가 연결리스트의 첫번째 노드인지 따로 저장 해야하는데 시작점을 기억하는 노드를 머리(head)라고 한다.
일단 head는 언제든지 참조할수 있는 전역 변수로 선언하는것이 보통이다.

예)

#include <h>

 

// 노드 구조체

struct Node

{

     int value;

     Node *next;

};

Node *head;

 

// 연결 리스트 초기화 - 머리를 할당한다.

void InitList()

{

     head=(Node *)malloc(sizeof(Node));

     head->next=NULL;

}

 

// Target 다음에 노드를 삽입한다.

Node *InsertNode(Node *Target,Node *aNode)

{

     Node *New;

 

     New=(Node *)malloc(sizeof(Node));

     *New=*aNode;

 

     New->next=Target->next;

     Target->next=New;

     return New;

}

 

// Target 다음 노드를 삭제한다.

BOOL DeleteNode(Node *Target)

{

     Node *Del;

 

     Del=Target->next;

     if (Del==NULL) {

          return FALSE;

     }

     Target->next=Del->next;

     free(Del);

     return TRUE;

}

 

// 연결 리스트의 모든 노드와 머리를 해제한다.

void UnInitList()

{

     while (DeleteNode(head)) {;}

 

     free(head);

     head=NULL;

}

 

void main()

{

     int i;

     Node *Now,Temp;

 

     InitList();

 

     // 다섯 개의 노드 삽입

     Now=head;

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

          Temp.value=i;

          Now=InsertNode(Now,&Temp);

     }

 

     // 두 번째 노드 삭제

     DeleteNode(head->next);

 

     // 순회하면서 출력

     for (Now=head->next;Now;Now=Now->next) {

          printf("%d\t",Now->value);

     }

     printf("\n");

 

     UnInitList();

}