자료구조 원형연결리스트 예제

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 // !__C_Link_H__

CLinkedList.cpp

사용될 함수들의 정의입니다.

#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 LInsert(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;
		plist->tail->next = newNode;
		plist->tail = newNode;
	}
	plist->numOfData++;

}
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;
		plist->tail->next = newNode;
	}
	plist->numOfData++;
}

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;
}
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;

}
Data LRemove(List* plist)	//노드를 제거하는 함수
{
	Node* rpos = plist->cur;
	Data rdata = rpos->data;

	if (rpos == plist->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;
}
int LCount(List* plist)		//노드의 수를 보여주는 함수
{
	return plist->numOfData;
}

CLinkedListMain.cpp

원형연결리스트의 데이터삽입 및 출력 예시입니다.

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

int main() {

	List list;
	int data, i, nodeNum;
	ListInit(&list);

	LInsert(&list, 3);			//데이터 삽입
	LInsert(&list, 4);
	LInsert(&list, 5);
	LInsertFront(&list, 2);
	LInsertFront(&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;
}

참고: 윤성우의열혈자료구조