[자료구조] 연결리스트 (2) - 원형연결리스트

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

//L->tail 이 마지막
//L->tail의 next가 첫번째 노드 (L->tail->Link);
typedef int element;

typedef struct ListNode
{
	element data;
	struct ListNode* Link; //자기 참조 구조체 ListNode 이름으로 재정의가 12번줄 안되어있으니까 struct ListNode라고 붙인거스
}ListNode;

typedef struct
{
	ListNode* tail;
	int size; //전체 노드의 개수 count, but 삽입 삭제나 다른데서 실수가 일어나버리면 ,, 오류가 .,,
}ListType;

void init(ListType* L)
{
	L->tail = NULL;
	L->size = 0;
}

int isEmpty(ListType* L)
{
	return L->tail == NULL;
	// return L->size == 0; 둘 중에 하나만 만족해도 Empty
}

void insertLast(ListType* L, element e)
{
	//내가 가리키는 애, 나를 가리키는 애
	ListNode* node = (ListNode*)malloc(sizeof(ListNode)); //insert할 것을 만들어줌
	node->data = e;
	
	//내가 삽입될 노드가 처음일 때랑, 그렇지 않을 때를 나눠서 생각
	if (isEmpty(L))
	{
		node->Link = node; //내가 마지막, 첫 노드니까 날 가리키고
		L->tail = node; // 마지막을 가리킴
	}
	else
	{
		node->Link = L->tail->Link; //나는 내가 insertLast니까 현재 첫 노드를 가리켜야 함, 
		//현재 첫 노드는 L->tail->Link, 그럼 이제 내가마지막 노드
		//현재 마지막 노드가 내 왼편에 있
		L->tail->Link = node; //연결
		L->tail = node; //내가 이제 마지막 노드
	}
	L->size++;
}

void insertFirst(ListType* L, element e)
{
	ListNode* node = (ListNode*)malloc(sizeof(ListNode)); //insert할 것을 만들어줌
	node->data = e;

	if (isEmpty(L))
	{
		node->Link = node; 
		L->tail = node;
	}
	else
	{
		node->Link = L->tail->Link;
		L->tail->Link = node; //연결
		//insertFirst니까 내가마지막이 될 필요가 없어
	}
	L->size++;

}
void print(ListType* L)
{
	if (isEmpty(L))
		return;

	ListNode* p = L->tail->Link; //첫번째 노드를 가리킴

	for (int i = 1; i <= L->size; i++) //size 안쓰고 while문으로 돌리는 것
	{
		printf("[%d] =>", p->data);
		p = p->Link; //다음 노드로 움직임
	}
	printf("\b\b\b   \n");
}

void print2(ListType* L)
{
	if (isEmpty(L))
		return;

	ListNode* p = L->tail; //끝으로 잡기
	do
	{
		printf("[%d] =>", p->Link->data); //일단 찍고 움직이니까 마지막 것까지 출력 가능
		p = p->Link; //다음 노드로 움직임
	} while (p != L->tail); //마지막노드가 아닐때까지
	printf("\b\b\b   \n");
}

element deleteFirst(ListType* L)
{
	if (isEmpty(L))
		return -1; //의미없는 값을 리턴..

	ListNode* p = L->tail; //마지막 노드
	ListNode* q = p->Link; //첫번째 노드
	element e = q->data;
	
	if (p == q) //L의 size가 1일 때 tail이 노드를 가리키고 노드가 노드를 가리킨다 생각
		L->tail = NULL;
	else
		p->Link = q->Link;
	
	//리스트에 노드가 한개만 있을 때, 한개보다 많을 때 나눠서 생각

	L->size--;
	free(q);
	return e;
}

element deleteLast(ListType* L)
{
	if (isEmpty(L))
		return -1; //의미없는 값을 리턴..

	ListNode* p = L->tail; //마지막 노드
	ListNode* q = p->Link; //첫번째 노드
	element e = p->data;

	if (p == q) //L의 size가 1일 때 tail이 노드를 가리키고 노드가 노드를 가리킨다 생각
		L->tail = NULL;
	else
	{
		while (q->Link != p)
			q = q->Link;
		q->Link = p->Link;
		L->tail = q;
	}

	//리스트에 노드가 한개만 있을 때, 한개보다 많을 때 나눠서 생각



	L->size--;
	free(p); //이번에 없어지는건 마지막이니까
	return e;
}
int main()
{
	ListType L;
	init(&L);

	printf("InsertLast --------------\n");
	insertLast(&L, 10); print2(&L);
	insertLast(&L, 30); print2(&L);
	insertLast(&L, 20); print2(&L);

	printf("\n\nInsertFirst --------------\n");
	insertFirst(&L, 40); print(&L);
	insertFirst(&L, 60); print(&L);
	insertFirst(&L, 50); print(&L);

	printf("[%d] is deleted   ", deleteFirst(&L)); print2(&L);
	printf("[%d] is deleted   ", deleteLast(&L)); print2(&L);
	return 0;
}
//get first, last를 추가하면 deque