C++ LinkedList 만들기 (version 4 - Doubly LinkedList)

C++로 Doubly LinkedList 만들기

 

https://suldenlion.tistory.com/97

(C로 자료구조 구현하기) LinkedList 만들기 (version 2 - Doubly LinkedList)

위의 C로 Doubly LinkedLIst 만들기의 코드를 참고하여 C++ Doubly LinkedList를 만들어 보겠다.

 

바로 소스코드를 보며 비교 및 수정을 해보겠다.

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

void main()
{
	LinkedList list1;
	LinkedList list2;
	int i;
	
	list1.add(10);
	list1.add(20);
	list1.add(30);
	list1.addAt(1,40);
	list1.print();
	cout << list1.size() << endl;

	list2.addLast(200);
	list2.addFirst(100);
	list2.addFirst(300);
	list2.clear();
	list2.print();
	cout << list2.size() << endl;

	list1.addAllAt(&list2, 3);
	list1.print();
	cout << list1.size() << endl;

	LinkedList *list3;
	list3 = list1.clone();
	list3->print();
	cout << list3->size() << endl;

	cout << list3->indexOf(40) << endl;
	list3->add(40);
	list3->add(40);
	list3->addLast(80);
	list3->set(3, 100);
	list3->removeData(40);
	list3->removeData(40);
	list3->removeData(80);
	list3->removeAt(0);

	list3->print();
	cout << list3->size() << endl;

	/*int *arr = list3->toArray();

	for (int i = 0; i < list3->size(); i++) cout << arr[i] + " ";
	cout << endl;*/

	//cout << list3->lastIndexOf(40) << endl;	
	//cout << list3->get(2) << endl;
	//cout << list3->getLast() << endl;

	/*list1.add(10);
	list1.print();
	list1.add(20);
	list1.add(30);
	list1.add(30);
	list1.add(30);
	list1.add(40);
	list1.add(50);

	list2.add(100);
	list2.add(200);

	list2.addAllAt(&list1, 0);
	list2.clear();

	//list2 = *list1.clone();

	//cout << list1.contains(101) << endl;
	
	cout << "list1 = ";
	list1.print();

	cout << "list2 = ";
	list2.print();

	list1.addFirst(100);
	list1.addFirst(200);
	list1.addFirst(300);
	list1.addLast(400);
	list1.addLast(500);
	list1.print();

	list1.addAt(0, 7);
	list1.print();*/

	/* Iterator it = list1.begin();
	while(it != list1.end()) {
		int data = *it;
		cout << data << endl;
		it++;
	} */

	/*
	add(&list2, 100);
	add(&list2, 200);
	add(&list2, 300);

	printf("get 0 %d\n", get(&list1, 0));
	printf("getFirst %d\n", getFirst(&list1));
	printf("getLast %d\n", getLast(&list1));
	printf("list1 = ");
	print(&list1);

	printf("list2 = ");
	print(&list2);

	//printf("%d\n", get(&list1, 0));
	//printf("%d\n", element(&list1));
	//printf("%d\n", getFirst(&list1));
	//printf("%d\n", getLast(&list1));
	printf("%d\n", lastIndexOf(&list1, 30));
	
	set(&list1, 3, 700);

	//removeAt(&list1, 2);
	//removeAt(&list1, 0);
	removeData(&list1, 700);
	
	printf("list1 = ");
	print(&list1);

	arr = toArray(&list1);
	for (i = 0; i < size(&list1); i++) {
		printf("%d ", arr[i]);
	}*/
}

메인 함수이다.

LinkedList의 사용에 있어서 크게 다른점은 없다. 리스트를 Dynamic allocation할 때 new를 써서 생성한다는 점이나 함수 호출시 리시버 객체가 Argument에 포함되지 않는다는 것 정도의 차이가 있다.

 

 

#ifndef _LINKEDLIST_
#define _LINKEDLIST_

#include <stdio.h>
#include <malloc.h>

#define TRUE	(1)
#define FALSE	(0)

class LinkedList;
class Node;

class Iterator {
	Node *tmp;
	Node *endPtr;
	LinkedList *listOrg;
public:
	Iterator(LinkedList *list);
	Iterator(LinkedList *list, Node *ptr);
	int operator*();
	void operator++();
	bool operator!=(Iterator &it) {
		return tmp != it.endPtr;
	}
	bool operator==(Iterator &it) {
		return tmp == it.endPtr;
	}
	friend LinkedList;
};

