환형 연결 리스트(Circular Licked List), 원형 연결 리스트, C언어 구현, 코드 부에궹ㄱ

들어가기 앞서

뭐야 내사진 언제찍힘?

 

오늘은 환형 연결 리스트를 알아볼건데요.

그냥 이중 연결 리스트있죠?

혹시 기억 안나세요?

https://8ehrmin.tistory.com/6

이중 연결 리스트(Double Linked List), C언어 구현, 코드

 

 

그거랑 똑같은데 헤드랑 테일만 달라진거에요.

 

헤드와 테일은 각각 모(毛)자란점이 하나씩 있었어요.

헤드는 이전 노드가 없다.

테일은 다음 노드가 없다.

 

근데 환형 곧 쒀클은 뒁글뒁글 하게 생겼잖아요?

따라서 헤드의 이전 노드를 테일로

테일의 다음 노드를 헤드로 채워주면, 쒀클 릥크드 리스트가 되는겁니다.

 

그럼 대체 왜?!??????????? 굳이? 써야하나 생각할 수 있는데요.

저희 테일 노드까지 가려면 징검다리 건너듯 하나씩 노드를 건너가야 테일 노드를 알 수 있었습니다.

 

테일 노드가 100번째라면 100번 건너가야 알 수 있는거죠.

다리가 많이 아프겠죠?

 

따라서 환형 써클을 사용으로써 테일에 접근하는 비용을 줄일 수 있게 되는겁니다.

 

그렇다면 추가 및 삭제 연산을 제외하고는 모두 동일하게 됩니다.

 

따라서 다른 연산과정에 대한 설명을 보려면 연결 리스트서 부터 이중 연결 리스트까지 보고 와주시면 됩니다. ^^7

https://8ehrmin.tistory.com/6 

이중 연결 리스트(Double Linked List), C언어 구현, 코드

 

https://8ehrmin.tistory.com/5

Linked List (C언어), 연결 리스트 C언어 구현, 코드(너 ㅋ 이해하고 싶어?)

 

---

Circular Linked List(환형 연결 리스트)

 

리스트를 구성하고 있는 노드 중에서, 맨 마지막과 맨 처음에 있는 노드 사이에 링크가 존재하는 리스트 (네이버)

 

환형 연결 리스트라고도 불리면서 원형 연결 리스트라고 불리우는 이 리스트는, 헤드와 테일이 더 이상 외톨이가 아니라는 것 입니다.

 

 

 

이렇게 되면, 이전과는 다르게 시작을 알면 끝을 알 수 있고, 끝을 알면 시작을 알 수 있다는 점 입니다.

즉 tail에 접근하기 위한 비용이 거의 없는 것과 다름이 없다고 볼 수 있습니다.

 

---

노드 추가 연산

노드 추가 연산 : 노드를 Tail 노드 뒤에 추가하는 연산 

 

이전 추가 연산에서는, tail까지 찾기 위하여 다음 노드가 NULL 인 노드(테일)을 찾기 위한 루프문이 있었습니다.

하지만 해당 루프문이 이제 필요 없게 되었죠?

 

따라서 이제 쉽게, 테일과 헤드 사이에 새 노드를 삽입한다라고 생각하면 되겠습니다.

 

---

void appendNode_CLL(Node** head, Node* newNode)
{
	//head가 없다면, 추가되는 노드가 head가 된다. 
	if ((*head) == NULL)
	{
		*head = newNode;
		(*head)->nextNode = *head;
		(*head)->prevNode = *head;
	}
	else
	{
		//tail과 head 사이에 newNode를 삽입한다.
		Node* tail = (*head)->prevNode;

		tail->nextNode->prevNode = newNode;
		tail->nextNode = newNode;

		newNode->nextNode = (*head);
		newNode->prevNode = tail;
	}
}

---

 

if문을 먼저 보겠습니다.

head가 null이라는 말은, 이미 만들어진 list가 없는 상황입니다.

따라서 newNode가 리스트의 첫번째 노드가 됨으로써 모두 나를 가리키는 포인터를 취하게 됩니다.

 

