[C] 원형 연결 리스트(Circular Linked List)

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

 

- 리스트의 마지막 노드의 링크가 첫 번째 노드를 가리키는 리스트.

-> 마지막 노드의 링크 필드가 NULL이 아닌 첫 번째 노드 주소가 되는 리스트.

- 한 노드에서 다른 모든 노드로의 접근이 가능하다는 장점이 있음.

- 노드이 삽입과 삭제가 단순 연결 리스트보다는 용이해짐.

- 삭제나 삽입 시에는 항상 선행 노드의 포인터가 필요함.

- 리스트의 끝에 노드를 삽입하는 연산이 단순 연결 리스트보다 효율적일 수 있음.

 

코드

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

#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 data, ListNode *link) {
    ListNode *new_node;
    new_node = (ListNode *)malloc(sizeof(ListNode));
    if (new_node == NULL) error("메모리 할당 에러");
    new_node->data = data;
    new_node->link = link;
    return(new_node);
}


// 리스트의 항목 출력 (처음 노드의 값부터 출력)
void display(ListNode *head) {
    ListNode *p;
    if (head == NULL) return;

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

// phead : 리스트의 헤드 포인터의 포인터
// node : 삽입될 노드

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

// 중간에 노드를 삽입
void insert_middle(ListNode **phead, ListNode *pre, ListNode *node) {
    if (*phead == NULL) {
        *phead = node;
        node->link = node;
    }
    else {
        node->link = pre->link;
        pre->link = node;
    }
}

// 리스트 내의 원소를 탐색
ListNode* search(ListNode *head, element x) {
    ListNode *p;
    p = head->link;
    do {
        if (p->data == x) return p;        // 탐색 성공
        p = p->link;
    } while (p != head->link);

    return NULL;        // 탐색 실패
}

// 두 리스트를 연결
ListNode* concat(ListNode *head1, ListNode *head2) {
    ListNode *p1, *p2;
    if (head1 == NULL) return head2;
    else if (head2 == NULL) return head1;
    else {
        p1 = head1->link;            // 시작 노드 주소값 저장
        p2 = head2->link;            
        head1->link = p2;            // 연결
        head2->link = p1;            // 마지막 노드 링크 필드에 첫 번째 노드 주소값 
        
        return head2;
    }
}

// 첫 번째 노드 삭제
void remove_first(ListNode **phead) {
    ListNode* removed;
    if (*phead == NULL) return;                    // 공백 리스트인 경우
    else if (*phead == (*phead)->link) {         // 노드가 하나인 경우
        removed = *phead;                        // 삭제할 노드
        *phead = NULL;                            // 공백리스트로 변경
    }
    else {                                                // 노드가 둘 이상인 경우
        removed = (*phead)->link;                // 시작 노드가 삭제될 노드
        (*phead)->link = removed->link;        // 마지막 노드의 링크 필드에 삭제할 노드 다음의 주소값 저장
    }
    free(removed);
}

// 마지막 노드 삭제
void remove_last(ListNode **phead) {
    ListNode* removed, *pre;                    // pre는 삭제할 노드의 선행자 노드
    if (*phead == NULL) return;                    // 공백 리스트인 경우
    else if (*phead == (*phead)->link) {         // 노드가 하나인 경우
        removed = *phead;                        // 삭제할 노드
        *phead = NULL;                            // 공백리스트로 변경
    }
    else {                                                // 노드가 둘 이상인 경우 (삭제할 노드의 선행자 노드를 찾아야 함)
        pre = (*phead)->link;                        // 시작 노드 주소를 먼저 저장
        while (pre->link != *phead) {            // phead의 선행자 노드 위치 탐색
            pre = pre->link;
        }
        removed = *phead;                        // phead가 삭제할 노드
        pre->link = removed->link;                // 시작 노드이 주소를 저장
        *phead = pre;                                // 선행자 노드가 마지막 노드로 변경    
    }            
    free(removed);
}

// 중간 노드 삭제
void remove_middle(ListNode **phead, ListNode *pre) {
    ListNode* removed;                    
    if (*phead == NULL) return;                    // 공백 리스트인 경우
    if (pre->link == *phead) {                     // 노드가 하나인 경우
        removed = *phead;                        
        pre->link = removed->link;
        *phead = pre;
    }
    else {                                                // 삭제할 노드가 시작 노드이거나 중간 노드인 경우
        removed = pre->link;
        pre->link = removed->link;
    }
    free(removed);
}

// 모든 노드 삭제
void remove_all(ListNode **phead) {
    ListNode* removed, *p;
    if (*phead == NULL) {
        p = (*phead)->link;                // 시작 노드 포인터 저장
        (*phead)->link = NULL;            // 단순 연결리스트로 변환
        while (p != NULL) {
            removed = p;
            printf("%d=>", removed->data);
            p = p->link;
            free(removed);
        }
    }
    printf("\n");
    *phead = NULL;        // 모든 노드 삭제 후 공백 리스트로 변경
}

// 노드 순서 반전
ListNode* reverse(ListNode *head) {
    ListNode *p, *q, *r;
    if (head == NULL || head->link = head) {        // 공백이거나 노드가 하나인 경우
        return head;
    }
    p = head->link;            // 시작 노드 주소 저장
    q = head;                    // q는 역순으로 만들 노드
    while (p != head) {
        r = q;                        // r은 역순으로 된 리스트, r은 q, q는 p를 차례로 따라감
        q = p;
        p = p->link;
        q->link = r;                // q의 링크방향을 변경
    }
    head = head->link;
    p->link = q;
    return head;
}

void main() {
    ListNode *list1 = NULL, *list2 = NULL;
    insert_first(&list1, create_node(10, NULL));
    insert_first(&list1, create_node(20, NULL));
    insert_first(&list1, create_node(30, NULL));
    insert_last(&list1, create_node(40, NULL));
    insert_last(&list1, create_node(50, NULL));
    insert_last(&list1, create_node(60, NULL));
    printf("list1 display--------------------------------------\n");
    display(list1);
    printf("\n");

    insert_middle(&list1, search(list1, 30), create_node(70, NULL));
    insert_middle(&list1, search(list1, 60), create_node(80, NULL));
    insert_middle(&list1, search(list1, 10), create_node(90, NULL));
    printf("list1 display after insert_middle----------------\n");
    display(list1);
    printf("\n");

    remove_first(&list1);
    printf("list1 display after remove_first-----------------\n");
    display(list1);
    printf("\n");

    remove_last(&list1);
    printf("list1 display after remove_last------------------\n");
    display(list1);
    printf("\n");

    remove_middle(&list1, search(list1, 20));            // 중간인 경우
    printf("list1 display after remove_middle(10)----------\n");
    display(list1);
    printf("\n");

    remove_middle(&list1, search(list1, 50));            // 첫 번째 노드인 경우
    printf("list1 display after remove_middle(50)----------\n");
    display(list1);
    printf("\n");

    remove_middle(&list1, search(list1, 40));            // 마지막 노드인 경우
    printf("list1 display after remove_middle(40)----------\n");
    display(list1);
    printf("\n");
    
    list1 = reverse(list1);
    printf("list1 display after reverse-----------------------\n");
    display(list1);
    printf("\n");
    
    insert_last(&list2, create_node(60, NULL));
    insert_last(&list2, create_node(10, NULL));
    insert_last(&list2, create_node(30, NULL));
    insert_last(&list2, create_node(50, NULL));
    printf("list2 display--------------------------------------\n");
    display(list2);
    printf("\n");

    list1 = concat(list1, list2);
    printf("list1 display after concat------------------------\n");
    display(list1);

    remove_all(&list1);
    printf("list1 display after remove_all------------------\n");
    display(list1);
    printf("\n");
}

 

내용 출처 : C언어로 쉽게 풀어쓴 자료구조 (천인국 외 지음, 생능출판사)