이전 시간에 구현한 linked list를 이용해 circular linked list 구현하기.
#ifndef _CircularLIST_
#define _CircularLIST_
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct ListNodeType
{
int data;
struct ListNodeType* pLink;
} ListNode;
typedef struct CircularListType
{
int currentElementCount; // ���� ����� ������ ����
ListNode headerNode; // ��� ���(Header Node)
} CircularList;
CircularList* createCircularList();
int addLLElement(CircularList* pList, int position, ListNode element);
int removeLLElement(CircularList* pList, int position);
ListNode* getLLElement(CircularList* pList, int position);
void clearCircularList(CircularList* pList);
int getCircularListLength(CircularList* pList);
void deleteCircularList(CircularList* pList);
#endif
#ifndef _COMMON_LIST_DEF_
#define _COMMON_LIST_DEF_
#define TRUE 1
#define FALSE 0
#endif
circular linked list는 linked list와 이름만 다를 뿐이지 구성하는 함수나 변수는 같다. 따라서 linked list의 헤더를 분석하면 된다. linked list와 circular list의 다른 점은 add부분과 remove부분만 다르기 때문에 이 두 함수만 구현해 보겠다. 나머지는 linked list와 같다.
int addLLElement(CircularList* pList, int position, ListNode element)
{
ListNode* pNode = NULL;
ListNode* nextNode = NULL;
if (pList != NULL)
{
if (position >= 0 && position <= pList->currentElementCount)
{
nextNode = (ListNode*)malloc(sizeof(ListNode));
//case나눠서
if (nextNode != NULL)
{
pNode = &(pList->headerNode);
*nextNode = element;
nextNode->pLink = NULL;
if (pList->currentElementCount == 0)//첫번째 case. node가 아무것도 없고 0번째에 노드 추가할 때
{
pNode->pLink = nextNode;
nextNode->pLink = nextNode;
}
else if (position == 0 && pList->currentElementCount > 0)//2번째 case. node가 1개 이상이고 0번째에 노드 추가할 때
{
nextNode->pLink = pNode->pLink;
pNode->pLink = nextNode;
for(int i = 0; i < pList->currentElementCount; i++)
{
pNode = pNode->pLink;
}
pNode->pLink = nextNode;
}
else//3번째 case. node가 1개 이상이고 0번째가 아닌 position에 노드 추가할 때
{
for (int i = 0; i < position; i++)
{
pNode = pNode->pLink;
}
nextNode->pLink = pNode->pLink;
pNode->pLink = nextNode;
}
(pList->currentElementCount)++;
return (TRUE);
}
}
else
{
printf("out of index\\n");
}
}
return (FALSE);
}
함수 기능 : 노드 하나를 원하는 position에 추가하는 함수. listNode가 heap인지 stack인지 모르는 상황이기에 이 함수 내에서 따로 malloc으로 할당해 준다. remove나 delete에서 free를 하는데, 만일 stack이면 free를 못해주는 상황이기 때문.
추가를 하는 상황은 크게 3가지 case로 나뉘어진다.
1 ) 리스트에 노드가 없는 상황에서 0번째 노드를 추가할 때.
headNode의 pLink가 NULL을 가리키고 있는 상황에서, 새로 추가된 노드의 주소값을 가리키게 한다.
새로 추가된 노드의 pLink는 headNode가 아닌 자기 자신의 주소값을 가리키도록 한다.
2 ) 리스트에 노드가 1개 이상인 상황에서 0번째에 노드를 추가할 때.
headNode의 pLink가 새로운 노드를 가리키게 하기 전에, 새로 추가될 노드의 pLink를 원래 headNode의 pLink의 값을 넣는다. headNode의 pLink가 새 노드를 가리키게 되면 원래 있던 노드의 주소가 사라지기 때문.
newNode→pLink = headNode→pLink를 한 뒤에 비로소 headNode→pLink에 newNode의 주소값을 넣는다. 이후 맨 마지막 노드의 pLink에 새로 추가된 노드의 주소값을 넣어주면 된다.
3 ) 리스트에 노드가 1개 이상인 상황에서 0번째가 아닌 위치에 노드를 추가할 때.
