C++ LinkedList 만들기 (version 2 - LinkedList Template화 하기)

C++의 template 제도와 사용에 대해서 알아보고 또 이전 버전의 LinkedList에 직접 적용시켜 구현해보도록 하겠다.

 

C++의 template은 Java의 Generic과 같은 것으로 이해하면 된다.

우리가 어떤 Collection 객체를 갖다 쓰던지 실제 사용에 있어서 한 가지 변수 타입에 국한되지 않게 쓸 수 있어야 한다. 

이전 버전의 LinkedList는 자료형의 리턴 타입이 전부 int형이었다. 하지만 Library에서 갖다쓰는 자료 구조들은 int 뿐만이 아닌 String, bool ... 혹은 객체가 됐든 어떠한 데이터도 담을 수 있다.

그래서 저번 버전의 LinkedList를 template화 시켜 다양한 자료형을 다룰 수 있게 해보겠다.

 

<참고> int만 담을 수 있는 이전 버전의 LinkedList 

https://suldenlion.tistory.com/89

 

#include <iostream>
#include <string.h>
using namespace std;
#include "LinkedList"

void main()
{
	LinkedList<Student> sList;
	LinkedList<Student> sList1;
	LinkedList<Student> sList2;
	Student a("Kim", true, 50);
	Student b("Lee", false, 70);
	Student c("Park", true, 30);

	sList.add(a);
	sList.add(b);
	sList.add(c);

	/*
	LinkedList<Student*> sList;
	sList.add(new Student("Kim", false, 30));
	sList.add(new Student("Lee", false, 90));
	sList.add(new Student("Park", false, 50));*/

	cout << sList << endl;

	LinkedList<int> list1;
	LinkedList<int> *list2 = new LinkedList<int>();

	list1.addFirst(10);
	list1.addFirst(20);
	list1.add(50);
	list1.add(60);
	list1.addAt(0, 300);

	list2->addFirst(100);
	list2->addFirst(200);

	cout << "list1 = " << list1;
	list1[2] = 20000;
	cout << "list1 = " << list1;

	int p = list1[2];
	cout << p << endl;

	int q = (*list2)[1];
	cout << q << endl;

	LinkedList<char *> ls;
	ls.add("kim");
	ls.add("lee");
	ls.add("park");
	cout << ls << endl;

}

우선 메인 소스파일이다.

 

LinkedList를 만들어서 Student를 담아서도 사용해보고, 정수와 문자도 넣어서 사용해 보도록 하겠다.

 

다음으로 LinkedList 파일을 보겠다.

#pragma once
#include <iostream>
using namespace std;

//template <class Type>
//class LinkedList<Type>;

class Student {
public:
	char name[10];
	bool gender;
	int grade;
	Student() {
	}
	Student(char *s, bool g, int grade) {
		strcpy_s(name, s);
		gender = g;
		this->grade = grade;
	}
};
ostream& operator<<(ostream& out, Student &s) {
	out << s.name << ", " << s.gender << ", " << s.grade << "; ";
	return out;
}

template <class Type>
class Node 
{
public:
	Type data;
	Node *next;
	Node(Type x) {
		data = x;
		next = NULL;
	}
//	friend LinkedList<Type>;
//	friend ostream& operator<<(ostream& out, LinkedList<Type> &l);
};

template <class Type>
class LinkedList
{
public:
	Node<Type> *header;
	int count;
	LinkedList();
	~LinkedList();
	void addFirst(Type x);
	void add(Type x);
	void addLast(Type x);
	void addAt(int index, Type x);
	void addAllAt(LinkedList<Type> *list2, int index);
	void clear();
	bool contains(Type x);
	LinkedList<Type>* clone();
	Type element();
	Type get(int index);
	Type& operator[](int index);
	Type getFirst();
	Type getLast();
	int indexOf(Type x);
	int lastIndexOf(Type x);
	void offer(Type x);
	void offerFirst(Type x);
	void offerLast(Type x);
	Type peek();
	Type peekFirst();
	Type peekLast() {
		Node<Type> *tmp;

		if (header == NULL) {
			cout << "List is empty" << endl;
			exit(-1);
		}
		tmp = header;
		while (tmp->next != NULL) {
			tmp = tmp->next;
		}
		return tmp->data;	
	};
	Type poll();
	Type pollFirst();
	Type pollLast();
	Type remove();
	Type removeAt(int index);
	Type remove(Type x);
	Type removeFirst();
	Type removeLast();
	void set(int index, Type x);
	Type* toArray();
	inline int size() { return count; }
//	friend ostream& operator<<(ostream& out, LinkedList &l);
};

