JArchive 프로그래밍 일기

환형 링크드 리스트 

환형 링크드 리스트도 더블 링크드 리스트와 비슷합니다. 

유의할 점은 테일의 다음 노드 포인터가 헤드를 가리키게 하면 됩니다. 

이것 빼고는 더블 링크드 리스트와 똑같습니다. 그래서 노드 추가, 삭제만 살펴볼 것입니다. 

테일의 다음이 헤드이고, 헤드의 앞이 테일이기 때문에 "뒤"부터 검색할 수도 있습니다!

그래서 탐색과 추가 기능의 성능을 개선할 수 있습니다. 

환형 더블 링크드 리스트의 주요 연산 

유의할 점은 다음 두 가지 입니다. 

첫 번째, 테일은 헤드의 '앞 노드'이다. 
두 번째, 헤드는 테일의 '뒷 노드'이다. 

노드 추가 

void AppendNode(Node** head, Node* newNode) {
	printf("[AppendNode] %d를 추가합니다. \n", newNode->data);

	if (NULL == (*head)) { // 헤드가 비었다면 뉴 노드가 헤드
		
		(*head) = newNode;
		(*head)->nextNode = (*head);
		(*head)->prevNode = (*head);

	}
	else { // 테일과 헤드 사이에 뉴노드 삽입 

		// 뉴노드의 다음은 헤드, 뉴노드 이전은 테일 
		newNode->nextNode = (*head);
		newNode->prevNode = (*head)->prevNode;

		// 기존테일의 다음노드가 뉴노드.
		(*head)->prevNode->nextNode = newNode;
		// 뉴노드가 새로운 테일이 된다.
		(*head)->prevNode = newNode;

	}
}

리스트 출력 (do-while 이용)

환형 리스트 이므로, while 조건문에 유의하여 리스트를 출력했습니다. 

void PrintList(Node* list) {
	printf("[PrintList] 리스트 전체를 출력합니다. \n");

	Node* current = list;

	do {
		printf("%3d", current->data);
		current = current->nextNode;
	} while (current->nextNode != list->nextNode);

	printf("\n");
}

노드 탐색 

인덱스를 입력하여 노드의 주소를 리턴합니다. 

Node* GetLocation(Node* head, int location) {
	printf("[GetLocation] %d번째 노드를 찾아보자. \n", location);

	Node* current = head;

	while ((--location) >= 0) {
		//printf("location : %d 번째 탐색 \n", location);
		current = current->nextNode;
	}

	return current;
}

노드 삭제 

RemoveNode() 함수는 특정 주소에 있는 노드를 삭제합니다. 

void RemoveNode(Node** head, Node* target) {
	printf("[RemoveNode] %d를 삭제합니다. \n", target->data);

	if ((*head) == target) {
    	// 헤드의 앞뒤 노드의 포인터를 갱신  
		(*head)->prevNode->nextNode = (*head)->nextNode;
		(*head)->nextNode->prevNode = (*head)->prevNode;

		// 헤드를 갱신 
		(*head) = (*head)->nextNode;
	}
	else {
    	// 타겟의 앞뒤 노드의 포인터를 갱신 
		target->prevNode->nextNode = target->nextNode;
		target->nextNode->prevNode = target->prevNode;
	}

	// 타겟 메모리해제 
	target->nextNode = NULL;
	target->prevNode = NULL;
	free(target);
}

전체 코드 입니다. 

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

// 환형 링크드 리스트  

/* 노드 정의 */
typedef struct Node {
	int data;
	struct Node* prevNode;
	struct Node* nextNode;
}Node;

/* 노드 생성*/
Node* CreateNode(int data) {

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

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

	return newNode;
}



/* 리스트 출력 */
void PrintList(Node* list) {
	printf("[PrintList] 리스트 전체를 출력합니다. \n");

	Node* current = list;

	do {
		printf("%3d", current->data);
		current = current->nextNode;
	} while (current->nextNode != list->nextNode);

	printf("\n");
}

/* 노드 탐색 */
Node* GetLocation(Node* head, int location) {
	printf("[GetLocation] %d번째 노드를 찾아보자. \n", location);

	Node* current = head;

	while ((--location) >= 0) {
		//printf("location : %d 번째 탐색 \n", location);
		current = current->nextNode;
	}

	return current;
}


/* 노드 추가 */
void AppendNode(Node** head, Node* newNode) {
	printf("[AppendNode] %d를 추가합니다. \n", newNode->data);

	if (NULL == (*head)) { // 헤드가 비었다면 뉴 노드가 헤드
		
		(*head) = newNode;
		(*head)->nextNode = (*head);
		(*head)->prevNode = (*head);

	}
	else { // 테일과 헤드 사이에 뉴노드 삽입 

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

		// 뉴 노드의 다음은 헤드, 뉴 노드 이전은 테일 
		newNode->nextNode = (*head);
		newNode->prevNode = (*head)->prevNode;

		// 기존테일의 다음노드가 뉴노드.
		(*head)->prevNode->nextNode = newNode;
		// 뉴노드가 새로운 테일이 된다.
		(*head)->prevNode = newNode;
	}
}


/* 노드 삭제 */
void RemoveNode(Node** head, Node* target) {
	printf("[RemoveNode] %d를 삭제합니다. \n", target->data);

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

		(*head) = (*head)->nextNode;
	}
	else {
		target->prevNode->nextNode = target->nextNode;
		target->nextNode->prevNode = target->prevNode;
	}

	// 타겟 메모리해제 
	target->nextNode = NULL;
	target->prevNode = NULL;
	free(target);
}

int main() {
	Node* list = NULL;

	AppendNode(&list, CreateNode(10));
	AppendNode(&list, CreateNode(20));
	AppendNode(&list, CreateNode(30));

	PrintList(list);
	
	// 3번째 노드 삭제(인덱스2)
	RemoveNode(&list, GetLocation(list, 2));
	PrintList(list);

	AppendNode(&list, CreateNode(40));
	PrintList(list);

	// 1번째 노드 삭제(인덱스0)
	RemoveNode(&list, GetLocation(list, 0));
	PrintList(list);

	// 2번째 노드 삭제(인덱스1)
	RemoveNode(&list, GetLocation(list, 1));
	PrintList(list);

	return 0;
}

콘솔 결과 입니다.