C언어로 원형 연결 리스트 구현하긩

원형 연결 리스트란?

원형 연결 리스트는 마지막 노드가 첫 번째 노드를 가리키는 리스트다.

단순 연결 리스트라면 마지막 노드는 NULL을 가리키지만, 원형은 첫 번째 노드를 가리킨다.

 

장점? - 원형 연결 리스트는 원형적으로 구현되어있어 하나의 노드에서 다른 모든 노드를 접근할 수 있다.

            왜냐면, 노드를 쭉 따라다가보면 결국 모든 노드를 거쳐 자기 자신 노드로 되돌아 올 수 있기 때문에.

            그리고, 삽입 / 삭제가 단순 연결 리스트보다 간편하다. (이전 노드를 가리키는 포인터가 필요없다!)

 

 

---

원형 연결 리스트는 리스트의 끝에 노드를 삽입할 때, 

단순 연결 리스트보다 효율적이다.

단순 연결 리스트의 경우, 리스트의 끝에 노드를 삽입할 때,

첫 노드부터 링크를 따라서 끝까지 도달해야만 한다.

 

하지만! 원형 연결 리스트에서 헤드 포인터를 마지막 노드를 가리키게 한다면,

리스트의 처음과 끝에 더 빠르게 노드를 삽입하는게 가능하다.

헤드포인터로 마지막 노드를 가리킨다.

이렇게 된다면,

마지막 노드는 head가 가리키고,

첫 노드를 head->link가 가리키고 있기 때문에,

마지막에 노드 삽입을 위해서 리스트의 끝까지 엉금엉금 기어갈 필요가 없다.

---

원형 연결 리스트의 처음에 삽입

원형 연결 리스트의 처음에 노드를 삽입해보자.

위에서 말했듯이, head는 마지막 노드를 가리키게하자.

처음부분에 노드를 삽입하는 과정

이것을 함수로 작성해보자.

Node *insert_first(Node *head, element value)
{
    Node *node = (Node *)malloc(sizeof(Node));
    node->data = value;
    if(head == NULL){ //head가 NULL을 가리킨다면 비어있는 리스트
        head = node;
        node->link = head;
    }
    else{
        node->link = head->link; //새로운 노드가 head가 가르키던 것을 가르키게함
        head->link = node; //그리고 head의 링크가 새로운 노드를 가리키도록
    }
    return head; //head를 반납
}

---

원형 연결 리스트의 마지막에 삽입

마지막에 삽입하는 과정

마지막에 삽입할 때는,

head의 위치만 새로 생성한 노드로 바꿔주면 된다.

why? 우리는 head가 가르키는 것을 마지막 노드로 하기로 정했기 때문이다.

 

이것을 함수로 작성하면, 처음부분에 삽입하는 함수에서 한줄만 더 추가하면 된다.

head를 새로 생성한 노드를 가리키게 하는 것만 추가하면 됨!

Node *insert_last(Node *head, element value)
{
    Node *node = (Node *)malloc(sizeof(Node));
    node->data = value;
    if(head == NULL){
        head = node;
        node->link = head;
    }
    else{
        node->link = head->link;
        head->link = node;
        head = node; //이 부분만 추가하면 됨
    }
    return head;
}

---

출력하는 함수

void print_list(Node *head)
{
    Node *p;
    if(head == NULL){
        return;
    }
    else{
        p = head->link;
        do {
            printf("%d->", p->data);
            p = p->link;
        } while(p != head);
        printf("%d->", p->data);
    }
}

---

전체 코드 / 확인

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

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

Node *insert_first(Node *head, element value)
{
    Node *node = (Node *)malloc(sizeof(Node));
    node->data = value;
    if(head == NULL){ //head가 NULL을 가리킨다면 비어있는 리스트
        head = node;
        node->link = head;
    }
    else{
        node->link = head->link; //새로운 노드가 head가 가르키던 것을 가르키게함
        head->link = node; //그리고 head의 링크가 새로운 노드를 가리키도록
    }
    return head; //head를 반납
}

Node *insert_last(Node *head, element value)
{
    Node *node = (Node *)malloc(sizeof(Node));
    node->data = value;
    if(head == NULL){
        head = node;
        node->link = head;
    }
    else{
        node->link = head->link;
        head->link = node;
        head = node; //이 부분만 추가하면 됨
    }
    return head;
}

void print_list(Node *head)
{
    Node *p;
    if(head == NULL){
        return;
    }
    else{
        p = head->link;
        do {
            printf("%d->", p->data);
            p = p->link;
        } while(p != head);
        printf("%d->", p->data);
    }
    printf("\n");
}

int main(void)
{
    Node *head = NULL;

    head = insert_last(head, 10); //끝에 10삽입
    head = insert_last(head, 20); //끝에 20삽입
    head = insert_last(head, 30); //끝에 30삽입
    head = insert_first(head, 40); //첫부분에 40삽입
    print_list(head);

    return 0;
}