if ((*head) == NULL)
{
	*head = newNode;
	(*head)->nextNode = *head;
	(*head)->prevNode = *head;
}

---

 

나머지 else문을 보겠습니다.

 

간단하게 차례대로 설명 해 볼까요?

1) tail 노드를 찾는다.

 

2) head 노드의 prevNodePointer가 newNode를 가리키게 한다. 

3) 기존 tail 노드의 nextNodePoiner가 newNode를 가리키게 한다.

 

4) newNode의 nextNodePoiner가 head를 가리키게 한다.

5) newNode의 prevNodePointer가 기존 tail 노드를 가리키게 한다.

 

 

즉 기존 노드들을 newNode로 가리키게 한 다음, newNode의 포인터를 수정하였습니다.

 

환형 연결 리스트의 장점인 head 뒤에는 무조건 tail이라는 특징을 사용함으로써, tail을 찾는 loop문이 없이 수행할 수 있는 코드를 볼 수 있습니다.

 

else
{
	Node* tail = (*head)->prevNode; 	// 1)

	tail->nextNode->prevNode = newNode; //2)
	tail->nextNode = newNode; 			//3)

	newNode->nextNode = (*head); 		//4)
	newNode->prevNode = tail; 			//5)
}

 

---

노드 삭제 연산

 

노드를 삭제하는 것 또한 이전에 배웠던 삭제 연산과 비슷합니다.

하지만 추가 된 것은?

head가 가리키고 있는 tail이라는 정보

tail이 가리키고 있는 head라는 정보가 있기 때문에,

 

내 자신이 head이고 이를 삭제하기 위해서는 추가적으로 수행해야하는 적은 코드가 있습니다.

 

---

void removeNode_CLL(Node** head, Node* remove)
{
	if ((*head) == remove)
	{
		(*head)->prevNode->nextNode = remove->nextNode;
		(*head)->nextNode->prevNode = remove->prevNode;

		*head = remove->nextNode;

		remove->prevNode = NULL;
		remove->nextNode = NULL;
	}
	else
	{
		remove->prevNode->nextNode = remove->nextNode;
		remove->nextNode->prevNode = remove->prevNode;

		remove->prevNode = NULL;
		remove->nextNode = NULL;
	}
}

---

if문 조건만 보겠습니다.

 

내 자신이 곧 head이라면?

다음 노드에게 head를 수여하면서 내 정보들을 주변 노드에게 전달해야 할 것입니다.

이 다음 head가 가리키는 pointer들도 지워줘야 겠죠?

괜찮아요.. 저는 정말 괜찮아요..

 

if ((*head) == remove)
{
	(*head)->prevNode->nextNode = remove->nextNode;
	(*head)->nextNode->prevNode = remove->prevNode;

	*head = remove->nextNode;

	remove->prevNode = NULL;
	remove->nextNode = NULL;
}

---

Circular Linked List 예제 프로그램

 

지금까지 배운 연산을 모두 활용할 수 있는 프로그램을 작성해 보겠습니다.

 

#include<stdio.h>
#include<stdlib.h>
#pragma warning(disable:4996)

extern void printBar();

typedef int elementType;

typedef struct tagNode
{
	elementType data;
	struct tagNode* nextNode;
	struct tagNode* prevNode; // 얘만 추가

} Node;

Node* createNode_CLL(elementType newData)
{
	Node* newNode = (Node*)malloc(sizeof(Node));

	newNode->data = newData;
	newNode->nextNode = NULL;
	newNode->prevNode = NULL;

	printf("[%d]노드 생성 완료..\n", newNode->data);
	return newNode;
}

void destroyNode_CLL(Node* node)
{
	printf("[%d]노드 해제 완료..\n", node->data);
	free(node);
}

void appendNode_CLL(Node** head, Node* newNode)
{
	//head가 없다면, 추가되는 노드가 head가 된다. 
	if ((*head) == NULL)
	{
		*head = newNode;
		(*head)->nextNode = *head;
		(*head)->prevNode = *head;
	}
	else
	{
		//tail과 head 사이에 newNode를 삽입한다.
		Node* tail = (*head)->prevNode;

		tail->nextNode->prevNode = newNode;
		tail->nextNode = newNode;

		newNode->nextNode = (*head);
		newNode->prevNode = tail;
	}
}



