#include "List.h"
 
#include <string>
#include <iostream>
using namespace std;
 
int main( )
{
        List<int> myIntList;
	cout << "Inserting 1 in the list...\n";
	myIntList.insertFirst(1);	
	myIntList.printList();
	cout << endl;
	system("Pause");
    return 0;
}

#ifndef LIST_H
#define LIST_H
 
template <class T>
class Node
{
public:
	Node(){}
    Node(T theData, Node<T>* theLink) : data(theData), link(theLink){}
    Node<T>* getLink( ) const { return link; }
    const T getData( ) const { return data; }
    void setData(const T& theData) { data = theData; }
    void setLink(Node<T>* pointer) { link = pointer; }
private:
    T data;
    Node<T> *link;
};
 
template <class T>
class List
{
public:
	List( );
	//Default constructor.
	//Initializes the list to an empty list.
 
	bool isEmpty();
	//Checks whether the list is empty.
 
	void insertFirst(const T& newData);
	//Inserts a new node at the beginning of the list
	//param T& - new data
 
	void printList();
	//Print out the list
 
	void insertLast(const T& newData);
	//Inserts a new node at the end of the list.
 
	int length( );
	//Returns the length of the list.
 
	T front( );
	//Returns the information contained in the first node.
 
	T back( );
	//Retruns the information contained in the last node.
 
	bool search(const T item);
	//Searches the list for a given item.
	//This is a sequential search.	
 
	void deleteNode(const T& deleteItem);
	//Delete a node from the list with a given info.
 
	void copyList(List<T>& otherList);
	//Make an identical copy of the list
 
	void destroyList( );
	//Deallocates the memory occupied by each node.
 
	void initializeList( );
	//Initializes the list to an empty state. 
	//Note that the default constructor has already initialized
	//  the list when the list object was declared.
 
	~List( );   
	//Destructor destroys the list and returns
	//   all the memory to the freestore when
	//   the class goes out of scope.
 
private:		
	Node<T> *first;
	//pointer to the first node of the list
	Node<T> *last;
	//pointer to the last node of the list
	int count;
	//stores the number of elements in the list
};
 
#endif

 
#include "List.h"
 
#include<iostream>
using namespace std;
 
template <class T>
List<T>::List()
{
	first = NULL; 
	last = NULL;
	count = 0;
}
 
template <class T>
bool List<T>::isEmpty()
{
	return (first == NULL);
}
 
template <class T>
void List<T>::insertFirst(const T& newData){
	first = new Node(newData, first);
	++count;
}
 
template <class T>
void List<T>::printList(){
	Node<T> *tempt;
	tempt = first;
	while(tempt != NULL){
		cout << tempt->getData() << " ";
		tempt = tempt->getLink();
	}
}
 
template <class T>
void List<T>::insertLast(const T& newData)
{
	Node<T> *newNode;				//pointer to create the new node	
	newNode = new Node;			//create the new node	
 
	newNode->setData(newData);	//store new data in the node	
	newNode->setLink(NULL);		//insert new node at the end pointing to NULL	
 
	if (first == NULL)			//if the list is empty, newNode is
								//  both the first and last node
	{
		first = newNode;
		last = newNode;
		++count;
	}
	else						//the list is not empty, insert
								//  newNode after the last node
	{
		last->setLink(newNode); //insert newNode after last
		last = newNode;			//make last point to the actual last node
		++count;
	}
}
 
template <class T>
int List<T>::length( )
{
	return count;
}
 
template <class T>
T List<T>::front( )
{
	return first->getData(); //return the info of the
							 //  first node
}
 
template <class T>
T List<T>::back( )
{
	return last->getData(); //return the info of the
							//  last node
}
 
template <class T>
bool List<T>::search(const T itemToSearch)
{
	Node<T> *current;		//pointer to traverse the list
	bool found;
	current = first;	//set current to point to the 
						//  first node in the list
	found = false; 
 
	while(current != NULL && !found)			//search the list
		if (current->getData() == itemToSearch)	//the item is found
			found = true;
		else									//otherwise
			current = current->getLink();		//  make current point
												//  to the next node
	return found;
}
 
