연결리스트(Linked List) - 원형(환형)

이인혁·2024년 5월 30일

자료구조

목록 보기

3/12

1. 원형 연결리스트(환형 연결리스트)

연결리스트에서 단방향과 양방향 2개를 배웠습니다. 원형은 이 둘과는 종류가 다르지만, 원형 역시 탐색을 좀 더 수월하게 하기위해서 사용하는 자료구조입니다. 원형은 말 그대로 Node의 Head와 Tail을 이어서 원처럼 만든 것입니다.

위 그림처럼 단순 연결리스트에서 Tail과 Head를 연결하면 원형 연결리스트가 됩니다.

또한, 이중 연결리스트에서 Tail과 Head를 연결하면 원형 연결리스트가 됩니다. 따라서 원형 연결리스트는 단순 연결리스트이던 이중 연결리스트이던 상관이 없습니다.

만약에 원형 연결리스트를 탐색한다고 생각해보겠습니다. Tail까지 갔을 때, 만약 주소값이 NULL일 때까지 반복한다면, 끝도 없이 계속 도는 무한루프가 형성 될것입니다. 따라서 원형 연결리스트는 항상 Node의 개수도 세주는 것이 좋습니다.

헤더파일

그럼 헤더파일을 먼저 보겠습니다.
CircularDoublyLinkedList.h

#ifndef CIRCULAR_DOUBLY_LINKEDLIST_H
#define CIRCULAR_DOUBLY_LINKEDLIST_H

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

typedef int ElementType;

typedef struct tagNode {
	ElementType Data;
	struct tagNode* PrevNode;
	struct tagNode* NextNode;
}Node;

Node* CDLL_CreateNode(ElementType NewData); ->노드를 생성하는 함수
void CDLL_DestroyNode(Node* Node); ->노드를 제거하는 함수
void CDLL_AppendNode(Node** Head, Node* NewNode); ->노드를 리스트의 헤드에 추가하는 함수
void CDLL_InsertAfter(Node* Current, Node* NewNode); ->노드를 리스트의 중간에 추가하는 함수
void CDLL_RemoveNode(Node** Head, Node* Remove); ->노드를 리스트에서 제거하는 함수
Node* CDLL_GetNodeAt(Node* Head, int Location); ->노드를 탐색하는 함수
int CDLL_GetNodeCount(Node* Head); ->노드의 개수를 반환하는 함수

#endif

헤더파일 부분은 양방향 연결리스트와 전혀 달라지지 않았습니다. 따라서 소스파일도 크게 달라지지 않았을 것으로 예상됩니다. 왜냐하면, 그냥 Tail과 Head를 이었을 뿐이기 때문이다.

소스파일

CircularDoublyLinkedList.c

#include "CircularDoublyLinkedList.h"

//노드 생성
Node* CDLL_CreateNode(ElementType NewData) {
	Node* NewNode = (Node*)malloc(sizeof(Node));

	NewNode->Data = NewData;
	NewNode->PrevNode = NULL;
	NewNode->NextNode = NULL;

	return NewNode;
}

//노드 소멸
void CDLL_DestroyNode(Node* Node) {
	free(Node);
}

//노드 추가
void CDLL_AppendNode(Node** Head, Node* NewNode) {
	//헤드 노느가 NULL이라면 새로운 노드가 Head가 된다.
	if ((*Head) == NULL) {
		*Head = NewNode;
		(*Head)->NextNode = *Head;
		(*Head)->PrevNode = *Head;
	}
	else {
		//테일과 헤드 사이에 NewNode를 삽입한다.
		Node* Tail = (*Head)->PrevNode;

		Tail->NextNode->PrevNode = NewNode;
		Tail->NextNode = NewNode;
		
		NewNode->NextNode = (*Head);
		NewNode->PrevNode = Tail;//새로운 테일의 PrevNode가 기존의 테일을 가리킨다.
	}
}

//노드 삽입
void CDLL_InsertAfter(Node* Current, Node* NewNode) {
	NewNode->NextNode = Current->NextNode;
	NewNode->PrevNode = Current;

	if (Current->NextNode != NULL) {
		Current->NextNode->PrevNode = NewNode;
		Current->NextNode = NewNode;
	}
}

//노드 제거
void CDLL_RemoveNode(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;
	}
}

//노드 탐색
Node* CDLL_GetNodeAt(Node* Head, int Location) {
	Node* Current = Head;

	while (Current != NULL && (--Location) >= 0) {
		Current = Current->NextNode;
	}

	return Current;
}

//노드 개수 세기
int CDLL_GetNodeCount(Node* Head) {
	unsigned int Count = 0;
	Node* Current = Head;

	while (Current != NULL) {
		Current = Current->NextNode;
		Count++;

		if (Current == Head) {
			break;
		}
	}

	return Count;
}

