[C로 만드는 자료구조]리스트(List) - 단순 연결 리스트(2/2)

지난 포스팅에서 기본적인 사항과 삽입, 삭제 구현을 알아보았으니 이번에는 실제 함수 구현을 보겠습니다.

ADT는 배열에서 구현한것과 같지만 배열이 아닌 동적 할당을 통해서 만들었습니다.

우선 필요한것은 노드! 그리고 노드들을 묶어줄 녀석이 필요합니다.

typedef struct ListNode
{
    int VALUE;
    struct ListNode *Link;
}ListNode;
 
typedef struct List
{
    ListNode *header;
}List;

노드 각각을 표현하기 위한 ListNode 구조체와 노드들의 집합 즉 헤더를 나타내기 위한 List 구조체를 만들어서 이용하였습니다. 이렇게 만드는 이유는 앞에서도 설명하였듯이 리스트는 header를 이용하여 리스트 각각을 구별하게 되며 해더를 이용하여 노드들을 찾아가기 때문에 위와 같이 설정하였습니다.

이번에 구현할 ADT들은 다음과 같습니다. 제가 짠것이기 때문에 없는 기능이 있을 수도 있고 더 추가할 수도 없앨 수도 있는 것입니다.

void Add_first(List *Target_List, int Item);//제일 앞에 추가
void Add(List *Target_List, int POSITION, int item);//노드 추가
void Delete(List *Target_List, int POSITION);//특정위치 삭제
void List_Initializer(List *Target_List);//생성후 초기화
void Replace(List *Target_List, int POSITION, int item);//특정 위치 값 교체
void Find(List *Target_List, int item);//특정값 탐색
void get_entry(List *Target_List, int POSITION);//특정 위치의 값 읽기
void get_length(List *Target_List); //노드전체 길이 얻기
void is_empty(List *Target_List);//비어있는지 확인
void Printing(List *Target_List);//리스트 내 모든 데이터 출력

각 ADT들을 하나 하나 살펴 보겠습니다.

1. 제일 앞에 노드를 추가
   
   

   void Add_first(List *Target_List, int Item)
   {
       ListNode *New = (ListNode *)malloc(sizeof(ListNode));//새로운 노드 생성
       if (Target_List->header == NULL)// 비엇을 때
       {
           Target_List->header = New;
           New->VALUE = Item;
           New->Link = NULL;
           return;
       }
       if (Target_List->header != NULL)
       {
           New->Link = Target_List->header;
           Target_List->header = New;
           New->VALUE = Item;
           return;
       }
   }

   노드를 추가하기 위하여 제일먼저 할 것은 새로운 노드를 만들어 주는 것입니다. 동적할당을 통해서 만들어 줍니다. 동적 연결 리스트에서는 배열과는 다르게 처음에 넣는 것이 중요합니다. List를 생성하고 header값에 첫 노드를 가리키도록 할당해 주어야 그 다음 노드도 찾아 갈 수 있고 또 header를 통하여 List를 구별 할 수도 있기 때문입니다. 첫 단추가 잘되어야 다음 작업들이 순조롭습니다.
   
   

2. 노드 추가
   
   
   

   void Add(List *Target_List, int POSITION, int item)
   {
       if (POSITION == 1)// 첫번 째위치 추가시 위의 함수를 이용
       {
           Add_first(Target_List, item);
           return;
       }
       ListNode *New = (ListNode *)malloc(sizeof(ListNode));
       ListNode *Cur = Target_List->header;//헤더는 움직이면 안됨!
       int pos = 1;
       while (pos > POSITION - 1)
       {
           Cur = Cur->Link;
           pos++;
       }
       New->VALUE = item;
       New->Link = Cur->Link;
       Cur->Link = New;
   }

   우선 처음 추가와 특정 위치 추가는 다르기 때문에(헤더 할당 때문에 다름) 위치값 1이 들어왔을 때는 위의 함수로 넘겨 줍니다. 그 이외의 위치라면 새로 할당을 받고 Cur이라는 포인터를 선언하여 헤더 값을 받는데 그 다음을 보면 그 이유가 나옵니다. while문 안에는 Cur = Cur->Link; 를 봤을 때 만약 header를 저런식으로 옮기게 되면 상관없이 추가를 잘 해줄 지는 모르겠으나 헤더는 첫 노드를 가리키고 있지 않을 것이기 때문에 다른 변수를 선언하여서 header 값을 받아준 뒤 위와같이 행동하도록 해줍니다. pos라는 정수형 변수를 이용하여 몇번 째 노드로 갈 것인지를 지정해줍니다.
   
   

3. 특정 위치 삭제
   
   

   void Delete(List *Target_List, int POSITION)
   {
       int pos = 1;
       ListNode *Temp = NULL;
       ListNode *Cur = Target_List->header;
       while (pos < POSITION)
       {
           if (pos == POSITION - 1)
               Temp = Cur;
           Cur = Cur->Link;
           pos++;
       }
       Temp->Link = Cur->Link;
       delete(Cur);
   }

   삭제하려는 노드의 바로 앞에 있는 노드를 저장해야 한다는 것이 중요합니다. 또한 메모리 낭비를 막기 위하여 마지막에 delete를 이용하여 동적 할당 해제를 해 줍니다.
   
   

