[C++ algorithm] 배열, 동적배열, 연결리스트

선형 자료구조

선형 구조는 자료를 순차적으로 나열한 형태이다. 배열이나 연결리스트, 스택, 큐 등을 말한다.

비 선형 구조는 하나의 자료 뒤에 다수의 자료가 올 수 있는 형태를 의미한다. 트리나 그래프 등이 있다.

선형 구조는 어떤 언어에서든 구현되어 있다.

배열

배열은 사용할 방 개수를 고정해서 계약하고 절대 변경이 불가능하다. 연속된 방을 배정 받아 사용한다.

장점은 연속된방이라는 점이고 단점은 방을 추가하거나 축소가 불가능하다는 점이다.

호텔에서 우리가 친구 3명이서 체크인 할 때 101호 , 102호, 103호를 배정 받았지만 친구 한명이 갑자기 급한일로 읺 ㅐ집에 가면 103호를 환불 받을 수 없는 것과 동일하다.

동적 배열

동적 배열은 사용할 방 개수를 유동적으로 계약하는 것이다. 이 역시 연속된 방으로 배정 받아 사용한다.

만약 친구 한명이 더 늘어나 104호를 추가적으로 계약하는 것이다. 그런데 단점은 바로 이사 비용이다.

새로운 친구가 재밌게 놀기 위해 이런저런 짐을 많이 가져왔다고 해보자. 그런데 호텔측에서 방이 가득차 다음 층으로 새로운 이동해 달라고 하면 그 짐을 전부 들고 이동해야하는 불편함이 있다.

이 문제를 해결하기 위해 실제로 사용할 방보다 많이, 여유분을 두고 예약을 하는 방식으로 해결해 이사 횟수를 초기화한다.

장점으로는 유동적은 여유분을 추가 할 수 있다는 점이고 단점으로는 중간 삽입삭제가 안된다는 점이다.(느리다.)

연결 리스트

연결 리스트는 연속되지 않은 방을 사용한다. 그렇기 때문에 중간에 삽입하고 삭제하는데 매우 빠른 속도로 동작한다. 하지만 n번째 방을 바로 찾을 수 없고 1번째부터 다 찾아야한다.

 

서로의 장점이 다 있기 때문에 누가 더 좋다고 할 순 없다.

실제로 구현을 하면서 다뤄보겠다.

동적 배열 구현

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

int main()
{
	vector<int> v;
	for (int i = 0; i < 100; i++)
	{
		v.push_back(i);
		cout << v.size() << " " << v.capacity() << endl;
	
	}
	v.clear();
	cout << v.size() << " " << v.capacity() << endl;
}

이것이 vector에서 size와 capacity를 테스트 한 것이다. 위에서 말했듯이 방이 가득 찼을 때 이사할 때 여유분을 1,5배 정도 늘려서 잡는 모습을 볼 수 있다. 

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

template<typename T>
class Vector
{
public:
	Vector()
	{

	}
	~Vector()
	{
		if (_data)
			delete[] _data;
	}

	void push_back(const T& value)
	{
		if (_size == _capacity)
		{
			// 증설 작업
			int newCapacity = static_cast<int>(_capacity * 1.5);
			if (newCapacity == _capacity)
				newCapacity++;
			reserve(newCapacity);
		}
		// 데이터 증가
		_data[_size] = value;
		_size++;
	}
	void reserve(int capacity)
	{
		if (_capacity >= capacity)
			return;
		_capacity = capacity;
		T* newData = new T[_capacity];
		for (int i = 0; i < _size; i++)
		{
			newData[i] = _data[i];
		}
		if (_data)
			delete[] _data;
		_data = newData;
	}
	T& operator[](const int pos) { return _data[pos]; }
	int size() { return _size; }
	int capacity() { return _capacity; }
	void clear()
	{
		if (_data)
		{
			delete[] _data;
			_data = new T[_capacity];
		}
		_size = 0;
	}

private:
	T*	_data = nullptr;
	int _size = 0;
	int _capacity = 0;
};


int main()
{
	Vector<int> v;
	for (int i = 0; i < 100; i++)
	{
		v.push_back(i);
		cout << v.size() << " " << v.capacity() << endl;
	
	}
	v.clear();
	cout << v.size() << " " << v.capacity() << endl;
}

실제로 구현된 vector랑 얼추 비슷하게 구현했다. 물론 실제 vector랑은 많이 다를 수 있지만 동적 배열의 특성인 size와 capacity에 대한 것만 확인할 수 있게 구현한 것이다.

연결 리스트 구현

