[Data Structure] 3. Circular List

특징

1. 순환 구조
   
   • 헤드포인터와 마지막 노드의 pLink가 가리키는 곳이 모두 첫번째 노드
   • 원소가 1개일 경우 첫번째 노드의 pLink는 자기 자신(첫번째 노드)을 가리킴
   • 첫번째 포지션에 노드 추가 시 마지막 노드의 pLink를 수정해줘야 함
   • 첫번째 노드 삭제 시 헤드포인터를 수정해줘야 함
     - 원소가 1개일 경우 헤드포인터가 NULL을 가리키도록 함
     - 원소가 1개이상일 경우 헤드포인터는 현재 첫번째 노드의 pLink를 가리키도록 함

장점

1. 헤드가 아닌 테일 포인터를 둘 경우 처음과 끝에 노드를 추가하는 것이 용이
   • 마지막 노드 = 테일, 첫 노드 = 테일의 pLink로 접근 가능

단점

1. 동적 할당, 포인터 연산 등으로 구현과 관리가 어려움
2. 자료 검색 시 맨 처음 원소부터 링크를 따라 순회해야 하므로 연산 비용이 높아짐: O(n)
3. 포인터의 사용으로 저장 공간의 낭비가 있음

구현

1. circularlist.c

#include "circularlist.h"

CircularList *createCircularList(void)
{
	CircularList *new;

	new = calloc(1, sizeof(CircularList)); // 구조체 변수 (현재 원소 개수 - 0, headPtr - NULL) 초기화
	if (!new)
		return (NULL);
	return (new);
}

// 원소 개수 == 0 (삽입 노드의 pLink = 자기 자신)

// 원소 개수 > 0 && 삽입하려는 위치 == 첫번째 (마지막 노드의 pLink = 삽입 노드)

// 원소 개수 > 0 && 삽입하려는 위치 != 첫번째

int addCLElement(CircularList *pList, int position, ListNode element)
{
	ListNode	*new; // 삽입 노드
	ListNode	*prev; // 삽입 노드를 연결 할 이전 노드
	ListNode	*last; // 마지막 노드

	if(!pList || position < 0 || position > pList->currentElementCount) // 에러 처리
		return (FALSE);
	new = malloc(sizeof(ListNode)); // 새 노드 할당
	if (!new)
		return (FALSE);
	*new = element; // 정보 저장
	prev = pList->headPtr;
	if (position == 0) // 삽입하려는 위치가 첫번째일 경우
	{
		if (pList->currentElementCount == 0) // 현재 원소 개수가 0개일 때
		{
			new->pLink = new; // 삽입 노드의 pLink를 자기 자신으로
			pList->headPtr = new; // headPtr의 pLink를 삽입 노드로
		}
		else // 현재 원소 개수가 1개 이상일 때
		{
			last = prev;
			while (last->pLink != pList->headPtr) // 노드의 pLink가 headPtr이 가리키는 노드와 같을 경우 마지막 노드이므로 반복문 탈출
				last = last->pLink; // 마지막 노드까지 last 이동
			new->pLink = prev; // 삽입 노드의 pLink를 headPtr이 가리키고 있던 첫번째 노드에 연결
			last->pLink = new; // 마지막 노드의 pLink를 삽입 노드에 연결
			pList->headPtr = new; // headPtr을 삽입 노드에 연결
		}
	}
	else // 삽입하려는 위치가 첫번째가 아닐 경우
	{
		while (--position > 0) // 삽입 위치 직전까지 prev 이동
			prev = prev->pLink;
		new->pLink = prev->pLink; // 삽입 노드의 pLink를 prev의 pLink에 연결
		prev->pLink = new; // prev의 pLink에 삽입 노드를 연결
	}
	pList->currentElementCount++; // 현재 원소 개수 갱신
	return (TRUE);
}

// 원소 개수 == 1

// 원소 개수 > 1 && 제거 노드 위치 != 첫번째

// 원소 개수 > 1

int removeCLElement(CircularList* pList, int position)
{
	ListNode *remove; // 제거 노드
	ListNode *prev; // 제거 노드의 이전 노드
	ListNode *last; // 마지막 노드

	if (!pList || position >= pList->currentElementCount || position < 0) // 에러 처리
		return (FALSE);
	prev = pList->headPtr;
	if (position == 0) // 제거 노드 위치가 첫번째일 경우
	{
		remove = prev; // 제거 노드 정보 저장
		if (pList->currentElementCount == 1) // 현재 원소 개수가 1개일 때
			pList->headPtr = NULL; // headPtr NULL에 연결
		else // 현재 원소 개수가 1개 이상일 때
		{
			last = prev; // 마지막 노드
			while (last->pLink != pList->headPtr) // 노드의 pLink가 headPtr이 가리키는 노드와 같을 경우 마지막 노드이므로 반복문 탈출
				last = last->pLink; // 마지막 노드까지 last 이동
			pList->headPtr = remove->pLink; // headPtr을 제거 노드의 pLink(현 두번째 노드)에 연결 
			last->pLink = remove->pLink; // 마지막 노드의 pLink를 제거 노드의 pLink(현 두번째 노드)에 연결
		}
	}
	else // 제거 노드 위치가 첫번째가 아닐 경우
	{
		while (--position > 0) // 제거 위치 직전까지 prev 이동
			prev = prev->pLink;
		remove = prev->pLink; // 제거 노드 정보 저장
		prev->pLink = remove->pLink; prev의 pLink에 제거 노드의 pLink를 연결
	}
	free(remove); // 제거 노드 free
	pList->currentElementCount--; // 현재 원소 개수 갱신
	return (TRUE);
}

