C++ Linked List

Template과 Node를 이용하여 간단하게 linked list 구현을 시도해보았다.

 

Template을 통한 다양한 자료형을 이용할 수 있도록 하며, 뒤쪽부터 삽입하는 Push와 뒤쪽부터 데이터를 제거하는 Pop 전체 데이터를 정리하는 Clear, 데이터의 개수를 반환하는 size함수까지 구현해보았다.

 

#include <iostream>

using namespace std;

template <class T>
class Node
{
public:
	Node() : Value(0), Next(nullptr) {}

	T			Value;
	Node*		Next;
};

template <class T>
class linklist
{
public:
	linklist() : NodeCount(0), Head(nullptr) {};
	~linklist();

public:
	void			Print() const;

	void			Push(const T& data);
	void			Pop();
	void			Clear();

	int				size() const;

	Node<T>*		CreateNode();

private:
	int				NodeCount;
	Node<T>*		Head;
};

template<class T>
linklist<T>::~linklist()
{
}

template<class T>
void linklist<T>::Print() const
{
	if (Head == nullptr)
	{
		cout << "빈 공간\n";
		return;
	}

	Node<T>* pNode = Head;
	while (pNode != nullptr)
	{
		cout << pNode->Value<<" ";
		pNode = pNode->Next;
	}
	cout <<"\n";
}

template<class T>
void linklist<T>::Push(const T& data)
{
	Node<T>* newNode = CreateNode();
	newNode->Value = data;

	if (Head == nullptr)
	{
		Head = newNode;
	}
	else
	{
		Node<T>* lastNode = Head;
		while (true)
		{
			if (lastNode->Next == nullptr)
			{
				lastNode->Next = newNode;
				break;
			}
			else
			{
				lastNode = lastNode->Next;
			}
		}
	}

	NodeCount++;
}

template<class T>
void linklist<T>::Pop()
{
	if (Head == nullptr) return;

	Node<T>* lastNode = Head;
	Node<T>* prevNode = nullptr;
	while (true)
	{
		if (lastNode->Next == nullptr)
		{
			if (NodeCount == 1) Head = nullptr;

			lastNode->Value = 0;
			if(prevNode!=nullptr) prevNode->Next = nullptr;
			delete lastNode;
			break;
		}
		else
		{
			prevNode		= lastNode;
			lastNode		= lastNode->Next;
		}
	}

	cout << "제거\n";
	NodeCount--;
}

template<class T>
void linklist<T>::Clear()
{
	if (Head == nullptr) return;

	Node<T>* node = Head;
	Node<T>* dnode;

	while (true)
	{
		if (node->Next == nullptr)
		{
			delete node;
			Head = nullptr;
			break;
		}
		else
		{
			dnode = node;
			node = node->Next;

			dnode->Next = nullptr;
			delete dnode;
		}
	}
	NodeCount = 0;
}

template<class T>
int linklist<T>::size() const
{
	cout << NodeCount << "\n";
	return NodeCount;
}

template<class T>
Node<T>* linklist<T>::CreateNode()
{
	Node<T>* newNode = new Node<T>;
	
	return newNode;
}

int main()
{
	linklist<int> list;
	
	while (true)
	{
		int select;
		cout << "\n행동을 선택(-1 : Exit, 0 : print, 1 : push, 2 : pop, 3 : clear, 4 : size) : ";	cin >> select;

		if (select == -1) break;

		switch (select)
		{
		case 0:
			list.Print();
			break;
		case 1:
			double data;
			cout << "Push할 데이터 입력 : ";	cin >> data;
			list.Push(data);
			break;
		case 2:
			list.Pop();
			break;
		case 3:
			list.Clear();
			break;
		case 4:
			list.size();
			break;
		case 5:

			break;
		default:
			break;
		}
	}

	return 0;
}