Node* getNodeAt_CLL(Node* head, int location)
{
	Node* current = head;

	while (current != NULL && (--location) >= 0)
	{
		current = current->nextNode;
	}

	return current;
}

void removeNode_CLL(Node** head, Node* remove)
{
	if ((*head) == remove)
	{
		(*head)->prevNode->nextNode = remove->nextNode;
		(*head)->nextNode->prevNode = remove->prevNode;

		*head = remove->nextNode;

		remove->prevNode = NULL;
		remove->nextNode = NULL;
	}
	else
	{
		remove->prevNode->nextNode = remove->nextNode;
		remove->nextNode->prevNode = remove->prevNode;

		remove->prevNode = NULL;
		remove->nextNode = NULL;
	}
}

void insertAfter_CLL(Node* current, Node* newNode)
{
	newNode->nextNode = current->nextNode;
	newNode->prevNode = current;

	if (current->nextNode != NULL)
	{
		current->nextNode->prevNode = newNode;
		current->nextNode = newNode;
	}

	printf("[%d] -> [%d]\n", current->data, newNode->data);
}

int getNodeCount_CLL(Node* head)
{
	int count = 0;
	Node* current = head;

	while (1)
	{
		count++;
		if (current->nextNode == head) break;
		current = current->nextNode;
		
	}
	return count;
}

void main()
{
	Node* list = NULL;
	Node* newNode = NULL;
	Node* current = NULL;

	int count = 0;


	printBar();
	printf("원형 연결 리스트의 노드 개수를 입력 해 주세요 : ");
	int nodeNum;
	scanf("%d", &nodeNum);

	//노드 생성
	printBar();
	for (int i = 0; i < nodeNum; i++)
	{
		appendNode_CLL(&list, createNode_CLL(i + 1));
	}

	//노드 추가
	printBar();
	printf("노드 추가 생성 중 입니다..\n");
	count = getNodeCount_CLL(list);
	appendNode_CLL(&list, createNode_CLL(count + 1));

	//노드 중간에 추가 
	printBar();
	printf("노드를 중간에 삽입 중 입니다..\n");
	
	count = getNodeCount_CLL(list);
	int mid = 0;
	if (count > 1) mid = 1;

	Node* midNode = getNodeAt_CLL(list, mid);
	newNode = createNode_CLL(10);
	insertAfter_CLL(midNode, newNode);


	// 노드들 출력
	printBar();
	printf("노드를 출력 중 입니다..\n");
	count = getNodeCount_CLL(list);
	for (int i = 0; i < count; i++)
	{
		current = getNodeAt_CLL(list, i);
		printf("[%d번째]노드 데이터 : %d\n", i + 1, current->data);
	}


	//노드 제거
	printBar();
	printf("노드를 해제 합니다..\n");
	count = getNodeCount_CLL(list);
	for (int i = 0; i < count; i++)
	{
		current = getNodeAt_CLL(list, 0);
		if (current != NULL)
		{
			removeNode_CLL(&list, current);
			destroyNode_CLL(current);
		}

	}
}

 

아 이전 코드에서, 변경된 점이 하나 더 있습니다.

 

바로 getCount인 노드 개수를 리턴받는 함수입니다.

이전에는 다음 노드가 NULL이라면이라는 tail의 특징으로 끝을 알 수 있었지만, 현재는 tail이 head를 가리키고 있는 상황이라 변경 해 주어야 합니다.

 

따라서 제가 준 조건은, 순환을 도는 Node의 nextNodePointer가 Head를 가리킨다면 즉 tail이라면?

while문을 탈출하라는 코드를 작성하였습니다.

 

어지럽네요.

---

 

 끝으로 

뭐 이전 게시물들을 보고 오셨다면 쉬웠을 것 이라고 생각합니다.

하지만 겸손해야겠죠?

 

틀린 점이 있다면 알려주세요

 

이해 안가는 부분이 있다면 장문으로 물어도 좋으니 언제든 물어봐주시길 바랍니다.

 

참고

이것이 자료구조 알고리즘이다 with C언어