ListNode *getCLElement(CircularList *pList, int position)
{
	ListNode *ret;

	if (!pList || position < 0 || position > pList->currentElementCount) // 에러 처리
		return (FALSE);
	ret = pList->headPtr; 
	while (position-- > 0) // 반환 위치까지 ret 이동 
		ret = ret->pLink;
	return (ret);
}

int getCircularListLength(CircularList *pList)
{
	return (pList->currentElementCount);
}

void displayCircularList(CircularList *pList)
{
	ListNode	*cur;
	int			i;

	if (!pList) // 에러 처리
	{
		printf("No List\n");
		return ;
	}
	printf("(1) Current Element count: %d\n", pList->currentElementCount);
	if (pList->currentElementCount == 0)
		printf("(2) Element: No Element\n\n");
	else
	{
		printf("(2) Element\n");
		cur = pList->headPtr;
		for (i = 0; i < pList->currentElementCount; i++)
		{
			printf("[%d]: %d", i, cur->data);
			if (i != pList->currentElementCount - 1)
				printf(", "); // 마지막 노드 제외 쉼표 출력
			cur = cur->pLink;
		}
		printf("\n\n");
	}
}

void clearCircularList(CircularList* pList)
{
	ListNode* node;
	ListNode* tmp;

	if (pList->currentElementCount == 0)
		return ;
	node = pList->headPtr;
	while (pList->currentElementCount-- > 0) // 현재 원소 개수만큼
	{
		tmp = node->pLink; 현재 노드의 다음 노드 저장을 위한 임시 변수 저장
        free(node); // 현재 노드 할당 해제
		node = tmp; // 이전에 저장해 놓은 임시 변수 값을 가져와 연속적으로 리스트 순회
	}
	pList->headPtr = NULL; // 할당 해제 된 메모리에 접근하지 않도록 NULL처리
	pList->currentElementCount = 0; // 현재 원소 개수 초기화
}

void deleteCircularList(CircularList *pList)
{
	clearCircularList(pList); // clear를 통해 리스트 내부 모든 노드 할당 해제
	free(pList); // 리스트 구조체 할당 해제
}

2. circularlist_main.c

#include "circularlist.h"

int main(void)
{
	CircularList	*pList;
	ListNode		*node;
	ListNode		ListNode;
	int				loop;
	int				opt;
	int				position;

	pList = NULL;
	while (loop)
	{
		printf("[1] Create [2] Add [3] Remove [4] Get Element [5] Length [6] Display [7] Clear [8] Delete [9] Exit ");
		scanf("%d", &opt);
		switch (opt)
		{
			case 1:
				pList = createCircularList();
				if (pList)
					printf("Create Circular List: Success\n\n");
				else
					printf("Create Circular List: Failed\n\n");
				break;
			case 2:
				printf("Position: ");
				scanf("%d", &position);
				printf("Data: ");
				scanf("%d", &ListNode.data);
				if (addCLElement(pList, position, ListNode))
				{
					printf("Add: Success\n\n");
					displayCircularList(pList);
				}
				else
					printf("Add: Failed\n\n");
				break;
			case 3:
				printf("Position: ");
				scanf("%d", &position);
				if (removeCLElement(pList, position))
				{
					printf("Remove: Success\n\n");
					displayCircularList(pList);
				}
				else
					printf("Remove: Failed\n\n");
				break;
			case 4:
				printf("Position: ");
				scanf("%d", &position);
				node = getCLElement(pList, position);
				if (node)
					printf("[%d]: %d\n\n", position, node->data);
				else
					printf("Failed\n\n");
				break;
			case 5:
				printf("Length: %d\n\n", getCircularListLength(pList));
				break;
			case 6:
				displayCircularList(pList);
				break;
			case 7:
				if (!pList)
					printf("Clear: Failed\n\n");
				else
				{
					clearCircularList(pList);
					printf("Clear: Success\n\n");
				}
				break;
			case 8:
				if (!pList)
					printf("Delete: Failed\n\n");
				else
				{
					deleteCircularList(pList);
					pList = NULL;
					printf("Delete: Success\n\n");
				}
				break;
			case 9:
				loop = 0;
				break;
			default:
				printf("Please Enter a Valid Option\n\n");
				break;
		}
	}
}

3. circularlist.h

#ifndef _CIRCULARLIST_
#define _CIRCULARLIST_

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

typedef struct ListNodeType
{
	int data;
	struct ListNodeType* pLink; // 다음 노드 연결을 위한 포인터
} ListNode;

typedef struct CircularListType
{
	int currentElementCount;	// 현재 저장된 원소의 개수
	ListNode *headPtr;			// 헤드 포인터 
} CircularList;

CircularList* createCircularList();
int addCLElement(CircularList* pList, int position, ListNode element);
int removeCLElement(CircularList* pList, int position);
ListNode* getCLElement(CircularList* pList, int position);
int getCircularListLength(CircularList* pList);
void displayCircularList(CircularList *pList);
void clearCircularList(CircularList* pList);
void deleteCircularList(CircularList* pList);
#endif

#ifndef _COMMON_LIST_DEF_
#define _COMMON_LIST_DEF_

#define TRUE		1
#define FALSE		0

#endif