class Node {
	Node *prev;
	int data;
	Node *next;
	Node() {
		prev = next = this;
		data = 0;
	}
	Node(int d) {
		prev = next = this;
		data = d;
	}
	void insert(Node *chain);
	void append(Node *chain);
	void remove();
	friend LinkedList;
	friend Iterator;
};

class LinkedList {
	bool startFlag;
	Node *header;
	int count;
public:
	LinkedList();
	~LinkedList();
	Iterator begin() {
		startFlag = true;
		return Iterator(this);
	}
	Iterator end() {
		if (startFlag == true) return Iterator(this, NULL);
		return Iterator(this, header);
	}
	void addFirst(int x);
	void add(int x);
	void addLast(int x);
	void addAt(int index, int x);
	void addAllAt(LinkedList *l2, int index);
	void print();
	int size();
	void clear();
	LinkedList *clone();
	bool contains(int x);
	int get(int index);
	int getFirst();
	int getLast();
	int indexOf(int x);
	int lastIndexOf(int x);
	int element();
	void set(int index, int x);
	void removeData(int x);
	void removeAt(int index);
	int *toArray();
	friend Iterator;
};

#endif

다음은 헤더 파일이다.

C++ 형식에 맞게 수정해주고 traverse 용도의 Iterator 클래스를 정의해 두었다.

 

 

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

Iterator::Iterator(LinkedList *list) {
	tmp = list->header;
	listOrg = list;
	endPtr = NULL;
}

Iterator::Iterator(LinkedList *list, Node *ptr) {
	tmp = list->header;
	listOrg = list;
	endPtr = ptr;
}

int Iterator::operator*() {
	return tmp->data;
}

void Iterator::operator++() {
	listOrg->startFlag = false;
	tmp = tmp->next;
}

void Node::insert(Node *chain)
{
	this->prev = chain->prev;
	this->next = chain;
	chain->prev->next = this;
	chain->prev = this;
}

void Node::append(Node *chain)
{
	this->prev = chain;
	this->next = chain->next;
	chain->next->prev = this;
	chain->next = this;
}

void Node::remove()
{
	//printf("node->data = %d\n", node->data);
	this->prev->next = this->next;
	this->next->prev = this->prev;
	delete this;
}

LinkedList::LinkedList()
{
	this->header = NULL;
	this->count = 0;
	this->startFlag = true;
}

LinkedList::~LinkedList() 
{
	Node *tmp;
	if (this->header == NULL) return;
	while (this->header->next != this->header) {
		tmp = this->header->next;
		tmp->remove();
	}
	this->header->remove();
}

void LinkedList::addFirst(int x)
{
	add(x);
	this->header = this->header->prev;
}

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

	this->count = this->count + 1;
	if (this->header == NULL) {
		this->header = new Node(x);
		return;
	}
	tmp = new Node(x);
	tmp->insert(this->header);
}

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

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

	if (index == 0) {
		addFirst(x);
		return;
	}
	tmp = this->header;
	this->count = this->count + 1;
	for (i = 0; i < index; i++) {
		tmp = tmp->next;
	}
	newNode = new Node(x);
	newNode->insert(tmp);
}

void LinkedList::addAllAt(LinkedList *l, int index)
{
	Node *tmp;
	Node *tmp2;
	Node *newNode;
	int listCount;
	int i;

	if (index > count-1) {
		cout << "Invalid index" << endl;
		return;
	}
	tmp = this->header;
	for (i = 0; i < index; i++) {
		tmp = tmp->next;
	}
	tmp2 = l->header;
	listCount = l->count;
	while (listCount-- > 0) {
		newNode = new Node(tmp2->data);
		newNode->insert(tmp);
		tmp2 = tmp2->next;
		this->count++;
	}
	if (index == 0) {
		for (i = 0; i < l->count; i++) {
			tmp = tmp->prev;
		}
		this->header = tmp;
	}
}

void LinkedList::print() 
{
	Node *tmp;
	
	if (this->header == NULL) {
		cout << "[]" << endl;
		return;
	}
	tmp = this->header;
	cout << "[" << tmp->data;
	while (tmp->next != this->header) {
		tmp= tmp->next;
		cout << " " << tmp->data;
	}
	cout << "]" << endl;
}

int LinkedList::size()
{
	return this->count;
}

