//	p.356
//

#include <iostream>

using namespace std;

struct NodeType
{	int info;
	NodeType* next;
	NodeType* back;
};

class List
{
	NodeType* front, * rear;
public:
	List()
	{	front = rear = NULL;	// empty	
	}
	void InsertFront(int item)
	{	
	    if ( front == NULL )
	    {
		// 1. empty case --> one node
		front = new NodeType;
		front->info = item;
		front->next = NULL;
		front->back = NULL;
		rear = front;
	     }
	     else 
  	     {
 		// 2. one node --> two nodes
		NodeType* temp = new NodeType;
		temp->info = item;
		temp->next = front;
		front->back = temp;
		temp->back = NULL;
		front = temp;
		// 3. general
	      }
	}
	void InsertRear(int item )
	{	// empty
		if ( front == NULL )
		{
			front = new NodeType;
                	front->info = item;
                	front->next = NULL;
                	front->back = NULL;
                	rear = front;
		}
		else	// general
		{
			NodeType* temp = new NodeType;
			temp->info = item;
			rear->next = temp;
			temp->back = rear;
			rear = temp;
		}
	}
	void Print() const
	{	// 1. empty
		if ( front == NULL )	cout << "Empty list.\n";
		// 2. general
		else
		{
			NodeType* temp = front;
			while ( temp != NULL )
			{	// out
				cout << temp->info << " ";
				temp = temp->next;	
			}
		}
	}
};	

int main()
{
	List me;

	me.InsertFront(9);
	me.InsertFront(7);
	me.InsertFront(12);

	me.Print();

	me.InsertRear(17);
	me.InsertRear(1);

	cout << "\n\n";
	me.Print();

	cout << "\n\nBye.\n\n";
	return 0;
}