(C++로 데이터 구조 구현) LinkedList 생성(버전 2 – LinkedList 템플릿)

by

템플릿 시스템과 C++ 사용법에 대해 알아보고 이전 버전의 LinkedList에 직접 적용하여 구현해 보겠습니다.

C++의 템플릿을 Java의 제네릭과 동일하게 생각할 수 있습니다.

우리가 어떤 Collection 객체를 사용하든 실제 사용시 한 가지 변수에 국한되지 않고 사용할 수 있어야 합니다.

이전 버전의 LinkedList에서는 데이터 유형 반환 유형이 모두 int 유형이었습니다. 그러나 라이브러리에서 사용되는 데이터 구조는 int뿐만 아니라 문자열, bool… 또는 객체와 같은 모든 데이터를 보유할 수 있습니다.

'추천 관련글,

따라서 다른 데이터 유형을 처리할 수 있도록 이전 버전의 LinkedList를 템플릿으로 사용하겠습니다.

int만 포함할 수 있는 이전 버전의 LinkedList

https://suldenlion.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를 생성하여 학생을 포함하는 데 사용하고 정수와 문자도 포함하여 사용하려고 합니다.

다음으로 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;
}

기존에는 헤더 파일과 구현 파일을 따로 작성했지만 템플릿 기반의 LinkedList는 확장명을 제거하고 하나의 파일로 만든다. 라이브러리의 파일은 다음과 같이 헤더 및 구현 파일과 결합됩니다. 그래서 메인파일에 파일을 넣으면 똑같아요. 대신에 .

제출 절차는 간단합니다.

“템플릿 ‘ 다른 데이터 유형이 필요한 클래스 또는 메서드 위에 있습니다.

위의 Node 클래스를 예로 사용


“템플릿 작성 ‘ 클래스 정의 직전. 그리고 리스트의 각 노드에 담을 데이터의 타입을 타입으로 정의한다. 참고로 타입 이름이 Type인지, T인지, var인지는 중요하지 않습니다.

마찬가지로 기존 LinkedList에서 데이터를 int로 반환하는 부분을 타입을 반환하도록 변경합니다. 또한 형식 매개변수로 받은 int를 수정합니다.



peekLast()는 클래스 내부에서 선언 및 정의하지만 “템플릿”을 사용하지 않으면 “, 그렇게 할 수 있습니다.

이러한 방식으로 여러 데이터 유형으로 작업할 때 위의 방법을 사용하십시오.

나는 학생 클래스를 만들고 각 학생을 포함하는 LinkedList를 만들 것입니다.


학생 클래스는 대략 char형의 이름, bool형의 성별, int grade를 데이터 멤버로 만들고 toString()에 따라 연산자 오버로드<<를 구현한다.


메인 함수에서 Student 타입을 처리하는 LinkedList를 생성하고 데이터를 추가하여 출력하면 문제 없이 출력됩니다.

너무 많은 템플릿을 사용하면 컴파일 속도가 느려진다고 합니다. 그러나 C++의 발전 추세에 따라 템플릿의 사용은 필수불가결한 것으로 여겨진다. 생산성, 유지 보수성 및 재사용성이 우수하기 때문입니다.