template <class Type>
ostream& operator<<(ostream& out, LinkedList<Type> &l)
{
	Node<Type> *tmp = l.header;
	out << "[";
	while (tmp != NULL) {
		out << tmp->data;
		if (tmp->next != NULL) out << ", ";
		tmp = tmp->next;
	}
	out << "]" << endl;
	return out;
}


template <class Type>
LinkedList<Type>::LinkedList()
{
	header = NULL;
	count = 0;
}

template <class Type>
LinkedList<Type>::~LinkedList()
{
}

template <class Type>
void LinkedList<Type>::addFirst(Type x)
{
	Node<Type> *newNode = new Node<Type>(x);

	count++;
	newNode->next = header;
	header = newNode;
}



template <class Type>
void LinkedList<Type>::add(Type x)
{
	Node<Type> *newNode = new Node<Type>(x);
	Node<Type> *tmp;

	if (count == 0) {
		header = newNode;
		count++;
		return;
	}

	tmp = header;
	while (tmp->next != NULL) {
		tmp = tmp->next;
	}

	tmp->next = newNode;
	count++;
	return;
}

template <class Type>
void LinkedList<Type>::addLast(Type x)
{
	add(x);
}

template <class Type>
void LinkedList<Type>::addAt(int index, Type x) 
{
	Node<Type> *newNode = new Node<Type>(x);
	Node<Type> *tmp;

	if (index == 0) {
		addFirst(x);
		return;
	}
	if (index > count) {
		cout << "Index out of Bounds" << endl;
		return;
	}
	tmp = header;
	for (int i = 0; i < index-1; i++) {
		tmp = tmp->next;
	}
	newNode->next = tmp->next;
	tmp->next = newNode;
	count++;
	return;
}

template <class Type>
void LinkedList<Type>::addAllAt(LinkedList<Type> *list2, int index)
{
	Node<Type> *tmp;
	int pos;

	if (index > count) {
		cout << "Index out of Bounds" << endl;
		return;
	}

	tmp = list2->header;
	pos = index;
	while (tmp != NULL) {
		addAt(pos++, tmp->data);
		tmp = tmp->next;
	}

	return;
}

template <class Type>
void LinkedList<Type>::clear() 
{
	Node<Type> *tmp;
	Node<Type> *follow;

	tmp = header;
	follow = header;
	while (tmp != NULL) {
		follow = tmp;
		tmp = tmp->next;
		delete follow;
	}
	count = 0;
	header = NULL;
}

template <class Type>
LinkedList<Type>* LinkedList<Type>::clone()
{
	LinkedList<Type> *copied;
	Node<Type> *tmp;

	if (count == 0) return NULL;

	copied = new LinkedList<Type>();

	tmp = header;
	while (tmp != NULL) {
		copied->add(tmp->data);
		tmp = tmp->next;
	}

	copied->count = count;
	return copied;
}

template <class Type>
bool LinkedList<Type>::contains(Type x)
{
	Node<Type> *tmp;

	tmp = header;
	while (tmp != NULL) {
		if (tmp->data == x) return true;
		tmp = tmp->next;
	}
	return false;
}

template <class Type>
Type LinkedList<Type>::element()
{
	if (header == NULL) {
		cout << "List is empty" << endl;
		exit(-1);
	}
	return header->data;
}

template <class Type>
Type LinkedList<Type>::get(int index)
{
	Node<Type> *tmp;
	Type value;

	tmp = header;
	if (count == 0) {
		cout << "List is empty" << endl;
		exit(-1);
	}
	if (index == 0) {
		value = tmp->data;
		return value;
	}
	if (index > count-1) {
		cout << "Cannot get element" << endl;
		exit(-1);
	}

	for (int i = 0; i < index; i++) {
		tmp = tmp->next;
	}
	value = tmp->data;
	return value;
}

