자료구조 - 원형 연결 리스트

페에지 교체 정책을 공부하다보면 사용가능한 알고리즘이 나오는데

원형 연결 리스트를 이용해서 구현 할 수 있을 것같다.

Circular Linked List

단순 연결 리스트에서 마지막 노드가 리스트의 첫 번째 노드를 가리키게 하여

리스트의 구조를 원형으로 만든 연결 리스트

 --> 단순 연결 리스트의 마지막 노드의 링크 필드에 첫 번째 노드의 주소를

 저장하여 구성

--> 링크를 따라 계속 순회하면 이전 노드에 접근 가능

---

#include "stdio.h"

#include "stdlib.h"



typedef struct Data_Node

{

	int data;

	struct Data_Node* link;

}Node;





// 연결 리스트의 시작점을 저장

Node* Head = NULL;



void Insert_Node(Node* pNode, int data);

void Delete_Node(Node* pNode, int data);

void Print(Node* pNode);



int main()

{

	Insert_Node(Head, 1);

	Insert_Node(Head, 2);

	Insert_Node(Head, 3);

	Insert_Node(Head, 4);

	Insert_Node(Head, 5);

	Insert_Node(Head, 6);

	Insert_Node(Head, 7);

	Insert_Node(Head, 8);

	Delete_Node(Head, 8);



	Print(Head);

	system("pause");



}





void Print(Node* pNode)

{

	int count = 1;

	Node* tmp_Node = pNode;

	while (tmp_Node->link != pNode)

	{

		printf("count : %d value : %d\n",count, tmp_Node->data);

		tmp_Node = tmp_Node->link;

		count++;

	}

	printf("count : %d value : %d\n", count, tmp_Node->data);

}







void Insert_Node(Node* pNode, int data)

{

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

	Node* restore_Node = pNode;

	//처음 삽입할때 

	if (Head == NULL)

	{

		Head = new_node;

		new_node->data = data;

		new_node->link = new_node;

		return;

	}



	while (restore_Node ->link != pNode)

	{

		restore_Node = restore_Node->link;

	}

	restore_Node->link = new_node;

	new_node->link = pNode;

	new_node->data = data;



}



void Delete_Node(Node* pNode, int data)

{

	Node* tmp_node = pNode;

	Node* restore_node = NULL;

	while (tmp_node ->link != pNode)

	{

		//찾는 데이터가 같으면 삭제 진행

		//해당 노드가 맞으면 

		//중간 노드 삭제 루틴

		if (tmp_node->data == data && tmp_node !=pNode)

		{

			restore_node->link = tmp_node->link;

			return;

			

		}



		//before node 저장

		restore_node = tmp_node;

		//A저장



		//back node 를 저장

		//B저장

		tmp_node = tmp_node->link;

		//C는 tmp_node-> link

	}



	//마지막 노드값일때 삭제 루틴

	if (tmp_node->data == data && tmp_node->link == pNode)

	{

		restore_node->link = tmp_node->link;

		return;

	}

	



	//첫번째 삭제 루틴

	restore_node = tmp_node;

	tmp_node = tmp_node->link;



	if (tmp_node->data == data)

	{

		restore_node->link = tmp_node->link;

		Head = tmp_node->link;

		return;

	}

}