[C++] 7 - 기초 문법 공부 일지(Array)

• Array
  • 연속된 방을 사용할 수 있지만 방을 추가하거나 축소할 수 없음

0	1	2	3	4	5	6
0	1	2	3	4	5	6
0	1	2	3	4	5	6

Array.h

#pragma once
#include <assert.h>

template<typename T>
class Array
{
public:
	explicit	Array(int capacity = 10) : _capacity(capacity) { _buffer = new T[capacity]; }
				~Array() { delete[] _buffer; }

	void		push_back(const T& index)
	{
		if (_size == _capacity) return;
		_buffer[_size] = index;
		_size++;
	}
	T&			operator[](int index)
	{
		assert(index >= 0 && index < _size);
		return _buffer[index];
	}
	int			size() { return _size; }
	int			capacity() { return _capacity; }

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

main.cpp

#include "pch.h"
#include "Array.h"

int main()
{
	Array<int> array(100);

	array.push_back(100);
	array.push_back(200);
	array.push_back(300);
	array.push_back(400);
	array.push_back(500);

	for (int i = 0; i < array.size(); i++)
		cout << array[i] << endl;
}

• Vector
  
  • 사용할 방 개수를 유동적으로 선택하고 연속된 방을 사용
  • 중간 삽입 삭제가 어려움

0	1	2	3	4	5	6
0	1	2	3	4	5	6
0	1	2	3	4	5	6

Vector.h

#pragma once
#include <assert.h>

template<typename T>
class Vector
{
public:
	explicit	Vector(int capacity = 5) : _capacity(capacity) { _buffer = new T[capacity]; }
				~Vector() { delete[] _buffer; }
	
	void		push_back(const T& index)
	{
		if (_size == _capacity)
		{
			int _new = static_cast<int>(_capacity * 1.5); // 방이 없을 때 1.5배 만큼 방을 추가
			// 곱해도 값이 같은 경우 1 -> 1.5 -> 1
			if (_new == _capacity) _new++;
			reserve(_new); // 새로운 버퍼와 capacity 값 변경
		}

		_buffer[_size] = index;
		_size++;

	}
	void		reserve(int capacity)
	{
		if (_capacity == capacity) return;
		_capacity = capacity;

		T* _new = new T[_capacity];
		for (int i = 0; i < _size; i++)
			_new[i] = _buffer[i];
		delete[] _buffer;
		_buffer = _new;
	}

	T&			operator[](int index)
	{
		assert(index >= 0 && index < _size);
		return _buffer[index];
	}
	int			size() { return _size; }
	int			capacity() { return _capacity; }

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

main.cpp

#include "pch.h"
#include "Vector.h"

int main()
{
	Vector<int> vector(5);

	vector.push_back(100);
	vector.push_back(200);
	vector.push_back(300);
	vector.push_back(400);
	vector.push_back(500);

	for (int i = 0; i < vector.size(); i++)
		cout << vector[i] << endl;
}

• Linked List
  • 연속되지 않는 방을 사용
  • array, vector와 다르게 중간 삽입 및 삭제가 쉽지만 임의 접근 힘듦

0	1	2	3	4	5	6
0	1	2	3	4	5	6
0	1	2	3	4	5	6

template<typename T>
class Node
{
public:
	Node(int data) : _data(data), prev(nullptr), next(nullptr) {}
public:
	T		_data; // 데이터
	Node*	prev; // 이전 노드
	Node*	next; // 다음 노드
};

List.h

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

template<typename T>
class List
{
public:
	explicit List()
	{
		// 첫 데이터에 빈 노드를 생성 - 삭제 삽입할 때 자유로움
		_head = new Node<T>(0);
		_tail = new Node<T>(0);
		_head->next = _tail;
		_tail->prev = _head;
	}
	~List()
	{
		Node<T>* node = _head;
		while (node)
		{
			Node<T>* deleteNode = node;
			node = node->next;
			delete deleteNode;
		}
	}

	Node<T>* AddHead(int data)
	{
		Node<T>* headNextNode = _head->next;
		Node<T>* newNode = new Node<T>(data);

		newNode->next = headNextNode;
		newNode->prev = _head;
		headNextNode->prev = newNode;
		_head->next = newNode;

		return newNode;
	}
	Node<T>* AddTail(int data)
	{
		Node<T>* tailPrevNode = _tail->prev;
		Node<T>* newNode = new Node<T>(data);
		
		newNode->prev = tailPrevNode;
		newNode->next = _tail;
		tailPrevNode->next = newNode;
		_tail->prev = newNode;

		return newNode;
	}

	void Insert(Node<T>* posNode, int data)
	{
		auto* newNode = new Node<T>(data); // c++ 11

		newNode->next = posNode->next;
		newNode->prev = posNode;
		posNode->next = newNode;
	}
	auto* Remove(Node<T>* removeNode)
	{
		auto* prevNode = removeNode->prev;

		prevNode->next = removeNode->next;
		removeNode->next = removeNode->prev;

		delete removeNode;
		return removeNode;
	}

	void Print()
	{
		Node<T>* node = _head->next;
		while (node && node != _tail)
		{
			cout << node->_data << " - ";
			node = node->next;
		}
		cout << endl;
	}

private:
	Node<T>* _head = nullptr; // start
	Node<T>* _tail = nullptr; // end
};

main.cpp

#include "pch.h"
#include "List.h"

int main()
{
	List<int> list;

	list.AddHead(100);
	list.AddHead(200);
	list.Print();

	list.AddTail(300);
	auto preNode = list.AddTail(400);
	list.Print();

	list.Insert(preNode, 1000);
	list.Print();

	list.Remove(preNode);
	list.Print();
}