void PrintNode(Node* _Node) {
	if (_Node->PrevNode == NULL) {
		printf("Prev: NULL");
	}
	else {
		printf("Prev: %d", _Node->PrevNode->Data);
	}

	printf("Current: %d", _Node->Data);

	if (_Node->NextNode == NULL) {
		printf("Next: NULL\n");
	}
	else {
		printf("Next: %d\n", _Node->NextNode->Data);
	}
}

양방향과 바뀐부분만 찾아보겠습니다.

void CDLL_AppendNode(Node** Head, Node* NewNode) {
	if ((*Head) == NULL) {
		*Head = NewNode;
		(*Head)->NextNode = *Head;
		(*Head)->PrevNode = *Head;
	}
	else {
		Node* Tail = (*Head)->PrevNode;

		Tail->NextNode->PrevNode = NewNode;
		Tail->NextNode = NewNode;
		
		NewNode->NextNode = (*Head);
		NewNode->PrevNode = Tail;
	}
}

원래라면 처음 추가하는 if부분에서도 NULL로 초기화를 시키고, else부분에서도 앞뒤를 계속 연결해주는 코드가 나옵니다.

void CDLL_InsertAfter(Node* Current, Node* NewNode) {
	NewNode->NextNode = Current->NextNode;
	NewNode->PrevNode = Current;

	if (Current->NextNode != NULL) {
		Current->NextNode->PrevNode = NewNode;
		Current->NextNode = NewNode;
	}
}

void CDLL_RemoveNode(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 (Current->NextNode != NULL) {
		Current->NextNode->PrevNode = NewNode;
		Current->NextNode = NewNode;
	}

이 부분과

(*Head)->PrevNode->NextNode = Remove->NextNode;
		(*Head)->NextNode->PrevNode = Remove->PrevNode;

		*Head = Remove->NextNode;

Remove->PrevNode->NextNode = Remove->NextNode;
		Remove->NextNode->PrevNode = Remove->PrevNode;

이부분들이 추가됨으로써 삽입하거나 제거해도 함수의 원형을 지킬 수가 있습니다.

실행예시

메인함수를 보이고 결과까지 보여드리겠습니다.
CircularDoublyLinkedListMain.c

#include "CircularDoublyLinkedList.h"

int main() {
	int i = 0;
	int Count = 0;
	Node* List = NULL;
	Node* NewNode = NULL;
	Node* Current = NULL;

	//노드 5개 추가
	for (i = 0; i < 5; i++) {
		NewNode = CDLL_CreateNode(i);
		CDLL_AppendNode(&List, NewNode);
	}

	//리스트 출력
	Count = CDLL_GetNodeCount(List);
	for (i = 0; i < Count; i++) {
		Current = CDLL_GetNodeAt(List, i);
		printf("List[%d] : %d\n", i, Current->Data);
	}

	//리스트의 세 번째 칸 뒤에 노드 삽입
	printf("\nInserting 3000 After [2]...\n\n");

	Current = CDLL_GetNodeAt(List, 2);
	NewNode = CDLL_CreateNode(3000);
	CDLL_InsertAfter(Current, NewNode);

	printf("\nRemoving Node at 2...\n");
	Current = CDLL_GetNodeAt(List, 2);
	CDLL_RemoveNode(&List, Current);
	CDLL_DestroyNode(Current);

	//리스트 출력
	//(노드 개수의 2배만큼 루프를 돌며 환형임을 확인한다.)
	Count = CDLL_GetNodeCount(List);
	for (i = 0; i < Count * 2; i++) {
		if (i == 0) {
			Current = List;
		}
		else {
			Current = Current->NextNode;
		}

		printf("List[%d] : %d\n", i, Current->Data);
	}

	//모든 노드를 메모리에서 제거
	printf("\nDestroying List...\n");
	Count = CDLL_GetNodeCount(List);

	for (i = 0; i < Count; i++) {
		Current = CDLL_GetNodeAt(List, 0);

		if (Current != NULL) {
			CDLL_RemoveNode(&List, Current);
			CDLL_DestroyNode(Current);
		}
	}

	return 0;
}

결과

List[0] : 0
List[1] : 1
List[2] : 2
List[3] : 3
List[4] : 4

Inserting 3000 After [2]...


Removing Node at 2...
List[0] : 0
List[1] : 1
List[2] : 3000
List[3] : 3
List[4] : 4
List[5] : 0
List[6] : 1
List[7] : 3000
List[8] : 3
List[9] : 4

Destroying List...

이인혁

게임개발공부블로그

이전 포스트

연결리스트(Linked List) - 양방향

다음 포스트