C++ Rookiss Part3 자료구조와 알고리즘 : 선형 자료구조

🙇‍♀️선형 자료구조

🪐선형 vs 비선형

• 선형 구조는 자료를 순차적으로 나열한 상태
  • 배열
  • 연결 리스트
  • 스택 / 큐
• 비선형 구조는 하나의 자료 뒤에 다수의 자료가 올 수 있는 형태
  • 트리
  • 그래프

🪐배열 vs 동적 배열 vs 연결 리스트

• 배열
  • 사용할 방 개수를 고정해서 계약 (변경 불가)
  • 연속된 방으로 배정 받아 사용
  • 장점 : 연속된 방
  • 단점 : 방을 추가 / 축소 불가
• 동적 배열
  • 사용할 방 개수를 유동적으로 계약 (변경 가능)
  • 연속된 방으로 배정 받아 사용
  • 장점 : 연속된 방, 유동적인 계약 (방 여유분 추가 예약으로 이사 횟수 최소화)
  • 단점 : 이사 비용이 크다, 중간 삽입 / 삭제가 비효율적
  • 동적 배열 할당 정책 : 여유분을 두고 예약 -> 이사 횟수를 최소화
• 연결 리스트
  • 비연속 된 방
  • 장점 : 중간 삽입 / 삭제 이점
  • 단점 : N번째 방을 바로 찾을 수가 없음 (임의 접근 Random Access 불가)

임의 접근? => N번째 방이 몇 번 방인지 바로 찾을 수 있는지

🪐배열 만들기

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

	}

	~Vector()
	{

	}

	void push_back(const T& value)
	{
		if (_capacity == _size)
		{
			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;
	}

	void clear()
	{
		if (_data)
		{
			delete[] _data;
			_data = new T[_capacity];

		}

		_size = 0;
	}

	T& operator[](const int value) { return _data[value]; }

	int size() { return _size; }
	int capacity() { return _capacity; }

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

🪐연결 리스트 만들기

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

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

	}

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

	}

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

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

	}

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

	}

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

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

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

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

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

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

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

private:
	Node<T>* _node;
};

template<typename T>
class List
{
public:

	List() : _size(0)
	{
		_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:

	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;
	}

	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); }

	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);
	}

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