void LinkedList::clear()
{
	Node *tmp;
	if (this->header == NULL) return;
	while (this->header->next != this->header) {
		tmp = this->header->next;
		tmp->remove();
	}
	this->header = NULL;
	this->count = 0;
}

LinkedList *LinkedList::clone()
{
	LinkedList *newList;
	Node *tmp;
	Node *newNode;
	int i;

	newList = new LinkedList();

	tmp = this->header;
	for (i = 0; i < this->count; i++) {
		newList->add(tmp->data);
		tmp = tmp->next;
	}
	newList->count = this->count;

	return newList;
}

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

	tmp = header;
	for (i = 0; i < count; i++) {
		if (tmp->data == x) return true;
		tmp = tmp->next;
	}

	return false;
}

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

	if (header == NULL) return -1;
	tmp = header;
	for (i = 0; i < index; i++) {
		tmp = tmp->next;
	}
	return tmp->data;
}

int LinkedList::getFirst() 
{
	if (header == NULL) return -1;
	return header->data;
}

int LinkedList::getLast() 
{
	if (header == NULL) return -1;
	return header->prev->data;
}

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

	if (header == NULL) return -1;
	tmp = header;
	pos = 0;
	for (i = 0; i < count; i++) {
		if (tmp->data == x) return pos;
		tmp = tmp->next;
		pos++;
	}
	return -1;
}

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

	if (header == NULL) return value;
	pos = 0;
	tmp = header;
	for (i = 0; i < count; i++) {
		if (tmp->data == x) value = pos;
		tmp = tmp->next;
		pos++;
	}

	return value;
}

int LinkedList::element() 
{
	if (header == NULL) return -1;
	return header->data;
}

void LinkedList::set(int index, int x) 
{
	Node *tmp;
	int i;

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

void LinkedList::removeData(int x)
{
	Node *tmp;
	Node *toDelete;
	int i;

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

	cout << "No such element" << endl;	
}

void LinkedList::removeAt(int index)
{
	Node *tmp;
	Node *toDelete;
	int i;

	if (header == NULL) {
		cout << "List is empty" << endl;
		return;
	}
	if (index > count-1) {
		cout << "Index error" << endl;
		return;
	}
	if (index == 0) {
		if (count == 1) {
			toDelete = header;
			header = NULL;
			count = 0;
			delete toDelete;
			return;
		}
		toDelete = header;
		header = header->next;
		count = count - 1;
		toDelete->remove();
		return;
	}
	tmp = header;
	count = count - 1;
	for (i = 0; i < index; i++) {
		tmp = tmp->next;
	}
	tmp->remove();
}

int *LinkedList::toArray() // toArray 문제있을수 있음
{
	int *arr;
	Node *tmp;
	int i;

	arr = new int[count];
	tmp = header;

	for (i = 0; i < count; i++) {
		arr[i] = tmp->data;
		tmp = tmp->next;
		//cout << arr[i] << "xxxxx";
	}

	return arr;
}

Doubly LinkedList 구현 파일이다.

scope resolution operator "::"을 메서드명 앞에 붙여줌으로 해당 객체에 포함된 함수인걸 명시해주는 둥 c++ 형식에 맞게 전체적으로 수정해준다. c에서 parameter로 넘어오던 reference type의 receiver객체에 -> 를 하여 멤버 변수들에 참조하던 것을 this->로 하도록 일괄 변경해준다.(this 생략 가능)

 

내용적인 부분은 아래 링크에 소개되어 있으니 넘어가고 Iterator 부분만 짚고 마무리하겠다.

https://suldenlion.tistory.com/97

(C로 자료구조 구현하기) LinkedList 만들기 (version 2 - Doubly LinkedList)

 

 

list에 값을 넣고 Iterator를 써서 각 데이터들을 알아내보려 한다.

 

위 코드에 대한 결과

 

Iterator에 대한 각각의 operator 연산을 overloading하여 '!=', '*', '==', '++' 등을 수행하게 해주면 된다.

 

 

한줄짜리 코드 != 와 ==은 헤더에 선언과 동시에 정의했다.

 

Iterator의 startFlag 변수는 header노드를 방문하는게 첫번째 인가 아니면 traverse를 한바퀴 돌고 나서 마지막 노드의 다음값인 헤더로 다시한번 방문했는가를 체크하기 위한 용도이다.