우리가 연결 리스트와 벡터중 고르라고 하면 90퍼 정도 벡터를 고르게 된다. 그만큼 벡터가 장점이 많다. 하지만 리스트는 다른 자료를 구조를 배울때 사용되는 기본 개념이기 때문에 꼭 알아야한다.

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

template<typename T>
class Node
{
public:
	Node() : _prev(nullptr), _next(nullptr), _data(T())
	{

	}

	Node(const T& value) : _prev(nullptr), _next(nullptr), _data(value)
	{

	}

public:
	Node* _prev;
	Node* _next;
	T		_data;
};

template<typename T>
class Iterator
{
public:
	Iterator() : _node(nullptr)
	{

	}

	Iterator(Node<T>* node) : _node(node)
	{

	}

	// ++it
	Iterator& operator++()
	{
		_node = _node->_next;
		return *this;
	}

	// it++
	Iterator operator++(int)
	{
		Iterator<T> temp = *this;
		_node = _node->_next;
		return temp;
	}

	// --it
	Iterator& operator--()
	{
		_node = _node->_prev;
		return *this;
	}

	// it--
	Iterator operator--(int)
	{
		Iterator<T> temp = *this;
		_node = _node->_prev;
		return temp;
	}

	// *it
	T& operator*()
	{
		return _node->_data;
	}

	bool operator==(const Iterator& other)
	{
		return _node == other._node;
	}

	bool operator!=(const Iterator& other)
	{
		return _node != other._node;
	}

public:
	Node<T>* _node;
};

template<typename T>
class List
{
public:
	List() : _size(0)
	{
		// [head] <-> ... <-> [tail]
		_head = new Node<T>();
		_tail = new Node<T>();
		_head->_next = _tail;
		_tail->_prev = _head;
	}

	~List()
	{
		while (_size > 0)
			pop_back();

		delete _head;
		delete _tail;
	}

	void push_back(const T& value)
	{
		AddNode(_tail, value);
	}

	void pop_back()
	{
		RemoveNode(_tail->_prev);
	}

private:

	// [head] <-> [1] <-> [prevNode] <-> [before] <-> [tail]
	// [head] <-> [1] <-> [prevNode] <-> [newNode] <-> [before] <-> [tail]
	Node<T>* AddNode(Node<T>* before, const T& value)
	{
		Node<T>* newNode = new Node<T>(value);
		Node<T>* prevNode = before->_prev;

		prevNode->_next = newNode;
		newNode->_prev = prevNode;

		newNode->_next = before;
		before->_prev = newNode;

		_size++;

		return newNode;
	}

	// [head] <-> [prevNode] <-> [node] <-> [nextNode] <-> [tail]
	// [head] <-> [prevNode] <-> [nextNode] <-> [tail]
	Node<T>* RemoveNode(Node<T>* node)
	{
		Node<T>* prevNode = node->_prev;
		Node<T>* nextNode = node->_next;

		prevNode->_next = nextNode;
		nextNode->_prev = prevNode;

		delete node;

		_size--;

		return nextNode;
	}

	int size() { return _size; }

public:
	using iterator = Iterator<T>;

	iterator begin() { return iterator(_head->_next); }
	iterator end() { return iterator(_tail); }

	// it '앞에' 추가
	iterator insert(iterator it, const T& value)
	{
		Node<T>* node = AddNode(it._node, value);
		return iterator(node);
	}

	iterator erase(iterator it)
	{
		Node<T>* node = RemoveNode(it._node);
		return iterator(node);
	}

private:
	Node<T>* _head;
	Node<T>* _tail;
	int			_size;
};

int main()
{
	List<int> li;

	List<int>::iterator eraseIt;
	// [ ] <-> [ ] <-> [ ] <-> [ ]  <-> [ ]  <-> [ ]
	for (int i = 0; i < 10; i++)
	{
		if (i == 5)
		{
			eraseIt = li.insert(li.end(), i);
		}
		else
		{
			li.push_back(i);
		}
	}

	li.pop_back();

	li.erase(eraseIt);

	for (List<int>::iterator it = li.begin(); it != li.end(); it++)
	{
		cout << (*it) << endl;
	}

}

iterator까지 직접 구현해본 코드이다. 다 필요 없고 가장 중요한 것은 Node 형태로 관리를 하고 서로 가리키고 있는 것이 매우 중요하다는 것이다. 그리고 중간 삽입 삭제가 매우 빠르다고 말했지만 진짜 그것만 빠른 것이다. 

데이터를 찾고 삭제하는건 여전히 느리다는 것이다. 왜냐면 찾는건 느리기 때문이다. 임의 접근이 안되기 때문이다.