원형 연결리스트(CLinkedList) - C++

후기. 연결리스트와 유사한 점이 많다보니, 연결리스트 이후에 짤 때 큰 어려움은 없었다.

이전 자료구조들을 template로 짰는데 단순하게 int 형으로만 테스트를 진행해서 이번에는 float형으로도 되는지 확인해봤다. string은 class라 그런지 안되는데 이유를 찾아볼 필요가 있을 것 같다. C에서도 문자열 처리는 어려웠는데 C++에서도 마찬가지인듯 싶다.

 

4학년 늘그막에 다시 복습을 하는 내가 초심을 잃지 않길..

 

CLinkedList.h

#ifndef CLINKEDLIST_H
#define CLINKEDLIST_H


template
<typename T>
class List
{
	private:
		typedef struct Node_
		{
			T data;
			Node_* next;
		}Node;


		int numOfData;

		Node* tail;
		Node* cur;
		Node* before;

	public:
		
		List()
		{
			numOfData = 0;
			tail = nullptr;
			cur = nullptr;
			before = nullptr;
		}

		void LInsert(T data);

		void LInsertFront(T data);

		bool LFirst(T& pdata);

		bool LNext(T& pdata);

		T LRemove();

		const int LCount()
		{
			return numOfData;
		}


};


#endif

 

CLinkedList.cpp

#include "CLinkedList.h"

template
<typename T>
void List<T>::LInsert(const T data) //꼬리에 삽입
{
	Node* NewNode = (Node*)malloc(sizeof(Node));
	NewNode->data = data;

	if (tail == nullptr)
	{
		tail = NewNode;
		NewNode->next = tail;
	}
	else
	{
		NewNode->next = tail->next;
		tail->next = NewNode;
		tail = NewNode;
	}
	
	numOfData++;

}


template
<typename T>
void List<T>::LInsertFront(const T data) // 머리 == 꼬리 + 1 에 삽입
{
	Node* NewNode = (Node*)malloc(sizeof(Node));
	NewNode->data = data;

	if (tail == nullptr)
	{
		tail = NewNode;
		NewNode->Next = tail;
	}
	else
	{
		NewNode->next = tail->next;
		tail->next = NewNode;
	}
	numOfData++;

}

template
<typename T>
bool List<T>::LFirst(T& pdata)
{
	if (tail->next == nullptr)
	{
		return false;
	}
	else
	{
		before = tail;
		cur = tail->next;
		pdata = cur->data;

		return true;
	}
	

}

template
<typename T>
bool List<T>::LNext(T& pdata)
{
	if(tail == nullptr)
	{
		return false;
	}
	before = cur;
	cur = cur->next;
	pdata = cur->next->data;

	return true;
}

template
<typename T>
T List<T>::LRemove()
{
	//예외 1 삭제할 노드가 tail 인 경우

	Node* dnode = cur;
	T rdata = cur->data;

	if (cur == tail)
	{
		if (cur->next != cur)
		{
			before->next = dnode->next;
			tail = before;
		}
		else //예외 2 노드가 하나만 남은 경우(노드가 하나가 남은 경우에는 cur이 tail임)
		{
		tail = nullptr;
		}
	}

		before->next = dnode->next;
		cur = before;

		free(dnode);
		numOfData--;

		return rdata;

	free(dnode);

}

 

main.cpp

#include <iostream>
using namespace std;

#include "CLinkedList.cpp"

int main()
{
	List<int> CList;

	cout << CList.LCount() << endl;

	for (int i = 0; i < 10; i++)
	{
		CList.LInsert(i);
	}

	cout << CList.LCount() << endl;
	int a;
	for (int i = 0; i < 10; i++)
	{
		CList.LFirst(a);
		cout << a << " ";
		CList.LRemove();
		cout << CList.LCount() << endl;
	}

	List<float> CListF;

	for (int i = 0; i < 10; i++)
	{
		CListF.LInsert(i + 0.1);
	}
	float b;
	for (int i = 0; i < 10; i++)
	{
		CListF.LFirst(b);
		cout << b << " ";
		CListF.LRemove();
		cout << CListF.LCount() << endl;
	}


	return 0;
}