C++ LinkedList 만들기 (version 3 - Iterator 구현 및 사용)

이전에 만든 LinkedList에 Iterator를 추가하여 traverse하는 용도로 써보겠다.

 

먼저, C++의 STL에 대해 짚고 넘어가겠다.

STL이란 표준 템플릿 라이브러리라고 하며, ISO C++위원회에서 specification을 정한다. ISO에서 특정 클래스의 명세를 결정해 발표하면 C++ 컴파일러를 만드는 vendor들이 알아서 template들을 구현한다. 

이것은 알고리즘, 컨테이너, 함수자, 반복자의 네가지 구성 요소를 제공한다.

프로그래머가 자료구조와 알고리즘의 정확한 내부 구조를 모르더라도 사용할 수 있게 구현해놓았다.

 

간단한 STL 사용 예제를 보겠다.

#include <iostream>
using namespace std;
#include <vector>
#include <stack>
#include <list>

template <class Type>
ostream& operator<<(ostream &outs, list<Type> &v) 
{
	outs << "[";
	list<Type>::iterator it = v.begin();
	while (it != v.end()) {
		Type data = *it;
		outs << data;
		it++;
		if (it != v.end()) outs << " ";
	}

	/*for (int i = 0; i < v.size(); i++)
	{
		outs << v[i];
		if (i < v.size()-1) outs << " ";
	}*/
	outs << "]";

	return outs;
}

template <class Type>
ostream& operator<<(ostream &outs, vector<Type> &v) 
{
	outs << "[";
	for (int i = 0; i < v.size(); i++)
	{
		outs << v.at(i);
		if (i < v.size()-1) outs << " ";
	}
	outs << "]";
	return outs;
}

void main()
{
	vector<int> v1;
	stack<int> x1;
	list<int> l1;

	l1.push_back(10);
	l1.push_back(20);
	l1.push_back(30);
	l1.push_front(40);
	l1.push_front(50);

	cout << l1 << endl;

	x1.push(10);
	x1.push(20);
	x1.push(30);

	//cout << x1 << endl;

	v1.push_back(10);
	v1.push_back(20);
	v1.push_back(30);

	cout << v1 << endl;
	/*for (int x : v1) {
		cout << x << " ";
	}*/
}

vector와 stack, list 등을 라이브러리로 부터 import 해와서 사용한다.

라이브러리의 이런 컨테이너들은 push_front(), push_back() 같은 이름의 함수로 값을 넣는 경우가 많다.

 

또, 이런 컨테이너들을 traverse 할 일이 있을 때,

iterator의 첫번째 요소를 불러오는 메서드는 begin(), 끝난 것에 해당하는 것은 end() 라는 식의 함수 이름을 쓴다.

 

 

마이크로소프트 표준 라이브러리의 설명서에 있는 내용이다.

위 메서드 명과 맞춰서 iterator를 직접 구현해 보도록 하겠다.

 

 

 

 

C++ 라이브러리의 iterator는 맨 앞글자를 소문자로 해서 쓴다.

 

라이브러리 iterator랑 이름이 겹칠 수 있으므로, 만들 Iterator는 i를 대문자로 하겠다.

 

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

void main()
{
	LinkedList list1;

	list1.addFirst(10);
	list1.addFirst(20);
	list1.add(50);
	list1.add(60);
	list1.addAt(0, 300);
	
	Iterator it;
	
	it = list1.begin();
	while (it != list1.end()) {
		int data = *it;
		cout << data << endl;
		it++;
	}

	/*POSITION pos = list1.GetHeadPosition();
	while (pos != NULL) {
		int data = list1.GetNext(pos);
		cout << data << endl;
	}*/

	cout << "list1 = " << list1;
}

List에 값을 채워넣은 후, Iterator it를 list의 begin()으로 가져와 end()까지 돌면서 it가 가리키는 포인터의 데이터를 data에 담아 출력해주는 프로그램이다.

 

Iterator를 만들기 전, 같은 역할의 void* 타입의 POSITION을 만들어 traverse 해봤다.

 

헤더에서 자세히 보겠다.

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

typedef void* POSITION;

class LinkedList;
class Node;
class Iterator;

//typedef void* Iterator;

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

class Iterator 
{
	Node *tmp;
public:
	Iterator() {
		tmp = NULL;
	}
	Iterator(Node *h) {
		tmp = h;
	}
	void operator++() {
		tmp = tmp->next;
	}
	int operator*() {
		return tmp->data;
	}
	bool operator!=(Iterator &it) {		
		return tmp != it.tmp;
	}
};

class LinkedList
{
	Node *header;
	int count;
public:
	LinkedList();
	~LinkedList();
	void addFirst(int x);
	void add(int x);
	void addLast(int x);
	void addAt(int index, int x);
	void addAllAt(LinkedList *list2, int index);
	void clear();
	bool contains(int x);
	LinkedList* clone();
	int element();
	int get(int index);
	int getFirst();
	int getLast();
	int indexOf(int x);
	int lastIndexOf(int x);
	void offer(int x);
	void offerFirst(int x);
	void offerLast(int x);
	int peek();
	int peekFirst();
	int peekLast();
	int poll();
	int pollFirst();
	int pollLast();
	int remove();
	int removeAt(int index);
	int remove(int x);
	int removeFirst();
	int removeLast();
	void set(int index, int x);
	int* toArray();
	inline int size() { return count; }
	POSITION GetHeadPosition() {
		return header;
	}
	int GetNext(POSITION &pos) {
		int data = ((Node *)pos)->data;
		pos = ((Node *)pos)->next;
		return data;
	}
	Iterator begin() {
		return *(new Iterator(header));
	}
	Iterator end() {
		return *(new Iterator(NULL));
	}
	friend ostream& operator<<(ostream& out, LinkedList &l);
};

 

 

