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

단순 원형 연결 리스트

앞에서 단순 연결 리스트를 해보았습니다. 하지만 이번에 알아볼 것은 단순 '원형' 연결 리스트 인데요 단순 원형 연결 리스트는 단순 연결 리스트와 어떤 차이가 있을 까요? 단순 연결 리스트의 단점 부터 알아보겠습니다.

• 단순 연결 리스트 단점
  
  
• 특정 노드 검색시 대상 이전의 도드들에 대해서 검색 불가
• 검색시 항상 첫 노드부터 검색

이를 보완할 수 있는것이 단순 원형 연결 리스트 인데요. 다음은 단순 원형 연결 리스트의 특징 및 장점들입니다.

• 단순 원형 연결 리스트의 특징
  
  
• 첫 번째 노드와 마지막 노드를 가리키도록 구성
• 첫 번째 노드와 마지막 노드의 구분이 없음
• 어떤 노드의 연결 필드에서도 NULL값은 갖지 않음
• 현재 위치에서 계속해서 검색 작업을 할 수 있음

첫번 째 노드와 마지막 노드를 가리키도록 구성 한다는 것은 다음과 같이 볼 수 있습니다.

일반적으로 헤드 포인터가 마지막 노드를 가리키게끔 구성하며

head대신 tail이라고 부르기도 합니다.

단순 원형 연결 리스트 - 삽입 연산

• 마지막 노드의 링크를 첫 번째 노드로 연결하는 부분만 단순 연결과 차이가남
• 공백 리스트의 경우 : 삽입하는 노드는 리스트의 첫 번째 노드이자 마지막 노드가 되어야함

단순 원형 연결 리스트에서처음에 삽입하는 경우를 그림으로 나타내면 다음과 같이 나타낼 수 있습니다.

단순 원형 연결 리스트에서 마지막에 삽입하는 경우를 그림으로 나타내면 다음과 같이 나타낼 수 있습니다.

단순 원형 연결 리스트 - 삭제 연산

• 마지막 노드 또는 첫번째 노드를 삭제하는 경우에 뒤쪽 노드 또는 앞쪽 노드와 연결해주는 과정 빼고 단순 연결과 같음
• 주의 사항 : 노드를 가리키는 포인터가 있는 노드를 삭제할 경우에는 포인터를 옮겨줘야 함(마지막 일 경우 제외)

단순 원형 연결 리스트 - ADT

ADT의 예시입니다.  만드는 것과 같을 수도 다를 수도 있습니다. 이름 또한 마찬가지고 예시는 예시일 뿐입니다.

단순 원형 연결 리스트 - 구현

그럼 단순 원형 연결 리스트를 구현해 보겠습니다. 위에서는 head, tail 중 하나만 사용하였는데 저는 header, tailer 2개의 포인터 를 사용하여 만들었습니다. 그림처럼 만드려면 같은 소스에서 둘중 하나로 맞춰주면 위 그림과 같은 형태가 나오게 됩니다.

우선 단순원형 연결 리스트를 구현하기 위하여 노드와 노드를 묶어줄 껍데기인 List 구조체를 만들어 주었습니다.

typedef struct ListNode
{
    int VALUE;
    struct ListNode *Link;
}ListNode;
 
typedef struct List
{
    ListNode *header;//제일 처음 노드를 가리킴
    ListNode *tailer;//제일 마지막 노드를 가리킴
}List;

노드자체는 전과 다를 것이 없지만 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)

전에 했던 단순 연결 리스트와 같습니다.

1. 제일 앞 노드 추가
   
   

   void Add_first(List *Target_List, int Item)
   {
       ListNode *New = (ListNode *)malloc(sizeof(ListNode));//새로 값을 넣을 곳
       if (Target_List->header == NULL)
       {
           Target_List->header = New;
           Target_List->tailer = New;
           New->VALUE = Item;
           New->Link = Target_List->tailer;
           return;
       }
       if (Target_List->header != NULL)
       {
           New->Link = Target_List->header;
           New->VALUE = Item;
           Target_List->header = New;
           Target_List->tailer->Link = Target_List->header;
           return;
       }
   }

   첫 노드를 더할 때는 전과 조금 달라 졌습니다. 바로 첫 노드를 만들 때 부터 연결을 잡아 주는건데요. 첫 노드를 만들고 그 다음 노드를 첫 노드가 될 수 있도록 만들어 줍니다.
   
   

2. 노드 추가
   
   

   void Add(List *Target_List, int POSITION, int item)
   {
       if (POSITION == 1)
       {
           Add_first(Target_List, item);
       }
       int pos = 1;
       ListNode *Cur = Target_List->header;
       ListNode *New = (ListNode *)malloc(sizeof(ListNode));
       while (pos > POSITION - 1)
       {
           Cur = Cur->Link;
           pos++;
       }
       New->VALUE = item;
       New->Link = Cur->Link;
       Cur->Link = New;
   }

   단순 연결 리스트와 완전히 같습니다.(사실 엄밀히 보면 예외 사항 몇개를 더 추가하는 것이 맞긴 하지만 여기서는 제외했습니다.)
   
   

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);
   }

   단순 연결 리스트와 완전히 같습니다.(사실 엄밀히 보면 예외 사항 몇개를 더 추가하는 것이 맞긴 하지만 여기서는 제외했습니다.)
   
   

4. 리스트 초기화
   
   

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

   단순 연결 리스트와 같으나 tailer 포인터를 초기화 하는 것만 추가됐습니다.
   
   

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 != Target_List->header)
       {
           if (Cur->VALUE == item)
           {
               printf("%d 번째 노드에 %d가 있습니다.\n", i, item);
           }
           i++;
           Cur = Cur->Link;
       }
   }

   단순 연결 리스트와 같지만 단순연결 리스트에서는 NULL을 만날 때 까지 진행했다면 이번에는  header를 다시 만날때 까지로 바뀌었습니다.
   
   

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);
   }

   단순 연결 리스트와 같습니다.
   
   

8. 총 길이 구하기
   
   

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

   단순 연결 리스트와 같습니다.
   
   

9.  비어 있는지 확인
   
   

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

   헤더를 조사하여 NULL값일 경우 리스트가 비었음을 판단합니다.
   
   

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

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

        리스트 내의 모든 데이터를 출력합니다. 단순 연결 리스트와 비교해서 루프 끝내는 조건이 헤더와 같은 때라는 점 빼고는 같습니다.

같이 보기

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

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

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

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

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

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