열혈 자료구조 - 5-1. 원형 연결 리스트(2)

변형 원형 연결 리스트의 구현

- 원형 연결 리스트의 구조체

typedef struct _CLL
{
	Node * tail;		// 꼬리를 가르키는 포인터
	Node * cur;			// 현재 노드를 가르키는 포인터
	Node * before;		// 이전 노드를 가르키는 포인터
	int numOfData;		// 데이터 개수
} CList;

- 삽입

    -> HEAD에 추가

void LInsertFront(List * plist, Data data)
{
	Node * newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;

	if(plist->tail == NULL) 
	{
		plist->tail = newNode;
		newNode->next = newNode;
	}
	else
	{
		newNode->next = plist->tail->next;	// 새 노드의 next가 현재 tail의 next를 가르킴
		plist->tail->next = newNode;		// tail의 next가 새 노드가 됨
        						// tail은 그대로
	}

	(plist->numOfData)++;
}

    -> TAIL에 추가 : TAIL이 바뀌는 차이가 있음

void LInsertTAILList * plist, Data data)
{
	Node * newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;

	if(plist->tail == NULL) 
	{
		plist->tail = newNode;
		newNode->next = newNode;
	}
	else 
	{
		newNode->next = plist->tail->next;	// 새 노드의 next를 현재 tail의 넥스트를 받음
		plist->tail->next = newNode;		// 현재 tail의 next를 새 노드를 가르킴
		plist->tail = newNode;			// 새 노드가 tail이 됨
	}

	(plist->numOfData)++;
}

공통 부분

 

- 조회

    -> LFirst : head가 아닌 tail을 비교

int LFirst(List * plist, Data * pdata)
{
	if(plist->tail == NULL)    // 저장된 노드가 없다면
		return FALSE;

	plist->before = plist->tail;
	plist->cur = plist->tail->next;

	*pdata = plist->cur->data;
	return TRUE;
}

cur은 HEAD befor은 HEAD의 하나 왼쪽

    -> LNext : 원형 연결 리스트를 계속 순환하고 다음 노드가 NULL임을 비교하지 않음

int LNext(List * plist, Data * pdata)
{
	if(plist->tail == NULL)    // 저장된 노드가 없다면
		return FALSE;

	plist->before = plist->cur;
	plist->cur = plist->cur->next;		// 계속 순환하게 됨

	*pdata = plist->cur->data;
	return TRUE;
}

- 삭제 : 삭제하려는 노드가 tail을 가르킬 때를 구분

    -> tail을 befor로 옮기고 cur을 삭제

    -> tail이 마지막 노드이면 tail을 NULL로 만듬

Data LRemove(List * plist)
{
	Node * rpos = plist->cur;
	Data rdata = rpos->data;

	if(rpos == plist->tail)    // 삭제 대상을 tail이 가리킨다면
	{
		if(plist->tail == plist->tail->next)    // 그리고 마지막 남은 노드라면
			plist->tail = NULL;
		else
			plist->tail = plist->before;
	}

	plist->before->next = plist->cur->next;
	plist->cur = plist->before;

	free(rpos);
	(plist->numOfData)--;
	return rdata;
}

- 초기화, 개수 : 이전에 구현한 연결 리스트와 동일

void ListInit(List * plist)
{
	plist->tail = NULL;
	plist->cur = NULL;
	plist->before = NULL;
	plist->numOfData = 0;
}

int LCount(List * plist)
{
	return plist->numOfData;
}