자료구조 - 원형 링크드 리스트

자료구조 - 원형 링크드 리스트

단순 링크드 리스트와 비슷하지만 마지막 노드 tail가 가르키는 노드가 null이 아니고 head가 된다.

단순 링크드 리스트 : head -> node -> ... -> node -> tail -> null

원형 링크드 리스트 : head -> node -> ... -> node -> tail -> head

기본적인 list만 구현하면 여러 응용이 가능하니 가장 기본적인 구현만 함

1. 구조체 선언

링크드 리스트 구현시 hail, taill 노드를 사용하면 더 간편함

typedef struct _node{

    int value;

    struct _node * next;

}node, *nptr;

typedef struct _list{

    nptr head;

    nptr tail;                                                                            -> 마지막 노드를 가르킴

    int count;

}list;

2. list init

void init_node(list *lptr)

{

    lptr->head = NULL;

    lptr->tail = NULL;

    lptr->count = 0;

}        

3. add node

void add_node(list *lptr, int _value)

{

    node * new_node = (node*)malloc(sizeof(node));

    new_node->value = _value;

    if(lptr->head ==NULL && lptr->tail == NULL)                            -> 최초 node 추가시

    {

        new_node->next = new_node;

        lptr->head = new_node;

    }

    else

    {

        new_node->next = lptr->head;

        lptr->tail->next = new_node;

    }

    lptr->tail = new_node;

    lptr->count++;

}

4. delete node

void delete_node(list *lptr)

{

    nptr tmp = lptr->head;

    nptr remove;

    if(lptr->count <= 0)                                                            -> 추가 보다 삭제가 더 많을 경우

    {

        printf("error : out of range\n");

        return;

    }

    else if(lptr->count == 1)                                                      -> 노드가 하나일 경우 head, tail 모두 null 초기화

    {

        lptr->tail = NULL;

        lptr->head = NULL;

        lptr->count--;

    }

    else

    {

        while(tmp->next != lptr->tail)

        {

            tmp = tmp->next;

        }

        remove = lptr->tail;

        tmp->next = lptr->head;

        lptr->tail = tmp;

        free(remove);

        lptr->count--;

    }

}