#08 자료구조 원형연결리스트(Circular Linked List)

원형 연결 리스트 (Circular Linked List)

 

Main.h

#include <stdio.h>
#include "CLinkedList.h"

int main(void)
{
	// 원형 연결 리스트의 생성 및 초기화
	List list;
	int data, i, nodeNum;
	ListInit(&list);

	// 리스트에 5개의 데이터를 저장
	LInsert(&list, 3);
	LInsert(&list, 4);
	LInsert(&list, 5);
	LInsertFront(&list, 2);
	LInsertFront(&list, 1);

	// 리스트에 저장된 데이터를 연속 3회 출력
	if (LFirst(&list, &data))
	{
		printf("%d ", data);

		for (i = 0; i < LCount(&list) * 3 - 1; i++) {
			if (LNext(&list, &data))
				printf("%d ", data);
		}
	}
	printf("\n");

	// 2의 배수를 찾아서 모두 삭제
	nodeNum = LCount(&list);

	if (nodeNum != 0)
	{
		LFirst(&list, &data);
		if (data % 2 == 0)
			LRemove(&list);

		for (i = 0; i < nodeNum - 1; i++)
		{
			LNext(&list, &data);
			if (data % 2 == 0)
				LRemove(&list);
		}
	}

	// 현재 데이터 1회 출력
	if (LFirst(&list, &data))
	{
		printf("%d ", data);

		for (i = 0; i < LCount(&list) - 1; i++)
		{
			if (LNext(&list, &data))
				printf("%d ", data);
		}
	}
	return 0;
}

 

CLinkedList.h

#ifndef __C_LINKED_LIST_H__
#define __C_LINKED_LIST_H__

#define TRUE 1
#define FALSE 0

typedef int Data;

typedef struct _node
{
	Data data;
	struct _node* next;
} Node;

typedef struct _CLL
{
	Node* tail;
	Node* cur;
	Node* before;
	int numOfData;
} CList;

typedef CList List;

void ListInit(List* plist);
void LInsert(List* plist, Data data); // 꼬리에 노드를 추가.
void LInsertFront(List* plist, Data data); // 머리에 노드를 추가.

int LFirst(List* plist, Data* pdata);
int LNext(List* plist, Data* pdata);
Data LRemove(List* plist);
int LCount(List* plist);

#endif

 

CLinkedList.c

구현해보기

#ifdef _MSC_YER
#define _CRT_SECURE_NO_WARNINGS
#endif

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

void ListInit(List* plist)
{

}

void LInsert(List* plist, Data data)
{

}

void LInsertFront(List* plist, Data data)
{

}

int LFirst(List* plist, Data* pdata)
{

}

int LNext(List* plist, Data* pdata)
{

}

Data LRemove(List* plist)
{

}

int LCount(List* plist)
{

}

구현

#ifdef _MSC_YER
#define _CRT_SECURE_NO_WARNINGS
#endif

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

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

void LInsertFront(List* plist, Data data) // 새 노드를 머리에 저장
{
	Node* newNode = (Node*)malloc(sizeof(Node)); // 새 노드 생성
	newNode->data = data; // 새 노드에 데이터 저장

	if (plist->tail == NULL) // 첫 번째 노드라면,
	{
		plist->tail = newNode; // tail이 새 노드를 가리키게 한다.
		newNode->next = newNode; // 새 노드 자신을 가리키게 한다.
	}
	else // 두 번째 이후의 노드라면,
	{
		newNode->next = plist->tail->next; // 새 노드와 4가 저장된 노드 연결
		plist->tail->next = newNode; // 2가 저장된 노드와 새 노드 연결
	}
	(plist->numOfData)++;
}

void LInsert(List* plist, Data data) // 새 노드를 꼬리에 저장
{
	Node* newNode = (Node*)malloc(sizeof(Node)); // 새 노드 생성
	newNode->data = data; // 새 노드에 데이터 저장

	if (plist->tail == NULL) // 첫 번째 노드라면,
	{
		plist->tail = newNode; // tail이 새 노드를 가리키게 한다.
		newNode->next = newNode; // 새 노드 자신을 가리키게 한다.
	}
	else // 두 번째 이후의 노드라면,
	{
		newNode->next = plist->tail->next; // 새 노드와 4가 저장된 노드 연결
		plist->tail->next = newNode; // 2가 저장된 노드와 새 노드 연결
		plist->tail = newNode; // LInsertFront 함수와의 유일한 차이점
	}
	(plist->numOfData)++;
}

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

	plist->before = plist->tail; // before가 꼬리를 가리키게 한다.
	plist->cur = plist->tail->next; // cur이 머리를 가리키게 한다.

	*pdata = plist->cur->data; // cur이 가리키는 노드의 데이터 반환.
	return TRUE;
}

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

	plist->before = plist->cur; // before가 다음 노드를 가리키게 한다.
	plist->cur = plist->cur->next; // cur이 다음 노드를 가리키게 한다.

	*pdata = plist->cur->data; // cur이 가리키는 노드의 데이터 반환.
	return TRUE;
}

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; // before의 next를 cur 다음과 연결
	plist->cur = plist->before; // cur를 before로 이동(이전 데이터로 이동)

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

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