#include <iostream>
#include <list>

using std::list;
using std::cout;

template <typename T>
class linked_list {
	struct Node {
		T data;
		Node* next;
		Node* prev;

		Node(T val) : data(val), next(nullptr), prev(nullptr) { }
	};

	Node* head;
	Node* tail;

public:
	linked_list() : head(nullptr), tail(nullptr) { }
	~linked_list() { clear(); }

	Node* front() const {
		return head;
	}

	Node* back() const {
		return tail;
	}

	bool empty() const {
		return head == nullptr;
	}

	void push_back(const T& val) {
		if (empty()) {
			head = new Node(val);
			tail = head;
		}
		else if (head == tail) {
			tail = new Node(val);
			head->next = tail;
			tail->prev = head;
		}
		else {
			Node* newNode = new Node(val);
			tail->next = newNode;
			newNode->prev = tail;
			tail = newNode;
		}
	}

	void push_front(const T& val) {
		if (empty()) {
			head = new Node(val);
			tail = head;
		}
		else if (head == tail) {
			head = new Node(val);
			head->next = tail;
			tail->prev = head;
		}
		else {
			Node* newNode = new Node(val);
			newNode->next = head;
			head->prev = newNode;
			head = newNode;
		}
	}

	void pop_back() {
		if (empty()) return;
		if (head == tail) {
			delete head;
			head = tail = nullptr;
		}
		else {
			Node* last = tail->prev;
			last->next = nullptr;
			delete tail;
			tail = last;
		}
	}

	void pop_front() {
		if (empty()) return;
		if (head == tail) {
			delete head;
			head = tail = nullptr;
		}
		else {
			Node* first = head->next;
			first->prev = nullptr;
			delete head;
			head = first;
		}
	}

	void clear() {
		while (head) {
			Node* toDelete = head;
			head = head->next;
			delete toDelete;
		}
	}



};

template <typename T>
class queue {
	T* data;
	unsigned begin, end;
	const unsigned size;
	unsigned capacity;

	void resize() {
		T* newData = new T[capacity * 2];
		for (unsigned i = begin; i < last; ++i) newData[i] = data[i];
		//std::swap(newData, m_arr);
		delete[] data;
		data = newData;
		capacity *= 2;
	}
public:
	queue(unsigned sz = 16) : data(new T[sz + 1]), begin(0), end(0), size(sz + 1) { }
};

int main() {
	linked_list<int> l;
	cout << l.empty() << "\n";
	l.push_back(1);
	l.push_back(2);
	l.push_back(3);
	l.push_back(4);
	l.push_back(5);
	l.push_back(6);
	l.push_back(7);
	l.push_front(0);
	l.push_front(5);
	cout << l.front()->data << "\n";
	//cout << l.back()->data << "\n";
	l.pop_front();
	l.pop_front();
	l.pop_front();
	l.pop_front();
	l.pop_front();
	l.clear();
	cout << l.empty() << "\n";
	//l.pop_back();
	//l.pop_back();
	//l.pop_back();
	//l.pop_back();
	//l.pop_back();
	//cout << l.front()->data << "\n";

	return 0;
}