[Data Structure] 원형 연결 리스트(circular linked list)

---

원형 연결 리스트

 

 

노드 링크로 다음 노드를 가리키게만 하여 끝에 가면 NULL을 가리키게 되는 단일 연결 리스트는 자신을 가리키는 노드에는 접근할 수 없다는 단점이 있다. 예를 들어 세 번째 노드에서는 두 번째 노드로 접근할 수 없다.

이를 해결하기 위해 가장 끝 노드가 처음 노드를 가리키게 하여 원형으로 리스트를 구현하는 방법이 있다. 이를 원형 연결 리스트라 하며, 원형 연결 리스트에서는 어떤 노드에서든 다음 노드를 향해 가기만 하면 연결된 모든 노드에 도달 가능하다.

기본적인 연산은 연결 리스트와 같지만, 헤드 포인터가 가리키는 곳이 마지막 노드이고, 헤드 포인터의 링크가 가리키는 곳이 시작 노드라는 점이 단일 연결 리스트와 차이이다.

 

---

구현 | C

 

연결 리스트 구현과 같이 구현하였다. 단 앞서 말한 바와 같이 헤드 포인터는 마지막 노드를 가리키고, 헤드 포인터의 링크가 시작 노드를 가리킨다.

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

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

typedef struct {
    Node* head;
    int length;
} LinkedList;

void init(LinkedList* L) {
    L->head = NULL;
    L->length = 0;
}

int is_empty(LinkedList* L) {
    return L->length == 0;
}

int get_length(LinkedList* L) {
    return L->length;
}

void insert(LinkedList* L, int pos, element item) {
    if (pos < 0 || pos > L->length) {
        printf("Invalid location\n");
        return;
    }
    Node* node = (Node*)calloc(1, sizeof(Node));
    node->data = item;
    if (is_empty(L)) {
        L->head = node;
        L->head->link = node;
    } else if (pos == 0) {
        node->link = L->head->link;
        L->head->link = node;
    } else if (pos == L->length) {
        node->link = L->head->link;
        L->head->link = node;
        L->head = node;
    } else {
        Node* pre = L->head;
        for (int i = 0; i < pos; i++) {
            pre = pre->link;
        }
        node->link = pre->link;
        pre->link = node;
    }
    L->length++;
}

void insert_first(LinkedList* L, element item) {
    insert(L, 0, item);
}

void insert_last(LinkedList* L, element item) {
    insert(L, L->length, item);
}

void delete(LinkedList* L, int pos) {
    if (pos < 0 || pos >= L->length) {
        printf("Invalid location\n");
        return;
    }
    Node* removed;
    if (L->length == 1) {
        removed = L->head;
        L->head = NULL;
    } else if (pos == 0) {
        removed = L->head->link;
        L->head->link = removed->link;
    } else {
        Node* pre = L->head;
        for (int i = 0; i < pos; i++) {
            pre = pre->link;
        }
        removed = pre->link;
        pre->link = removed->link;
    }
    free(removed);
    L->length--;
}

void delete_first(LinkedList* L) {
    delete(L, 0);
}

void delete_last(LinkedList* L) {
    delete(L, L->length - 1);
}

element get_entry(LinkedList* L, int pos) {
    if (pos < 0 || pos >= L->length) {
        printf("Invalid location\n");
        return -1;
    } else if (pos == L->length - 1) {
        return L->head->data;
    } else {
        Node* current = L->head->link;
        for (int i = 0; i < pos; i++) {
            current = current->link;
        }
        return current->data;
    }
}

void print_list(LinkedList* L) {
    if (is_empty(L)) {
        printf("NULL\n");
    } else {
        Node* current = L->head->link;
        for (int i = 0; i < L->length; i++) {
            printf("%d -> ", current->data);
            current = current->link;
        }
        printf("First Node\n");
    }
}