[자료구조론] C로 원형 연결리스트를 만들자

kysung95·2021년 5월 27일

자료구조론

목록 보기

4/11

안녕하세요. 김용성입니다.
이전 포스팅에 이어서 자료구조론 원형리스트에 대해 포스팅하고자 합니다.

원형 연결 리스트 (circular LinkedList)

원형 리스트는 말 그대로 원모양의 리스트입니다. 어떻게 연결리스트가 원 모양일 수가 있을가요?
바로 연결 리스트의 마지막 노드가 첫 번째 노드를 가리키면 됩니다.
이전 포스팅에서 설명드렸던 연결 리스트에서는 마지막 노드의 링크가 NULL 값이 되던 것을 확인하셨을텐데요. 여기서는 마지막 노드의 링크가 NULL 값이 아닌, head를 가리킵니다.
다음 그림과 같이 나타낼 수 있어요.

원형 연결 리스트의 장점은 구조 특성상 리스트의 마지막에 요소를 삽입하거나 삭제하기 위해 리스트의 맨 끝까지 가지 않아도 된다는 점입니다.

정의하는 방식은 연결리스트와 같습니다.

ListNode *head;

원형리스트 함수

구현해 볼 원형리스트 함수로는 다음과 같은 것들이 있습니다.

insert_first() : 리스트의 시작 부분에 항목을 삽입하는 함수

insert_last() : 리스트의 중간 부분에 항목을 삽입하는 함수

print_list() : 원형리스트 출력

insert_first()

원형 연결 리스트의 마지막 노드의 링크는 항상 head입니다. 그 부분만 알면 쉽게 이해할 수 있습니다.

리스트의 가장 앞부분에 노드를 삽입하는 함수입니다. 코드를 작성하기 이전에 이해를 돕기위해 사진을 먼저 보여드리도록 하겠습니다.

그림을 보시면 우리가 새로운 노드를 추가해줄 때 기존에 1이라는 데이터를 가진 head 노드가 insert_first()를 실행한 뒤에는 노드로 변경되었고 들어오는 노드가 head가 되어 있는 것을 확인할 수 있습니다. 즉, insert_first() 함수를 통해 들어온 노드는 head가 되는 것이죠.

코드로 구현하면 다음과 같습니다.

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

중간에 head==NULL인 경우를 처리해주었는데요. head가 NULL이라는 것은 기존에 데이터가 없던 리스트겠죠? 원형 연결리스트 답게 노드를 head로 변경해준 뒤 마지막 요소도 자기 자신이기 때문에 link또한 head로 설정해줍니다.

이해가 되셨나요?

insert_last()

이번에는 마지막에 요소를 삽입하는 함수를 구현해보도록 하겠습니다.
사실 달라지는 건 크게 없어요. 다만 제가 앞서 말씀드렸던 가장 중요한 개념!
원형 연결 리스트의 마지막 노드의 링크는 항상 head 라는 개념을 가지고 차근차근 접근해보면 됩니다.

그림으로 표현하면 다음과 같습니다. 사실 원형 연결리스트 자체가 어차피 원형으로 연결되어 있으므로 어디가 처음이고 어디가 끝인지는 불분명합니다.

코드는 insert_first()와 거의 유사합니다.

ListNode *insert_last(ListNode *head,element data)
{
  ListNode *node=(ListNode *)malloc(sizeof(ListNode));
  node->data=data;
  if(head==NULL){
     head=node;
     node->link=head;
  }
  else{
     node->link=head->link;
     head->link=node;
     head=node;
  }
  return head;
}

print_list()

원형 연결리스트의 출력문은 일반적인 연결리스트와 다르게 do-while 루프를 통해 구현할 수 있습니다.(물론 for문을 통해서도 구현 가능해요)
또한 마지막 노드의 링크가 NULL이 아닌 head라는 점을 알아야 합니다.


void print_list(ListNode* head)
{

    ListNode*p;

    if(head==NULL) return;
    p=head->link;
    do{
      printf("%d->",p->data);
      p=p->link;
    } while (p!=head);
    
    print("%d->",p->data);
    
}

원형 연결 리스트 구현

위에서 만든 함수들을 토대로 간단한 원형리스트 구현을 해보겠습니다.

#include <stdio.h>
#include <stdlib.h>

typedef int element;
typedef struct ListNode{
    element data;
    struct ListNode *link;
} ListNode;

void print_list(ListNode* head)
{

    ListNode*p;

    if(head==NULL) return;
    p=head->link;
    do{
      printf("%d->",p->data);
      p=p->link;
    } while (p!=head);
    
    print("%d->",p->data);
    
}

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

ListNode *insert_last(ListNode *head,element data)
{
  ListNode *node=(ListNode *)malloc(sizeof(ListNode));
  node->data=data;
  if(head==NULL){
     head=node;
     node->link=head;
  }
  else{
     node->link=head->link;
     head->link=node;
     head=node;
  }
  return head;
}


int main() {
    ListNode *head=NULL;

    head=insert_last(head,20);
    head=insert_last(head,20);
    head=insert_last(head,20);
    head=insert_first(head,20);
    print_list(head);
    
    return 0;
}