C++ Rookiss Part1 C++ 프로그래밍 입문 : List

🙇‍♀️List

🪐List

#include <iostream>
using namespace std;
#include <vector>
#include <list>
// 오늘의 주제 : list

template<typename T>
class Node
{
public:
	Node() : _next(nullptr), _prev(nullptr), _data(T()) // T() 로 초기화 함
	{

	}

	Node(const T& value) : _next(nullptr), _prev(nullptr), _data(value) // const T& 로 참조 값을 받는다
	{

	}

public:
	Node*	_next; // 노드만 생각 했을 때 앞 뒤 데이터만 들고있다
	Node*	_prev;
	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;
	}

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

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

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

public:
	Node<T>* _node; // iterator는 Node<T>* 만 멤버변수로 들고있다
};

//   <-> [ header ] <-> 
// [1] <-> [2] <-> [3] <-> [4] <-> [ header ] <-> 
template<typename T>
class List
{
public:
	List() : _size(0)
	{
		_header = new Node<T>(); // 앞 뒤 노드를 자기자신을 들고있다
		_header->_next = _header;
		_header->_prev = _header;
	}

	~List()
	{
		while (_size > 0) // 크기가 없어질 때 까지 값 뺴주기
			pop_back();

		delete _header; // 헤더 삭제
	}

	void push_back(const T& value)
	{
		AddNode(_header, value);
	}
	
	void pop_back()
	{
		RemoveNode(_header->_prev);
	}

	// [node] <-> [ header ] <->
	// [1] <-> [2] <-> [before] <-> [4] <-> [ header ] <-> 
	// [1] <-> [prevNode] <-> [node] <-> [before] <-> [4] <-> [ header ] <-> 
	Node<T>* AddNode(Node<T>* before, const T& value) // 노드들은 포인터 값!
	{
		Node<T>* node = new Node<T>(value); // 받은 값으로 새로운 노드를 생성

		Node<T>* prevNode = before->_prev; // 이전 노드를 저장
		prevNode->_next = node; // 이전 노드의 다음을 새로운 노드로 저장
		node->_prev = prevNode; // 새로운 노드의 이전을 이전 노드로 저장해 연결

		node->_next = before; // 새로운 노드의 다음을 before로 저장
		before->_prev = node; // before의 이전을 새로운 노드로 저장해 연결

		_size++; // 크기 증가

		return node; // 새로운 노드 리턴
	}

	// [1] <-> [prevNode] <-> [node] <-> [nextNode] <-> [ header ] <-> 
	// [1] <-> [prevNode] <-> [nextNode] <-> [ header ] <-> 
	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:

	typedef Iterator<T> iterator; // typedef Iterator<T>로 반복자 들고있기 이렇게 하면 벡터등 이터레이터와 이름을 맞출수있다

	iterator begin() { return iterator(_header->_next); } // 시작은 헤더의 다음 노드와 같다
	iterator end() { return iterator(_header); } // 끝 값은 헤더

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

	return 0;
}