4. 초기화
   
   

   void List_Initializer(List *Target_List)
   {
       Target_List->header = NULL;
   }

   리스트를 초기화 해주는 것입니다. header 값을 초기화시켜줍니다.
   
   

5. 특정 위치의 값 교체
   
   

   void Replace(List *Target_List, int POSITION, int item)
   {
       int pos = 1;
       ListNode *Cur = Target_List->header;
       while (pos < POSITION)
       {
           Cur = Cur->Link;
           pos++;
       }
       Cur->VALUE = item;
   }

   헤더를 받은 커서를 이동시킨 후에 값만 바꿔줍니다.
   
   

6. 특정값 탐색
   
   

   void Find(List *Target_List, int item)
   {
       ListNode *Cur = Target_List->header;
       int i = 1;
       while (Cur != NULL)
       {
           if (Cur->VALUE == item)
           {
               printf("%d 번째 노드에 %d가 있습니다.\n", i, item);
           }
           i++;
           Cur = Cur->Link;
       }
   }

   일일이 하나씩 살펴보면서 같은 값이 있는지 탐색을 합니다. 몇번 째 인지를 알기위한 변수 i값을 증가시키면서 표시하여 줍니다. 위에서 변수로 나타내는 첫 위치가 왜 1부터 인지 의문을 가질 수도 있는데 이는 header는 노드가 아닌 포인터 이기 때문입니다. 탐색을 들어가면 header가 가르키는것 부터 보는데 header가 가르키는 값은 첫번째 노드입니다. 그렇기 떄문에 1부터 시작하게 됩니다. while 조건에서 NULL이 아닐 때 루프를 돌리는 이유는 단순 열결 리스트의 끝이 NULL이기 때문입니다.
   
   

7. 특정 위치의 값 읽기
   
   

   void get_entry(List *Target_List, int POSITION)
   {
       int pos = 1;
       ListNode *Cur = Target_List->header;
       while (pos < POSITION)
       {
           Cur = Cur->Link;
           pos++;
       }
       printf("%d번째에는 %d가 있습니다.\n", POSITION, Cur->VALUE);
   }

   
   특정 위치 까지 옮기기 위하여 pos라는 변수를 이용 통제하여 특정위치 까지 옮겨 값을 읽어줍니다.
   
   

8. 노드 전체 길이 얻기
   
   

   void get_length(List *Target_List)
   {
       ListNode *Cur = Target_List->header;
       int i = 1;
       while (Cur != NULL)
       {
           i++;
           Cur = Cur->Link;
       }
       printf("노드의 개수는 %d개 입니다.\n", i);
   }

   끝까지 한칸 한칸 넘길 때 마다 1씩 증가시켜서 갯수를 세게 됩니다.
   
   

9. 비어있는 지 확인
   
   

   void is_empty(List *Target_List)
   {
       if (Target_List->header == NULL)
           printf("리스트가 비었습니다.\n");
       if (Target_List->header != NULL)
           printf("리스트에 내용이 있습니다.\n");
   }

   헤더가 NULL임을 판단하여 비었는지 아닌지를 판단합니다. 포스팅 하다보니 첫 노드를 삭제하는 경우에는 Header를 NULL로 초기화 해주는 부분을 넣지 않았다는게 생각났네요;;
   
   

10. 리스트 내 모든 데이터 출력
    
    
    

    void Printing(List *Target_List)
    {
        ListNode *Cur = Target_List->header;
        printf("%d -> ", Cur->VALUE);
        Cur = Cur->Link;
        while (Cur != NULL)
        {
            printf("%d -> ", Cur->VALUE);
            Cur = Cur->Link;
        }
        printf("

    끝에 도달 하는 동안의 모든 데이터 값을 출력합니다.
    
    

단순 연결 리스트에서 중요한것은 Header를 받은 Cur을 Cur=Cur->Link; 를 통하여 다음 노드로 옮겨 간다는 것입니다. 이것 이외에는 크게 어려울 건 없을 것 같습니다.

같이 보기

2016/01/22 - [Programming/STL] - STL(Standard Template Library) - Container - List

2015/11/07 - [Programming/자료구조] - [C로 만드는 자료구조]리스트(List)- 이중 원형 연결 리스트

2015/11/07 - [Programming/자료구조] - [C로 만드는 자료구조]리스트(List)- 단순 원형 연결 리스트

2015/11/04 - [Programming/자료구조] - [C로 만드는 자료구조]리스트(List) - 단순 연결 리스트(1/2)

2015/11/04 - [Programming/자료구조] - [C로 만드는 자료구조]리스트(List) - 동적 연결 리스트

2015/11/02 - [Programming/자료구조] - [C로 만드는 자료구조]리스트(List) - 배열