[Data Structure] #1-3 원형 연결리스트

원형 연결리스트 (Circular Linked-List)

 원형 연결리스트는 #2에서 다뤘던 연결 리스트와 아주 유사하다. 다른 점이라면 맨 끝의 노드가 다시 가장 처음 노드를 가리킨다는 점이다. 사실 원형이기 때문에 무엇이 head 인지 명확히 정할 수는 없다. 다만 여기서는 가장 마지막 노드를 head가 가리키도록 한다. 왜 그럴까? 

 생각해보자. 원형이라서 그냥 연결리스트보다 좋은 점이 대체 뭘까? 어차피 연결리스트이기 때문에 어떤 노드를 찾으려면 처음부터 뒤져야 하고 삽입이나 삭제시에도 결국 처음부터 모두 뒤져야 한다. 원형이라고 다를게 없지 않은가? 하지만 head가 마지막 노드를 가리키게 되면 이야기가 달라진다.

 head 포인터가 마지막 노드를 가리키게 되면 사용자가 마지막 index에 넣고 싶을 때 모두 노드를 거치지 않아도 된다. 또한 처음 index에 넣고자 할 때에도 head 포인터는 한 노드만 건너가면 처음 index에 삽입이 가능해진다. (삭제도 마찬가지) 바로 이 점 때문에 원형 연결리스트를 사용한다.

 그럼 코드를 함께 보도록 하자.

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

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

void error(char* message) {
    fprintf(stderr, "%s\n",message);
    exit(1);
}

ListNode* create_node(element item){
    ListNode *new_node;
    new_node = (ListNode*) malloc(sizeof(ListNode));
    new_node->link = NULL;
    new_node->data = item;
    return new_node;
}

void display(ListNode *head){
    ListNode *p;
    if(head == NULL) return;

    // 현재 head가 마지막 노드를 가리키고 있기 때문에
    // head를 처음 index로 옮긴다
    // 참고로 head를 더블포인터로 받지 않았기 때문에 head의 변경은 없다는 점을 알고 가자.

    head = head->link; 
    p = head;
    do {
        printf("%d->",p->data);
        p = p->link;
    } while (p != head);
    
    printf("\n");
}

void insert_first(ListNode **phead, ListNode *node){
    if (*phead == NULL) {
        *phead = node;
        node->link = node;
    } else {
        node->link = (*phead)->link;
        (*phead)->link = node;
    }
}

void insert_last(ListNode **phead, ListNode *node){
    if(*phead == NULL){
        *phead = node;
        node->link = node;
    }else{
        node->link = (*phead)->link;
        (*phead)->link = node;
        *phead = node; // insert node와 다른 점은 이 코드뿐이다.
    }
}

 여기서 유심히 봐야하는 코드는 insert다. 설명을 위해 insert_last를 보면.. 먼저 new_node가 head의 다음 노드를 가리키도록 한다. head의 다음 노드가 무엇인가? 위에서 설명했다시피 head는 마지막 노드를 가리킨다. 그런데 원형이다. 그러면 head의 다음 노드는 가장 첫 노드가 된다. 이 노드를 new_node가 가리키도록 하는 것이다. 그리고나면 head가 다시 new_node를 가리키도록 해서 new_node가 head 다음에 안착하도록 한다. 이제 new_node가 마지막 노드가 되었기 에 head를 new_node로 바꾼다.