C++ LinkedList 만들기 (version 1)

C에 이어 C++로 LinkedList를 구현해 보도록 하겠다.

 

LinkedList의 거의 모든 메서드의 동작 메커니즘은 아래 글에서 소개가 되어있다.

https://suldenlion.tistory.com/88

약간의 추가된 요소나 메서드들, 그리고 C++로 파일을 나눠서 작성한 코드 방식 등을 포스팅 해보겠다.

 

바로 메인 함수 코드를 보면서 어떤 함수들을 사용했는지 보겠다.

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

void main()
{
	LinkedList list1;
	LinkedList *list2 = new LinkedList();

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

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

	list1.addAllAt(list2, 3);

	//list1.clear();
	//list1 = *list2->clone();

	//cout << list1.contains(300) << endl; //출력시 1,0

	//cout << "list2의 First element : " << list2->element() << endl;

	//cout << "list1 0번째 index element get한 결과 : " << list1.get(0) << endl;
	//cout << "list1 getFirst한 결과 : " << list1.getFirst() << endl;
	//cout << "list1 getLast한 결과 : " << list1.getLast() << endl;

	//cout << "list1의 indexOf(200) 한 결과 : " << list1.indexOf(999) << endl;
	list1.add(20);
	list1.add(20);
	list1.add(30);
	//list1.offer(3000);
	//list1.offerFirst(1000);
	//list1.offerLast(5000);

	//cout << "list1의 peek() 값 : " << list1.peek() << endl;
	//cout << "list1의 peekFirst() 값 : " << list1.peekFirst() << endl;
	//cout << "list1의 peekLast() 값 : " << list1.peekLast() << endl;

	//cout << "list1의 poll() 값 : " << list1.poll() << endl;
	//cout << "list1의 pollFirst() 값 : " << list1.pollFirst() << endl;
	//cout << "list1의 pollLast() 값 : " << list1.pollLast() << endl;

	//cout << "list1의 lastIndexOf(20) 한 결과 : " << list1.lastIndexOf(20) << endl;

	//cout << "list2의 remove() 한 결과 값 : " << list2->remove() << endl;
	//cout << "list2의 remove() 한 결과 값 : " << list2->remove() << endl;
	//cout << "list2의 remove() 한 결과 값 : " << list2->remove() << endl;

	//cout << "list2의 removeAt(1) 한 결과 값 : " << list2->removeAt(1) << endl;
	//cout << "list1의 remove(20) 한 결과 값 : " << list1.remove(20) << endl;

	//cout << "list1의 removeFirst() 한 결과 값 : " << list1.removeFirst() << endl;
	//cout << "list2의 removeFirst() 한 결과 값 : " << list2->removeFirst() << endl;
	//cout << "list2의 removeLast() 한 결과 값 : " << list2->removeLast() << endl;

	//list1.set(0, 123);

	cout << "Size of list1 = " << list1.size() << endl;
	cout << "Size of list2 = " << list2->size() << endl;

	cout << "list1 = " << list1;
	cout << "list2 = " << *list2;

	int* arr = list1.toArray();
	cout << "list1.toArray() = [ ";
	for (int i = 0; i < list1.size(); i++) {
		cout << arr[i] << " ";
	}
	cout << "]";
}

이것저것 LinkedList가 가지고 있는 함수들을 API를 참조하여 하나 구현해보고 하나 실행하는 식으로 테스트 하였다.

list에 값을 넣거나 뺄 때 경계값에서 문제가 생길 수 있으므로 (list가 비어있거나 list 끝에서 작업하는 경우) 그런 경우의 데이터도 넣어가면서 테스트 해봤다. 리펙토링은 필요하겠지만 일단 기능상으로 문제가 없는듯 하다.

 

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

class LinkedList;

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

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; }
	friend ostream& operator<<(ostream& out, LinkedList &l);
};

헤더 파일이다.

맨 윗 라인에 #pragma once 라는 전처리기 명령어가 있는데, #ifndef ~ #endif의 기능과 같다. 컴파일러에 헤더파일이 한번만 포함되도록 해준다. Visual Studio의 클래스 마법사를 통해 LinkedList 헤더파일과 cpp파일을 동시에 만드니 자동으로 적힌다.

iostream include와 std 매크로설정은 LinkedList의 toString() 의 역할을 할 ostream& operator<< 사용을 위해 정의해준다.

LinkedList에서 사용할 함수들을 public으로 나열해 주겠다.

 

#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;
	int value;

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

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

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

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

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

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

LinkedList의 메서드들을 구현한 cpp파일이다.

 

대부분 메서드들 구현에 대한 설명은 아래 페이지에 해놓았다.

https://suldenlion.tistory.com/88

 

추가로 정리해보고자 하는 내용 >

poll(), pollFirst(), pollLast() 등은 getFirst(), getLast()의 기능과 같아서 그대로 함수 호출을 해주는 식으로 처리했다.

add()와 offer에 관한 내용도 마찬가지다.

여기서 든 의문은 왜 같은 기능을 하는 함수들이 반복적으로 나타나고 또 정의되어 있는가 였다.

이는 이제 상위 인터페이스들을 상속하는 과정에서 발생하는 것들인데, LinkedList는 List도 상속받고 Queue도 상속받는 이유에 있다.

그래서 같은 동작을 하는 다른 이름의 함수가 각각 존재하는 것이다. 

 

또한 웹서칭을 통해 본 다른 차이점으로는 add(), remove(), element() 등의 메서드는 사용에 실패한 경우에 exception을 날려준다고 하고, offer(), poll(), peek() 등은 null과 같은 값을 리턴해 준다고 한다. 즉, 반환값 처리의 차이를 가지고 있다고 한다.