#include <iostream>
using namespace std;

template<class T>
class List {
	struct Elem {
		T data_;
		Elem* next_;
		Elem* prev_;

		Elem(T val)
		: data_(val),
		  next_(0),
		  prev_(0)
		{}
	};

	Elem* head_;
	Elem* tail_;
public:
	List()
	: head_(0),
	  tail_(0)
	{}

	List(const List& other) {
		Elem* node = other.head_;
		while(node != NULL) {
			push_back(node->data_);
			node = node->next_;
		}
	}

	List& operator=(const List& other) {
		Elem* node = other.head_;
		while(node != NULL) {
			push_back(node->data_);
			node = node->next_;
		}
	}

	~List() {
		while(!empty()) {
			pop_front();
		}

		delete head_;
	}

	void push_back(const T& val) {
		Elem* node = new Elem(val);
		if(head_ == 0) {
			node->prev_ = NULL;
			head_ = node;
			tail_ = node;
		} else {
			node->prev_ = tail_;
			tail_->next_ = node;
			tail_ = node;
		}

		tail_->next_ = NULL;
	}

	void pop_back() {
		tail_ = tail_->prev_;
		tail_->next_ = NULL;
	}

	void pop_front() {
		head_ = head_->next_;
	}

	void push_front(const T& val) {
		Elem* node = new Elem(val);
		head_->next_->prev_ = node;
		node->next_ = head_;
		head_ = node;
	}

	T& front() {
		return head_->data_;
	}

	const T& front() const {
		return head_->data_;
	}

	T& back() {
		return tail_->data_;
	}

	const T& back() const {
		return tail_->data_;
	}

	int size() const {
		Elem* node = head_;
		int size = 0;

		while(node != NULL) {
			size++;
			node = node->next_;
		}

		return size;
	}

	bool empty() const {
		return size() == 0;
	}

	class iterator {
		Elem* node_;
		iterator(Elem* ptr)
		: node_(ptr)
		{}

		friend class List;
	public:
		iterator operator++() {
			node_ = node_->next_;
			return *this;
		}

		iterator operator++(int) {
			iterator res = *this;
			operator++();
			return res;
		}

		bool operator==(const iterator& other) const {
			return node_ == other.node_;
		}

		bool operator!=(const iterator& other) const {
			return !operator==(other);
		}

		T& operator*() {
			return node_->data_;
		}

		T* operator->() {
			return node_->data_;
		}
	};

	iterator begin() {
		return iterator(head_);
	}

	iterator end() {
		return iterator(tail_);
	}

	void pretty_print() {
		Elem* temp = head_;

		while(temp != NULL) {
			cout << temp->data_ << " ";
			temp = temp->next_;
		}

		cout << endl;
	}
};

int main() {
	List<int> l;
	l.push_back(1);
	l.push_back(2);
	l.push_back(3);
	l.push_back(4);
	l.push_front(5);
	l.pretty_print();

	return 0;
}