Iterator를 지원하는 Double Linked List 구현

#include <iostream>

using namespace std;

//양방향 연결 리스트
template <typename T>
class DList
{
public:
	struct Node
	{
		T _data;
		Node* _next;
		Node* _prev;

		Node() : _data(T()), _next(nullptr), _prev(nullptr) {}
		Node(T data) : _data(data), _next(nullptr), _prev(nullptr) {}
	};

public:
	//양방향 이터레이터
	class Iterator
	{
	public:
		Iterator(Node* node = nullptr) : _node(node) {}
		
		Iterator& operator++()
		{
			if(_node != nullptr)
				_node = _node->_next;
			return *this;
		}
		const Iterator operator++(int)
		{
			Iterator temp = *this;
			if (_node != nullptr)
				_node = _node->_next;
			return temp;
		}
		Iterator& operator--()
		{
			if (_node != nullptr)
				_node = _node->_prev;
			return *this;
		}
		const Iterator operator--(int)
		{
			Iterator temp = *this;
			if (_node != nullptr)
				_node = _node->_prev;
			return temp;
		}

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

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

		Node* _node;
	};

public:
	//생성자
	DList()
		:_size(0), _head(nullptr), _tail(nullptr)
	{
		//더미를 둔다
		_head = new Node;
		_tail = new Node;

		_head->_next = _tail;
		_tail->_prev = _head;
	}

	//소멸자
	~DList()
	{
		while (_size > 0)
		{
			pop_front(); 
		}

		delete _head;
		delete _tail;
	}
	//뒤 삽입
	void push_back(const T& value)
	{
		//노드 생성
		Node* newNode = new Node(value);

		//노드 연결
		newNode->_prev = _tail->_prev;
		newNode->_next = _tail;
		_tail->_prev->_next = newNode;
		_tail->_prev = newNode;

		_size++;
	}
	//앞 삽입
	void push_front(const T& value)
	{
		//노드 생성
		Node* newNode = new Node(value);

		//노드 연결
		newNode->_next = _head->_next;
		newNode->_prev = _head;
		_head->_next->_prev = newNode;
		_head->_next = newNode;

		_size++;
	}
	//중간 삽입
	Iterator Insert(Iterator iter, const T& value)
	{
		//노드 생성
		Node* newNode = new Node(value);
		//iter가 가리키는 노드의 앞에 삽입한다.
		//노드 연결
		newNode->_next = iter._node;
		newNode->_prev = iter._node->_prev;
		iter._node->_prev->_next = newNode;
		iter._node->_prev = newNode;

		_size++;
		return Iterator(newNode);
	}
	
	//뒤 삭제
	void pop_back()
	{
		if (_size <= 0)
		{
			return;
		}

		Node* delNode = _tail->_prev;
		delNode->_prev->_next = _tail;
		_tail->_prev = delNode->_prev;

		delete delNode;

		_size--;
		return;
	}
	//앞 삭제
	void pop_front()
	{
		if (_size <= 0)
		{
			return;
		}

		Node* delNode = _head->_next;
		delNode->_next->_prev = _head;
		_head->_next = delNode->_next;

		delete delNode;

		_size--;
		return;
	}
	//중간 삭제
	Iterator erase(Iterator iter)
	{
		if (_size <= 0)
		{
			return Iterator(_tail);
		}

		//없앤 노드 다음 이터레이터를 반환해야 한다.
		Node* delNode = iter._node;
		Iterator delNextNodeIter = ++iter;
		delNode->_next->_prev = delNode->_prev;
		delNode->_prev->_next = delNode->_next;

		delete delNode;
		_size--;

		return delNextNodeIter;
	}
	
	//크기
	int GetSize() const
	{
		return _size;
	}

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

private:
	Node* _head;
	Node* _tail;
	int _size;
};

 

헤드와 테일은 항상 더미노드를 가리키게 구현했다.

Iterator 패턴을 적용해서 raged-for에서도 활용 가능하다.

 

삽입 삭제를 구현할 때는 차분히 노드들의 앞 뒤 포인터의 변화를 생각하면 

구현할 수 있다.