template <class Type>
Type& LinkedList<Type>::operator[](int index)
{
	Node<Type> *tmp;
	Type value;

	tmp = header;
	if (count == 0) {
		cout << "List is empty" << endl;
		exit(-1);
	}
	if (index == 0) {
		value = tmp->data;
		return tmp->data;
	}
	if (index > count-1) {
		cout << "Cannot get element" << endl;
		exit(-1);
	}

	for (int i = 0; i < index; i++) {
		tmp = tmp->next;
	}
	return tmp->data;
}

template <class Type>
Type LinkedList<Type>::getFirst()
{
	Node<Type> *tmp;
	Type value;

	if (count == 0) {
		cout << "List is empty" << endl;
		exit(-1);
	}
	tmp = header;
	value = tmp->data;
	return value;
}

template <class Type>
Type LinkedList<Type>::getLast()
{
	Node<Type> *tmp;
	Type value;

	if (header == NULL) {
		cout << "List is empty" << endl;
		exit(-1);
	}
	tmp = header;
	while (tmp->next != NULL) {
		tmp = tmp->next;
	}
	value = tmp->data;
	return value;
}

template <class Type>
int LinkedList<Type>::indexOf(Type x) 
{
	Node<Type> *tmp;
	int pos = 0;

	if (header == NULL) {
		cout << "List is empty" << endl;
		exit(-1);
	}
	tmp = header;
	while (tmp != NULL) {
		if (tmp->data == x) {
			return pos;
		}
		pos++;
		tmp = tmp->next;
	}

	cout << "No such element" << endl;
	exit(-1);
}

template <class Type>
int LinkedList<Type>::lastIndexOf(Type x) 
{
	Node<Type> *tmp;
	int pos;
	int value = -1;

	if (header == NULL) {
		cout << "List is empty" << endl;
		exit(-1);
	}
	tmp = header;
	pos = 0;
	while (tmp != NULL) {
		if (tmp->data == x) value = pos;
		tmp = tmp->next;
		pos++;
	}
	if (value == -1) {
		cout << "No such element" << endl;
		exit(-1);
	}

	return value;
}

template <class Type>
void LinkedList<Type>::offer(Type x) 
{
	add(x);
}

template <class Type>
void LinkedList<Type>::offerFirst(Type x) 
{
	addFirst(x);
}

template <class Type>
void LinkedList<Type>::offerLast(Type x) 
{
	addLast(x);
}

template <class Type>
Type LinkedList<Type>::peek() 
{
	if (header == NULL) {
		cout << "List is empty" << endl;
		exit(-1);
	}
	return header->data;
}

template <class Type>
Type LinkedList<Type>::peekFirst()
{
	return peek();
}

template <class Type>
Type LinkedList<Type>::poll()
{
	return getFirst();
}

template <class Type>
Type LinkedList<Type>::pollFirst()
{
	return getFirst();
}

template <class Type>
Type LinkedList<Type>::pollLast()
{
	return getLast();
}

template <class Type>
Type LinkedList<Type>::remove() 
{
	Node<Type> *tmp;
	Type value;

	if (header == NULL) {
		cout << "List is empty" << endl;
		exit(-1);
	}
	if (count == 1) {
		value = header->data;
		header = NULL;
		count = 0;
		return value;
	}
	tmp = header;
	value = header->data;
	header = tmp->next;
	count--;
	delete tmp;
	return value;
}

template <class Type>
Type LinkedList<Type>::removeAt(int index)
{
	Node<Type> *tmp;
	Node<Type> *follow;
	Type value;

	if (header == NULL) {
		cout << "List is empty" << endl;
		exit(-1);
	}
	if (count == 1 && index == 0) {
		value = header->data;
		header = NULL;
		count = 0;
		return value;
	}
	if (index == 0) {
		value = header->data;
		tmp = header->next;
		header = tmp;
		count--;
		return value;
	}
	if (index > count-1) {
		cout << "Incorrect index" << endl;
		exit(-1);
	}
	tmp = header;
	for (int i = 0; i < index; i++) {
		follow = tmp;
		tmp = tmp->next;
	}
	value = tmp->data;
	follow->next = tmp->next;
	count--;
	delete tmp;
	return value;
}

