원형 연결리스트 코드

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

typedef int element;
typedef struct node
{
        struct node* llink;
        element data;
        struct node* rlink;
}NODE;

NODE* makeNode(element);
void insertNode(NODE**,NODE *);
void deleteNode(NODE**,element);
void printList(NODE**);

int main()
{
        NODE *head =NULL;

        insertNode(&head,makeNode(10));
        insertNode(&head,makeNode(20));
        insertNode(&head,makeNode(5));
        insertNode(&head,makeNode(15));
        printList(&head);

        deleteNode(&head,30);// no item
        printList(&head); //5 10 15 20
        deleteNode(&head,15);
        printList(&head);//5 10 20
        deleteNode(&head,20);
        printList(&head);// 5 10
        deleteNode(&head,5);
        printList(&head); //10
        deleteNode(&head,10);
        printList(&head);//Empty List
        return 0;
}

NODE *makeNode(element data)
{
        NODE *newNode;
        newNode = (NODE *)malloc(sizeof(NODE));

        newNode->llink = newNode;
        newNode->data = data;
        newNode->rlink = newNode;

        return newNode;

}

void insertNode(NODE **head,NODE* newNode)
{
        NODE *p;//q 필요없음.백업할 필요없고 rlink 이런게 있으니까

        if(*head == NULL)
        {
                *head = newNode;
                return;
        }
 p = *head;

        do
        {
                if(newNode->data < p->data)
                break;
                p = p->rlink;//뒷노드로 넘기기

        }while(p !=*head);

        if(p == *head && newNode->data < p->data)

                *head = newNode;

        {
                newNode->llink = p->llink;
                newNode->rlink = p;
                p->llink->rlink = newNode;
                p->llink = newNode;
        }
}
void printList(NODE** head)
{
        NODE *p = *head;
        if(*head == NULL)
                return;
        do{
                printf("%d\t",p->data);
                p = p->rlink;
        }while(p != *head);

        printf("\n**********************************\n");
}

void deleteNode(NODE **head,element data)
{
                NODE *p;

                if(*head == NULL)
                {
                        printf("Empty List\n");
                        return;
                }

                p = *head;
                do//지우려는 노드 찾기
                {
                        if(data == p->data)
                                break;
                        p = p->rlink;
                }while(p != *head);

                if(p == *head && p->data != data) //찾으려는 노드가 없는 상황
                {
                        printf("No item\n");
                        return;
                }
                //노드가 하나밖에 존재하지 않을 때
                if(p == p->llink && p == p->rlink)
                {
                        *head = NULL;
                        free(p);
                        return;
     }
                //첫 노드 삭제
                if(p == *head)
                        *head = p->rlink;

                        p->llink->rlink = p->rlink;
                        p->rlink->llink = p->llink;

}

---

결과

5       10      15      20
**********************************
No item
5       10      15      20
**********************************
5       10      20
**********************************
5       10
**********************************
10

**********************************