원형 연결 리스트

원형 연결 리스트란 마지막 노드가 첫 번째 노드를 가리키는 리스트이다. 즉 마지막 노드의 링크 필드가 NULL 이 아니라 첫 번째 노드 주소가 되는 리스트이다. 원형 연결 리스트에서는 하나의 노드에서 다른 모든 노드로의 접근이 가능하다. 하나의 노드에서 링크를 계속 따라 가면 결국 모든 노드를 거쳐서 자기 자신으로 되돌아 올 수 있는 것이다. 따라서 노드의 삽입과 삭제가 단순 연결 리스트보다는 용이해진다는 것이다. 삭제나 삽입 시에는 항상 선행 노드를 가리키는 포인터가 필요함을 기억하라.

 

원형 연결 리스트가 특히 유용한 경우는 리스트의 끝에 노드를 삽입하는 연산이 단순 연결 리스트보다 효율적일 수 있다는 것이다. 단순 연결 리스트에서 리스트의 끝에 노드를 추가하려면 첫 번째 노드에서부터 링크를 따라서 노드의 개수만큼 진행하여 마지막 노드까지 가야한다. 그러나 만약 원형 연결 리스트에서 다음과 같이 헤드 포인터가 마지막 노드를 가리키도록 구성한다면 상수 시간 안에 리스트의 처음과 끝에 노드를 삽입할 수 있다.

 

• 이러한 원형 연결 리스트를 이용하여 리스트의 처음에 삽입하는 함수를 작성해보자. 

ListNode *insert_first(ListNode* head, element value)
{
  ListNode *node = (ListNode *)malloc(sizeof(ListNode));
  node->data = data;
  if (head == NULL) {
    head = node;
    node -> link = head;
  }
  else {
    node -> link = head->link; //(1)
    head->link = node; //(2)
  }
  return head;
}

 

• 원형 리스트의 끝에 삽입

앞의 코드에 한 문장만 추가하면 원형 연결 리스트의 끝에 삽입할 수 있다. 즉 원형 연결 리스트는 어차피 원형으로 연결되어 있으므로 어디가 처음이고 어디가 끝인지는 불분명하다. 따라서 head 의 위치만 새로운 노드로 바꿔주면 새로운 노드가 마지막 노드가 된다.

ListNode *insert_first(ListNode* head, element value)
{
  ListNode *node = (ListNode *)malloc(sizeof(ListNode));
  node->data = data;
  if (head == NULL) {
    head = node;
    node -> link = head;
  }
  else {
    node -> link = head->link; //(1)
    head->link = node; //(2)
    head = node; //여기가 이제 다른 부분
    //head 가 가르키는 노드가 마지막 노드이므로로
  }
  return head;
}