#include <string>
#include <iostream>

using namespace std;

struct DNode
{
	DNode *prev, *next;
	string *data;
	DNode(string* d, DNode *p, DNode *n) {data = d; prev = p; next = n;}
	void print() {cout << *data << " "; }
};

class DList
{
private:
	DNode *header, *trailer; //header must always come first, trailer last.
	long size;
public:
	//initialize empty list with only 2 nodes header and trailer.
	DList() { 
		header = new DNode(NULL, NULL, NULL); 
		trailer = new DNode(NULL, header, NULL); 
		header->next = trailer;
		size = 0;
	}
	
	bool isEmpty() {return size==0; }
	
	//insert a new node to the position after node p
	DNode* insertAfter(string *data, DNode *p) {
		if (p == NULL) return NULL;	//error p cannot be a null pointer
		if (p->next == NULL) return NULL; // error, never insert after trailer
		
		DNode *newNode = new DNode(data, p, p->next);
		p->next->prev = newNode;
		p->next = newNode;	
		size++;
		return newNode;
	}
	
	//remove node p from the list
	string* remove(DNode *p) {
		if (p == NULL) return NULL;
		// header and trailer cannot be removed
		if ((p->next == NULL) || (p->prev == NULL)) return NULL;
		
		p->prev->next = p->next;
		p->next->prev = p->prev;
		string *d = p->data;
		delete p;
		size --;
		
		return d;
	}
	//insert new node to the end of the list
	DNode*  addLast(string *data) { return insertAfter(data, trailer->prev); }
	//insert new node to the beginning of the list
	DNode*  addFirst(string *data) { return insertAfter(data, header); }
	//remove the last node (comes before trailer)
	string* removeLast() { return remove(trailer->prev); }
	//remove the first node
	string* removeFirst() { return remove(header->next); }
	
	void print() {
		DNode *p = header->next;
		cout << "(";
		while (p != trailer) {
			p->print();
			p = p->next;
		}
		cout << ")" << endl;
	}
};

//test program
int main()
{
	DList *l = new DList();
	l->print();
	DNode* a = l->addFirst(new string("a"));
	l->print();
	DNode* b = l->addFirst(new string("b"));
	l->print();
	DNode* c = l->addLast(new string("c"));
	l->print();
	DNode* d = l->insertAfter(new string("d"), a);
	l->print();
	l->removeFirst();
	l->print();
	l->removeLast();
	l->print();
	l->remove(d);
	l->print();
	l->remove(a);
	l->print();
	l->remove(b);
	l->print();
}