[자료구조] 2. 연결리스트

링크로 연결된 연결리스트

 

2009. 10. 14 (水)

 

 

1.     연결리스트 필요성

1)     배열의 한계점

-       배열은 시작주소로부터 거리를 의하는 오프셋을 계산하여 접근하기 때문에 매우 빠르게 접근하지만 다음과 같은 한계점을 지니고 있다.

 

① 메모리 사용이 비효율적이다.

-       배열은 정적인 자료구조. 즉 배열 선언 시점에 크기가 정해지기 때문에 선언 이후에는 크기를 다시 설정되는 작업이 허용되지 않는다. 또 배열의 크기를 넘어서는 경우도 마찬가지다.

 

② 배열내의 데이터 이동 및 재구성이 어렵다

-       배열내의 데이터 이동 및 재구성이 어렵다. 즉 메모리상에 순차적으로 존재 하기 때문에 중간에서 하나 삭제하거나 삽입하면 그 부분 이후 데이터는 모두 순차적으로 이동하기 때문에 데이터의 이동 및 재구성이 어려운 것이다.

 

2.     연결 리스트 정의

1)     연결 리스트란?

위 배열의 두 한계점으로 수많은 데이터를 처리하기 위해서는 다양한 알고리즘이 존재한다.

스택, 큐, 해시 등 여러 가지가 있는데 연결리스트는 이들의 기본이 되는 자료구조이다.

연결리스트는 데이터 영역과 링크 영역으로 나누어 지는데 링크는 다음 연결리스트를 가리키고 있어 순차적으로 존재할 필요가 없다. 그래서 정적인 자료구조를 동적으로 해결할 수 있는 것이다. 하지만 배열보다는 데이터를 탐색하는 속도가 느리다.

 

2)     연결 리스트와 배열의 비교

①    장점

-       메모리를 효율적으로 사용한다

-       데이터 재구성이 용이하다.

-       대용량 데이터를 처리하는데 적합하다.

-        

②    단점

-       데이터 탐색 속도가 느리다

-       구현 및 사용 방법이 까다롭다.

 

3)     연결 리스트 종류

①    단순 연결 리스트

-       다음 노드에 대한 링크만 가지는 연결리스트

-       데이터 탐색 시 앞 방향으로만 전진

 

 

②    이중 연결 리스트

-       다음 노드 뿐만 아니라 이전 노드에 대한 링크를 포함하는 연결 리스트

-       양방향 데이터 탐색 가능

-       메모리 공간이 크다는 단점

 

 

③    환형 연결 리스트

-       머리 노드만 있고 꼬리 노드는 없다.

-       원형과 비슷하다 해서 환형 연결리스트

 

 

3.     단순 연결 리스트 구현

1)     메모리 동적 할당과 해제

-       malloc : 힙 영역에 저장 공간 할당하고 할당 영역의 주소 리턴

-       calloc : 사이즈 만큼 num 만큼 할당하고 해당 영역 0으로 초기화한 주소 리턴

-       free : 동적으로 할당된 영역 해제 즉 운영체제에 반환

 

2)     추가 기능

3)     삭제 기능

4)     검색 기능

 

(1)   소스

 

#include <stdio.h> #include <stdlib.h>   struct Node {        int nData;        Node* pLink; }; int InputData(int nMode); void InsertNode(Node* prenode, int nData); void DeleteNode(Node* prenode); int FindNode (Node* prenode, int nData); void PrintNode(Node* node); void PrintMenu();   void main() {        Node Head, Tail;        Head.nData = Tail.nData = 0;        Head.pLink = &Tail;        Tail.pLink = NULL;          int nNodeCount = 0;          int nContinue = 1;        int nFindCount = 0;        while(nContinue)        {                     PrintMenu();              int nCommandNumber;              scanf("%d", &nCommandNumber);              switch(nCommandNumber)              {                     case 1:                            InsertNode(&Head, InputData(nCommandNumber));                            nNodeCount++;                     break;                       case 2:                            if(nNodeCount)                            {                                  InputData(2);                                  DeleteNode(&Head);                                  nNodeCount--;                            }                            else                            {                                  printf("Don't exsist Node\n");                            }                     break;                       case 3:                            nFindCount = FindNode(&Head, InputData(3));                            if(nFindCount)                            {                                  printf("%d 번째위치\n", nFindCount-1);                            }                            else                            {                                  printf("존재하지않음\n");                            }                                         break;                       case 4:                            InputData(4);                            printf("현재노드수:%d \n", nNodeCount);                            PrintNode(&Head);                            printf("\n");                            break;                       case 5:                            InputData(5);                            nContinue = 0;                     break;                       default:                     break;                  }          }        } int InputData(int nMode) {        int nResult = 0;        switch(nMode)        {                   case 1:                     printf("데이터입력:");                     scanf("%d", &nResult);              break;                case 2:                     printf("데이터삭제\n");              break;                case 3:                     printf("검색할데이터입력:");                     scanf("%d", &nResult);              break;                case 4:                     printf("현재데이터상태\n");                     break;                case 5:                     printf("프로그램종료\n");                     break;                default:                     printf("잘못된입력\n");                     break;        }               return nResult; }   void InsertNode(Node* prenode, int nData) {        Node* node = (Node*)malloc(sizeof(Node));               node->nData = nData;          node->pLink = prenode->pLink;                    prenode->pLink = node; }   void DeleteNode(Node* prenode) {        Node* delnode = prenode->pLink;        prenode->pLink = delnode->pLink;        free(delnode); }   int FindNode (Node* prenode, int nData) {          static int nCount = 0;        nCount++;        Node* findnode = prenode;                 if(findnode->nData == nData)        {              int nResult = nCount;              nCount = 0;              return nResult;        }        else if(findnode->pLink == NULL)        {              nCount = 0;              return 0;        }        else        {              return FindNode(findnode->pLink, nData);        } }   void PrintNode(Node* node) {          Node* p = node;        if(p->pLink != NULL)        {              printf("[%d]->", p->nData);              PrintNode(p->pLink);                    }        else        {                     }        }     void PrintMenu() {        printf("1. 추가\n");        printf("2. 삭제\n");        printf("3. 검색\n");        printf("4. 출력\n");        printf("5. 종료\n"); }

 
(2) 결과