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

#define TRUE 1
#define FALSE 0

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

typedef struct {
 ListNode *head;   // 헤드 포인터
 int length;  // 노드의 개수
} ListType;

void init(ListType *list)
{
 list->head = NULL;
 list->length = 0;
}

ListType list1;

void insert_node(ListNode **phead, ListNode *p, ListNode *new_node)
{
 if (*phead == NULL) { // 공백리스트인 경우
  new_node->link = NULL;
  *phead = new_node;
 }
 else if (p == NULL) { // p가 NULL이면 첫번째 노드로 삽입
  new_node->link = *phead;
  *phead = new_node;
 }
 else {    // p 다음에 삽입
  new_node->link = p->link;
  p->link = new_node;
 }
}
void remove_node(ListNode **phead, ListNode *p, ListNode *removed)
{
 if (p == NULL)
  *phead = (*phead)->link;
 else
  p->link = removed->link;
 free(removed);
}

void insert_first(ListNode **phead, ListNode *node)
{
 if (*phead == NULL) {
  *phead = node;
  node->link = node;
 }
 else {
  node->link = (*phead)->link;
  (*phead)->link = node;
  *phead = node;
 }
}

void insert_last(ListNode **phead, ListNode *node)
{
 if (*phead == NULL) {
  *phead = node;
  node->link = node;
 }
 else {
  node->link = (*phead)->link;
  (*phead)->link = node;
  
 }
}

void error(char *str)
{
 printf("%s\n", str);
 exit(1);
}

int is_empty(ListType *list)
{
 if (list->head == NULL) return 1;
 else return 0;
}

int get_length(ListType *list)
{
 return list->length;
}

ListNode *get_node_at(ListType *list, int pos)
{
 int i;
 ListNode *tmp_node = list->head;
 if (pos < 0) return NULL;
 for (i = 0; i < pos; i++)
  tmp_node = tmp_node->link;
 return tmp_node;
}
// 주어진 위치에 데이터를 삽입한다.
void add(ListType *list, int position, element data)
{
 ListNode *p;
 if ((position >= 0) && (position <= list->length)) {
  ListNode*node = (ListNode *)malloc(sizeof(ListNode));
  if (node == NULL) error("메모리 할당에러");
  node->data = data;
  p = get_node_at(list, position - 1);
  insert_node(&(list->head), p, node);
  list->length++;
 }
}
void delete(ListType *list, int pos)
{
 if (!is_empty(list) && (pos >= 0) && (pos < list->length)) {
  ListNode *p = get_node_at(list, pos - 1);
  remove_node(&(list->head), p, (p != NULL) ? p->link : NULL);
  list->length--;
 }
}

element get_entry(ListType *list, int pos)
{
 ListNode *p;
 if (pos >= list->length) error("위치 오류");
 p = get_node_at(list, pos);
 return p->data;
}

void display(ListType *list)
{
 int i;
 ListNode *node = list->head;
 printf("( ");
 for (i = 0; i < list->length; i++) {
  printf("%d ", node->data);
  node = node->link;
 }
 printf(" )\n");
}

int is_in_list(ListType *list, element item)
{
 ListNode *p;
 p = list->head;  // 헤드 포인터에서부터 시작한다.
 while ((p != NULL)) {
  // 노드의 데이터가 item이면
  if (p->data == item)
   break;
  p = p->link;
 }
 if (p == NULL) return FALSE;
 else return TRUE;
}
void add_last(ListType *list, element data)
{
 ListNode *newnode;
 newnode = (ListNode *)malloc(sizeof(ListNode));
 newnode->data = data;
 if (newnode == (ListNode *)NULL) error("메모리 오류");
 insert_last(&(list->head), newnode);
 list->length++;
}
void add_first(ListType *list, element data)
{
 ListNode *newnode;
 newnode = (ListNode *)malloc(sizeof(ListNode));
 newnode->data = data;
 if (newnode == (ListNode *)NULL) error("메모리 오류");
 insert_first(&(list->head), newnode);
 list->length++;
}
int main()
{
 ListType list1;
 init(&list1);
 add(&list1, 0, 20);
 add_last(&list1, 30);
 printf("here:\n");
 display(&list1);
 add_first(&list1, 10);
 add_last(&list1, 40);
 // list1 = (10, 20, 30, 40)
 display(&list1);
 // list1 = (10, 20, 30)
 delete(&list1, 3);
 display(&list1);
 // list1 = (20, 30)
 delete(&list1, 0);
 display(&list1);
 printf("%s\n", is_in_list(&list1, 20) == TRUE ? "성공" : "실패");
 printf("%d\n", get_entry(&list1, 0));
}