template <class T>
void List<T>::deleteNode(const T& deleteItem)
{
	Node<T> *current;				//pointer to traverse the list
	Node<T> *trailCurrent;			//pointer just before current
	bool found;
 
	if(first == NULL)			//CASE 1; list is empty
		cerr << "Cannot delete from an empty list.\n";
	else
	{							//CASE 2: delete first node 
		if(first->getData() == deleteItem) 
		{
			current = first;
			first = first->getLink();
			--count;
			if(first == NULL)   //list has only one node
				last = NULL;
			delete current;
		}
		else  //search the list for the node with the given info
		{
			found = false;
			trailCurrent = first;		//set trailCurrent to point to
										//  the first node
			current = first->getLink(); //set current to point to the 
    									//  second node
 
			while(current != NULL && !found)
			{
  				if(current->getData() != deleteItem) 
				{
					trailCurrent = current;
					current = current->getLink();
				}
				else
					found = true;
			} // end while
 
			if(found) //CASE 3; if found, delete the node
			{
				trailCurrent->setLink(current->getLink());
				--count;
 
				if(last == current)			//node to be deleted was 
											//  the last node
					last = trailCurrent;	//update the value of last
 
				delete current;				//delete the node from the list
			}
			else
				cout << "Item to be deleted is not in the list." << endl;
		} 
	} 
} 
 
template <class T>
void List<T>::copyList(List<T>& otherList)
{
   Node<T> *newNode;		//pointer to create a node
   Node<T> *current;		//pointer to traverse the list
 
   if(first != NULL)	//if the list is non-empty, make it empty
	  destroyList();
 
   if(otherList.first == NULL) //otherList is empty
   {
		first = NULL;
		last = NULL;
 		count = 0;
   }
   else
   {
		current = otherList.first;  //current points to the 
									//list to be copied
		count = otherList.count;
 
		//copy the first node
		first = new Node;			 //create the node
 
		first->setData(current->getData()); //copy the info
		first->setLink(NULL);  				//set the link field of 
											//  the node to NULL
		last = first;    					//make last point to the 
            								//  first node
		current = current->getLink();		//make current point to  
           									//  the next node
 
		//copy the remaining list
		while(current != NULL)
		{
			newNode = new Node;		//create a node
 
			newNode->setData(current->getData()); //copy the info
			newNode->setLink(NULL);   	//set the link of 
											//  newNode to NULL
			last->setLink(newNode); 		//attach newNode after last
			last = newNode;   				//make last point to
											//  the actual last node
			current = current->getLink();	//make current point to
       										//  the next node
		}
	}
}
 
template <class T>
void List<T>::destroyList( )
{
	Node<T> *temp;						//pointer to deallocate the 
									//  memory occupied by the node
	while(first != NULL)			//while there are nodes in the list
	{
		temp = first;				//set temp to the current node
		first = first->getLink();	//advance first to the next node
		delete temp;				//deallocate the memory occupied by temp
	}
 
	last = NULL;	//iniitialize last to NULL
					//  (first has already been set to NULL
					//		by the while loop)
	count = 0;
}
 
template <class T>
void List<T>::initializeList( )
{ 
	destroyList( );		//if the list has any nodes,
						//   delete them
}
 
template <class T>
List<T>::~List( )
{
	destroyList();
}

#include "List.h"
 
#include <string>
#include <iostream>
using namespace std;
 
int main( )
{
 
	List<int> myIntList;
 
	system("Pause");
    return 0;
}

#ifndef LIST_H
#define LIST_H
 
 
template <class T>
class List
{
public:
	List();
};
 
#endif

#include "List.h"
 
#include<iostream>
using namespace std;
 
template <class T>
List<T>::List()
{
}