void를 가리키는 포인터 POSITION을 선언해주어, Traverse시 마다 Node와 같은 타입으로 type casting을 해준다.

이런 방식도 있다.

 

이제 Iterator의 방식을 보겠다.

코드 위쪽에 전방 선언을 해주고

Node를 Iterator에서 쓰기 때문에 friend 선언을 해준다

 

Iterator의 첫번쨰 인자를 얻어내기 위한 begin()과 traverse 마침을 위한 end()를 리스트 내에다 만들어준다.

각각 새로 만든 헤더를 가리키는 Iterator의 포인터와 NULL 값을 가리키는 Iterator의 포인터를 리턴해준다.

 

Iterator의 Constructor는 헤더를 가리키는 노드를 tmp 값이 가리키도록 세팅을 하고, operation overloading을 통해 operator++로 next() 역할을, operator*로 데이터 값 리턴을, operator!=으로 Formal parameter로 들어온 Iterator의 레퍼런스 type과 현재 traverse 중인 tmp가 같은지 비교하여 bool type을 리턴하는 메서드들을 만들어준다.(equals 역할)

 

그리고 LinkedLIst가 구현한 cpp 파일이다.

#include "LinkedList.h"

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

LinkedList::LinkedList()
{
	header = NULL;
	count = 0;
}


LinkedList::~LinkedList()
{
}

void LinkedList::addFirst(int x)
{
	Node *newNode = new Node(x);

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

void LinkedList::add(int x)
{
	Node *newNode = new Node(x);
	Node *tmp;

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

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

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

void LinkedList::addLast(int x)
{
	add(x);
}

void LinkedList::addAt(int index, int x) 
{
	Node *newNode = new Node(x);
	Node *tmp;

	if (index == 0) {
		addFirst(x);
		return;
	}
	if (index > count) {
		cout << "Index가 List 사이즈를 벗어났습니다" << endl;
		return;
	}
	tmp = header;
	for (int i = 0; i < index-1; i++) {
		tmp = tmp->next;
	}
	newNode->next = tmp->next;
	tmp->next = newNode;
	count++;
	return;
}

void LinkedList::addAllAt(LinkedList *list2, int index)
{
	Node *tmp;
	int pos;

	if (index > count) {
		cout << "Index가 List 사이즈를 벗어났습니다" << endl;
		return;
	}

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

	return;
}

void LinkedList::clear() 
{
	Node *tmp;
	Node *follow;
	
	tmp = header;
	follow = header;
	while (tmp != NULL) {
		follow = tmp;
		tmp = tmp->next;
		delete follow;
	}
	count = 0;
	header = NULL;
}

LinkedList* LinkedList::clone()
{
	LinkedList *copied;
	Node *tmp;

	if (count == 0) return NULL;

	copied = new LinkedList();

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

	copied->count = count;
	return copied;
}

bool LinkedList::contains(int x)
{
	Node *tmp;

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

int LinkedList::element()
{
	if (header == NULL) {
		cout << "List is empty" << endl;
	}
	return header->data;
}

int LinkedList::get(int index)
{
	Node *tmp;
	Node *follow;
	int value;

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

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

int LinkedList::getFirst()
{
	Node *tmp;
	int value;

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

int LinkedList::getLast()
{
	Node *tmp;
	Node *follow;
	int value;

	if (header == NULL) {
		cout << "List is empty" << endl;
		return -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;
}

int LinkedList::indexOf(int x) 
{
	Node *tmp;
	int pos = 0;

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

	cout << "No such element" << endl;
	return -1;
}

int LinkedList::lastIndexOf(int x) 
{
	Node *tmp;
	int pos;
	int value = -1;

	if (header == NULL) {
		cout << "List is empty" << endl;
		return value;
	}
	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;
	
	return value;
}

void LinkedList::offer(int x) 
{
	add(x);
}

void LinkedList::offerFirst(int x) 
{
	addFirst(x);
}

void LinkedList::offerLast(int x) 
{
	addLast(x);
}

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

int LinkedList::peekFirst()
{
	return peek();
}

int LinkedList::peekLast()
{
	Node *tmp;

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

int LinkedList::poll()
{
	return getFirst();
}

int LinkedList::pollFirst()
{
	return getFirst();
}
	
int LinkedList::pollLast()
{
	return getLast();
}

int LinkedList::remove() 
{
	Node *tmp;
	int value = -1;
	
	if (header == NULL) {
		cout << "List is empty" << endl;
		return value;
	}
	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;
}

int LinkedList::removeAt(int index)
{
	Node *tmp;
	Node *follow;
	int value = -1;

	if (header == NULL) {
		cout << "List is empty" << endl;
		return value;
	}
	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;
		return value;
	}
	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;
}

int LinkedList::remove(int x)
{
	Node *tmp;
	Node *follow;
	int pos = 0;

	if (header == NULL) {
		cout << "List is empty" << endl;
		return -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;
	return -1;
}

int LinkedList::removeFirst()
{
	int value = -1;

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

int LinkedList::removeLast()
{
	Node *tmp;
	Node *follow;
	int value = -1;

	if (header == NULL) {
		cout << "List is empty" << endl;
		return value;
	}
	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;
}

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

int *LinkedList::toArray()
{
	int* arr = (int *)malloc(sizeof(int) * count);
	Node *tmp;

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

	return arr;
}