template <class Type>
Type LinkedList<Type>::remove(Type x)
{
	Node<Type> *tmp;
	Node<Type> *follow;
	int pos = 0;

	if (header == NULL) {
		cout << "List is empty" << endl;
		exit(-1);
	}
	if (header->data == x) {
		header = header->next;
		count--;
		return pos;
	}
	tmp = header;
	while (tmp != NULL) {
		if (tmp->data == x) {
			follow->next = tmp->next;
			count--;
			delete tmp;
			return pos;
		}
		follow = tmp;
		tmp = tmp->next;
		pos++;
	}
	cout << "No such element" << endl;
	exit(-1);
}

template <class Type>
Type LinkedList<Type>::removeFirst()
{
	Type value;

	if (header == NULL) {
		cout << "List is empty" << endl;
		exit(-1);
	}
	value = header->data;
	header = header->next;
	count--;
	return value;
}

template <class Type>
Type LinkedList<Type>::removeLast()
{
	Node<Type> *tmp;
	Node<Type> *follow;
	Type value = -1;

	if (header == NULL) {
		cout << "List is empty" << endl;
		exit(-1);
	}
	if (count == 1) {
		value = header->data;
		header = NULL;
		count = 0;
		return value;
	}
	tmp = header;
	while (tmp->next != NULL) {
		follow = tmp;
		tmp = tmp->next;
	}
	count--;
	value = tmp->data;
	follow->next = NULL;
	delete tmp;
	return value;
}

template <class Type>
void LinkedList<Type>::set(int index, Type x)
{
	Node<Type> *tmp;

	if (header == NULL) {
		cout << "List is empty" << endl;
		exit(-1);
	}
	if (index > count-1) {
		cout << "Incorrect index" << endl;
		exit(-1);
	}
	tmp = header;
	for (int i = 0; i < index; i++) {
		tmp = tmp->next;
	}
	tmp->data = x;
	return;
}

template <class Type>
Type *LinkedList<Type>::toArray()
{
	Type* arr = (int *)malloc(sizeof(Type) * count);
	Node<Type> *tmp;

	tmp = header;
	for (int i = 0; i < count; i++) {
		arr[i] = tmp->data;
		tmp = tmp->next;
	}

	return arr;
}

이전 까지는 헤더 파일과 구현 파일을 따로 분리하여 작성하였는데 template화 시킨 LinkedList는 확장명을 떼고 한 파일로 만들어 주겠다. 라이브러리에 있는 파일들은 이렇게 헤더와 구현파일이 합쳐져 있는데, 그로인해 메인에서 파일을 include 할때, <LinkedList.h>가 아닌 <LinkedList>로 하는것과 같다.

 

Template화 과정은 간단하다.

다양한 데이터 타입을 요하는 클래스나 메서드 위에 "template <class Type>"이라고 한 줄 추가해 주면 된다.

 

위의 Node 클래스를 예시로 보면,

클래스를 정의해주기 직전에 "template <class Type>"을 적어준다. 그리고 리스트의 각 노드에 담을 데이터의 타입을 Type으로 정의해준다. 참고로 타입이름은 Type이던, T로 하던, var로 하던 상관없다.

 

마찬가지로 기존 LinkedList에서 데이터를 int로 돌려주는 부분을 Type을 돌려주도록 수정해준다. 또한 formal parameter로 들어오던 int들도 수정한다.

peekLast()는 클래스 내에서 선언과 정의를 해 주었는데, 함수 정의시 "template <class Type>"를 적기 싫다면 이렇게 하는 방법도 있다.

 

이런식으로 여러 종류의 데이터 타입을 갖고 작업하는 경우 위와 같은 방식들을 쓴다.

 

 

Student 클래스를 만들어 각 Student들을 담는 LinkedList를 만들어 사용해 보겠다.

Student 클래스는 char형 array의 name, bool 타입의 gender, int grade를 data member로 대충 만들어주고 toString()에 해당하는 operator overloading <<을 구현해준다.

 

메인 함수에서 Student 타입을 다루는 LinkedList를 만들어서 데이터를 추가해주고 출력시켜보면 문제없이 나올 것이다.

 

템플릿을 많이 쓰면 컴파일 속도가 조금 느려진다고 한다. 하지만 C++의 개발 트렌드로써의 템플릿의 사용은 필수라고 한다. 생산성과 유지보수성 및 재사용성이 좋기 때문이다.