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

// 리스트에 담을 데이터의 자료형
typedef int element;

// 리스트의 노드 구조체
typedef struct _Node
{
    element data;        // 각 노드에 담길 자료
    struct _Node* next;  // 다음 노드
} Node;

// 원형 연결리스트의 헤더 구조체
typedef struct _CircularList
{
    Node* head;        // 리스트의 맨 앞 노드
    unsigned int size; // 리스트의 노드 개수
} CircularList;

// CircularList 헤더 구조체라는 이름이 기니깐 List라고 별명짓기
typedef CircularList List;

// 연결리스트 초기화
void List_Init(List* list)
{
    list->head = NULL;
    list->size = 0;
}

// 연결리스트의 노드를 만들어준다.
Node* List_CreateNode(Node* n, element e)
{
    n = (Node*)malloc(sizeof(Node));
    if (n == NULL)
    {
        fprintf(stderr, "malloc() failed while creating new node\n");
        exit(1);
    }
    n->data = e;
    n->next = NULL;

    return n;
}

// 리스트의 내용물과 노드개수 출력
void List_Print(List* list)
{
    printf(">> ");
    if (list->size == 0)
    {
        printf("Empty list\n");
        return;
    }

    Node* head = list->head;
    Node* i;
    for (i = head->next; i != head; i = i->next)
    {
        printf("%d -> ", i->data);
    }
    printf("%d (size: %u)\n", i->data, list->size);
    printf("------------\n");
}

// 원형 연결리스트의 맨 앞에 삽입
void List_InsertFirst(List* list, element item)
{
    Node* head = list->head;

    Node* newNode = NULL;
    newNode = List_CreateNode(newNode, item);

    if (head == NULL)
    {
        head = newNode;
        head->next = newNode;
    }
    else
    {
        newNode->next = head->next;
        head->next = newNode;
    }

    list->head = head;
    ++list->size;
}

// 원형 연결리스트의 맨 뒤에 삽입
void List_InsertLast(List* list, element item)
{
    Node* head = list->head;
    Node* newNode = NULL;
    newNode = List_CreateNode(newNode, item);

    // 빈 리스트일때
    if (head == NULL)
    {
        // 맨 앞과 뒤를 똑같이 첫 노드로 삽입
        head = newNode;
        head->next = newNode;
    }
    // 노드가 1개 이상일 때
    else
    {
        newNode->next = head->next;
        head->next = newNode;
        head = newNode;
    }
    list->head = head;
    ++list->size;
}

// 원형 연결리스트의 맨 앞의 요소 제거
element List_RemoveFirst(List* list)
{
    Node* head = list->head;
    element e = -1;

    // 빈 리스트에서는 제거할 수 없다.
    if (head == NULL)
    {
        fprintf(stderr, "Cannot remove from an empty list!\n");
        exit(1);
    }
    // 노드가 1개일때 제거하면 빈 리스트가 됨
    else if (list->size == 1)
    {
        e = head->data;
        free(head);
        head = NULL;
        list->size = 0;
    }
    else
    {
        Node* removed = head->next;
        e = removed->data;
        head->next = removed->next;
        free(removed);
        --list->size;
    }

    list->head = head;

    return e;
}


int main()
{
    List list;
    List_Init(&list);

    List_InsertFirst(&list, 10);
    List_InsertFirst(&list, 20);
    List_InsertFirst(&list, 30);

    List_InsertLast(&list, 99);
    List_InsertLast(&list, 88);
    List_InsertLast(&list, 77);

    List_Print(&list);

    printf("Removed : %d\n", List_RemoveFirst(&list));
    printf("Removed : %d\n", List_RemoveFirst(&list));
    printf("Removed : %d\n", List_RemoveFirst(&list));
    List_Print(&list);

    printf("Removed : %d\n", List_RemoveFirst(&list));
    printf("Removed : %d\n", List_RemoveFirst(&list));
    List_Print(&list);

    printf("Removed : %d\n", List_RemoveFirst(&list));
    List_Print(&list);

    return 0;
}