#include<iostream>
using namespace std;

template<typename Item>
class Double_List
{
private:
	struct Element
	{
		Item inf;
		Element* next;
		Element* prev;
		Element(Item x):inf(x),next(0),prev(0){}
	};
	Element* head, * tail;
	int size;

	Item* Find(int index) {
		Element* cur = head;
		for (int i = 0, i < size; i++) {
			cur = cur->next;
		}
		return cur;
	}
public:
	Double_List() :head(0), tail(0),size(0){}

	bool Empty() {
		head == 0;
	}
	Item GetLength() {
		return size;
	}
	
	Item Get(int index) {
		if(index < 0 || index >size){
			cout << "Error";
		}
		else {
			Element* cur = Find(index);
			Item value = cur->inf;
			delete cur;
			return value;
		}
	}

	void InsertLeft(int index, Item data) {
		if (index < 0 || index >size) {
			cout << "Error";
		}
		else {
			Element* newPtr = Element(data);
			size = GetLength() + 1;
			Element* cur = Find(index);

			if (cur == NULL) {
				head = newPtr;
				tail = newPtr;
			}
			else {
				newPtr->next = cur;
				newPtr->prev = cur->prev;
				cur->prew = newPtr;
			}
			if (cur == head) {
				head = newPtr;
			}
			else {
				newPtr->prev->next = newPtr;
			}
		}
	}
	void InsertRight(int index, Item data) {
		if (index < 0 || index >size) {
			cout << "Error";
		}
		else {
			Element* newPtr = Element(data);
			size = GetLength() + 1;
			Element* cur = Find(index);

			if (cur == NULL) {
				head = newPtr;
				tail = newPtr;
			}
			else {
				newPtr->next = cur->next;
				newPtr->prev = cur;
				cur->next = newPtr;
			}
			if (cur == tail) {
				tail = newPtr;
			}
			else {
				newPtr->next->prev = newPtr;
			}
		}
	}
	void Remove(int index) {
		Element* cur = Find(index);
		size--;
		if (size==0) {
			head = NULL;
			tail = NULL;
		}
		else if(cur==head) {
			head = head->next;
			head->prev=NULl
		}
		else if (cur == tail) {
			tail=tail->prev;
			tail->next = NULL;
		}
		else {
			cur->prev->next = cur->next;
			cur->next->prev = cur->prev;
		}
	}

};