[자료구조] 원형 연결리스트(Circular LinkedList)

원형 연결리스트

- 마지막 노드가 첫번째 노드를 가리키는 리스트이다.

   선형 연결리스트는 마지막 노드가 NULL을 가리키지만

   원형 연결리스트는 첫번째 노드의 주소를 가리킨다.

 

- 이렇게 된다면 선형 연결리스트보다 삽입, 삭제가 더 쉬워진다.

   선형 연결리스트는 맨 마지막 노드에 삽입하고자 할 때

   head 노드부터 마지막 노드까지 전부 지나가야 하지만

   원형 연결리스트는 head->link에 삽입하고

   새로운 노드를 head가 되도록 하면 되므로 훨씬 쉬워진다.

 

- 노드를 맨 앞에 삽입하는 함수

//노드를 맨 앞에 삽입하는 함수
//원형 연결리스트이므로 head->link에 노드를 삽입하면 맨 앞에 삽입할 수 있다.
ListNode* insert_first(ListNode* head){
    int data;
    ListNode* new_node;
    
    printf("input data : ");
    scanf("%d", &data);
    
    new_node = create_node(data);
    
    if(head == NULL){
        head = new_node;
        new_node->link = head;
    }else{
        new_node->link = head->link;
        head->link = new_node;
    }
    
    return head;
}

 

- 노드를 맨 뒤에 삽입하는 함수

   원형 연결 리스트는 어디가 맨 앞이고 뒤인지 불분명하므로
   지금 새로 삽입된 노드가 맨 뒤인 head 포인터가 되면 된다.

   따라서 맨 앞에 삽입하는 함수에서 새로운 노드가 head라고 지정해주기만 하면 된다.

//노드를 맨 뒤에 삽입하는 함수
ListNode* insert_last(ListNode* head){
    int data;
    ListNode* new_node;
    
    printf("input data : ");
    scanf("%d", &data);
    
    new_node = create_node(data);
    
    if(head == NULL){
        head = new_node;
        new_node->link = head;
    }else{
        new_node->link = head->link;
        head->link = new_node;
        head = new_node;
    }
    
    return head;
}

 

<<전체 코드>>

 

//원형 연결리스트

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

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

//노드 생성 함수
ListNode* create_node(int data){
    ListNode* node;
    node = (ListNode*)malloc(sizeof(ListNode));
    node->data = data;
    node->link = NULL;
    
    return node;
}

//노드를 맨 앞에 삽입하는 함수
//원형 연결리스트이므로 head->link에 노드를 삽입하면 맨 앞에 삽입할 수 있다.
ListNode* insert_first(ListNode* head){
    int data;
    ListNode* new_node;
    
    printf("input data : ");
    scanf("%d", &data);
    
    new_node = create_node(data);
    
    if(head == NULL){
        head = new_node;
        new_node->link = head;
    }else{
        new_node->link = head->link;
        head->link = new_node;
    }
    
    return head;
}

//노드를 맨 뒤에 삽입하는 함수
//원형연결리스는 어디가 맨 앞이고 뒤징지 불분명하므로
//지금 새로 삽입된 노드가 맨 뒤 즉 head 포인터가 되면 된다.
ListNode* insert_last(ListNode* head){
    int data;
    ListNode* new_node;
    
    printf("input data : ");
    scanf("%d", &data);
    
    new_node = create_node(data);
    
    if(head == NULL){
        head = new_node;
        new_node->link = head;
    }else{
        new_node->link = head->link;
        head->link = new_node;
        head = new_node;
    }
    
    return head;
}

//전체 노드를 출력하는 함수
void print_node(ListNode* head){
    while(head != NULL){
        printf("%d ", head->data);
        head = head->link;
    }
    printf("\n");
}

int main(int argc, const char * argv[]) {
    ListNode* head = NULL;
    ListNode* pre_node;
    int menu;
    
    do{
        printf("========================\n");
        printf("1.insert_first 2.insert_last 3.print_node 4.end\n");
        printf("========================\n");
        printf("menu : ");
        scanf("%d", &menu);
        
        if(menu == 1){
            head = insert_first(head);
        }else if(menu == 2){
            head = insert_last(head);
        }else if(menu == 3){
            print_node(head);
        }
    }while(menu != 4);
}