using#ifndef H_LinkedListType
#define H_LinkedListType
#include "stdafx.h"
#using <mscorlib.dll>
#include <iostream>
#include <cassert>
using namespace std;

template <class Type>
struct nodeType
{
	Type info;
	nodeType<Type> *link;
};

template<class Type>
class linkedListType
{
	friend ostream& operator<<(ostream&, const linkedListType<Type>&);

public:
    const linkedListType<Type>& operator=
          			      (const linkedListType<Type>&); 
		//Overload the assignment operator.
    void initializeList(); 
 		//Initializes the list to an empty state.
	    //Postcondition: first = NULL, last = NULL,
		//                count = 0
    bool isEmptyList();
 		//Function to determine whether the list is empty. 
		//Postcondition: Returns true if the list is empty;
		//               otherwise, returns false.

	int length();
		//Function to return the number of nodes in the 
		//list.
		//Postcondition: The value of count is returned.
    void destroyList();
 		//Function to delete all the nodes from the list.
  		//Postcondition: first = NULL, last = NULL, 
		//               count = 0
    Type front(); 
 		//Function to return the first element of the list.
 		//Precondition: The list must exist and must not be
		//empty.
  		//Postcondition: If the list is empty, then the 
 		//               program terminates; otherwise, 
	    //               the first element of the list is 
		//               returned.
    Type back(); 
       //Function to return the last element of the
       //list.
		//Precondition: The list must exist and must not
		//be empty.
		//Postcondition: If the list is empty, then the 
		//               program terminates; otherwise,
		//               the last element of the list is 
		//               returned.

   bool search(const Type& searchItem);
		//Function to determine whether searchItem is in 
		//the list.
		//Postcondition: Returns true if searchItem is found
		//               in the list; otherwise, it returns
		//               false.

    void insertFirst(const Type& newItem);
		//Function to insert newItem in the list.
		//Postcondition: first points to the new list 
		//                and newItem is inserted at the
		//                beginning of the list.

    void insertLast(const Type& newItem);
		//Function to return newItem at the end of the
		//list.
	    //Postcondition: first points to the new list, 
		//                newItem is inserted at the end
		//                of the list, and last points to
		//                the last node in the list.

    void deleteNode(const Type& deleteItem);
  		//Function to delete deleteItem from the list.
 		//Postcondition: If found, the node containing 
   		//               deleteItem is deleted from the 
		//                list, first points to the first
		//                node, and last points to the last 
		//                node of the updated list. 
//////////////////////////////////////////////////////////////////
///////////////////////////////H E L P ///////////////////////////
//////////////////////////////////////////////////////////////////
	Type getKThElement(int k); 
		//Function to search list for the n'th node in the list
		//Postcondition: When found display info
	
	void deteteKthElement(int k);
		//Function used to delete the n'th number node in the list
//////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////

    linkedListType(); 
   		//default constructor
 		//Initializes the list to an empty state.
 		//Postcondition: first = NULL, last = NULL, 
		//               count = 0 

    linkedListType(const linkedListType<Type>& otherList); 
         //copy constructor

    ~linkedListType();   
    	//destructor
   		//Deletes all the nodes from the list.
    	//Postcondition: The list object is destroyed. 

protected:
    int count;		//variable to store the number of 
 					//elements in the list
    nodeType<Type> *first; //pointer to the first node of 
                           //the list
    nodeType<Type> *last;  //pointer to the last node of 
                           //the list 
private:
    void copyList(const linkedListType<Type>& otherList); 
		//Function to make a copy of otherList.
		//Postcondition: A copy of otherList is created 
		//               and assigned to this list.
};

template<class Type>
bool linkedListType<Type>::isEmptyList()
{
	return(first == NULL);
}

template<class Type>
linkedListType<Type>::linkedListType() // default constructor
{
	first = NULL;
	last = NULL;
	count = 0;
}

template<class Type>
void linkedListType<Type>::destroyList()
{
	nodeType<Type> *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->link; //advance first to the next node
	   delete temp;         //deallocate memory occupied by temp
	}

	last = NULL;	//initialize last to NULL; first has already
                   //been set to NULL by the while loop
 	count = 0;
}

	
template<class Type>
void linkedListType<Type>::initializeList()
{
	destroyList(); //if the list has any nodes, delete them
}

template<class Type>
int linkedListType<Type>::length()
{
 	return count;
}  // end length

template<class Type>
Type linkedListType<Type>::front()
{   
    assert(first != NULL);
   	return first->info; //return the info of the first node	
}//end front


template<class Type>
Type linkedListType<Type>::back()
{   
	 assert(last != NULL);
   	 return last->info; //return the info of the first node	
}//end back

template<class Type>
bool linkedListType<Type>::search(const Type& searchItem)
{
    nodeType<Type> *current; //pointer to traverse the list
    bool found;

    current = first; //set current to point to the 
                     //first node in the list
    found = false;   //set found to false

    while(current != NULL && !found)		//search the list
        if(current->info == searchItem)     //item is found
           found = true;
        else
           current = current->link; //make current point 
                                    //to the next node
     
     return found;
}//end search
/////////////////////////////////////////////////////////////////
/////////////////////////////H E L P/////////////////////////////
/////////////////////////////////////////////////////////////////
template<class Type>
Type getKThElement(int k)
{
// User enters a number 
// Traverse list until you have reached users number (for loop?)
// Display result
}
/////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////
template<class Type>
void linkedListType<Type>::insertFirst(const Type& newItem)
{
	nodeType<Type> *newNode; //pointer to create the new node

	newNode = new nodeType<Type>; //create the new node

	assert(newNode != NULL);	//If unable to allocate memory, 
 								//terminate the program

	newNode->info = newItem; 	   //store the new item in the node
	newNode->link = first;        //insert newNode before first
	first = newNode;              //make first point to the 
                                 //actual first node
	count++; 			   //increment count

	if(last == NULL)   //if the list was empty, newNode is also 
                      //the last node in the list
		last = newNode;
}

template<class Type>
void linkedListType<Type>::insertLast(const Type& newItem)
{
	nodeType<Type> *newNode; //pointer to create the new node

	newNode = new nodeType<Type>; //create the new node

	assert(newNode != NULL);	//If unable to allocate memory, 
 							//terminate the program

	newNode->info = newItem;      //store the new item in the node
	newNode->link = NULL;         //set the link field of newNode
         						//to NULL

	if(first == NULL)	//if the list is empty, newNode is 
     					//both the first and last node
	{
		first = newNode;
		last = newNode;
		count++;		//increment count
	}
	else			//the list is not empty, insert newNode after last
	{
		last->link = newNode; //insert newNode after last
		last = newNode;   //make last point to the actual last node
		count++;		//increment count
	}
}//end insertLast
////////////////////////////////////////////////////////////////////
/////////////////////////////////H E L P////////////////////////////
////////////////////////////////////////////////////////////////////
void deteteKthElement(int k)
{
//User enters number
//Traverse list until you reach that node
//Delete node
}
////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////
template<class Type>
void linkedListType<Type>::deleteNode(const Type& deleteItem)
{
	nodeType<Type> *current; //pointer to traverse the list
	nodeType<Type> *trailCurrent; //pointer just before current
	bool found;

	if(first == NULL)    //Case 1; list is empty. 
		cerr<<"Can not delete from an empty list.\n";
	else
	{
		if(first->info == deleteItem) //Case 2 
		{
			current = first;
			first = first->link;
			count--;
			if(first == NULL)    //list had 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->link;  //set current to point to the 
    			   //second node
	
			while((!found) && (current != NULL))
			{
  				if(current->info != deleteItem) 
				{
					trailCurrent = current;
					current = current-> link;
				}
				else
					found = true;
			} // end while

			if(found) //Case 3; if found, delete the node
			{
				trailCurrent->link = current->link;
				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;
		} //end else
	} //end else
} //end deleteNode


	//Overloading the stream insertion operator
template<class Type>
ostream& operator<<(ostream& osObject, const linkedListType<Type>& list)
{
	nodeType<Type> *current; //pointer to traverse the list

	current = list.first;   //set current so that it points to 
					   //the first node
	while(current != NULL) //while more data to print
	{
	   osObject<<current->info<<" ";
	   current = current->link;
	}

	return osObject;
}

template<class Type>
linkedListType<Type>::~linkedListType() // destructor
{
	destroyList(); 
}//end destructor


template<class Type>
void linkedListType<Type>::copyList
            	      (const linkedListType<Type>& otherList) 
{
   nodeType<Type> *newNode; //pointer to create a node
   nodeType<Type> *current; //pointer to traverse the list

   if(first != NULL)	//if list is nonempty, 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 nodeType<Type>;  //create the node

 		assert(first != NULL);

		first->info = current->info; //copy the info
		first->link = NULL;  	     //set the link field of 
									 //the node to NULL
		last = first;    		     //make last point to the 
            						 //first node
		current = current->link;     //make current point to the 
           							 //next node

			//copy the remaining list
		while(current != NULL)
		{
			newNode = new nodeType<Type>;  //create a node

			assert(newNode!= NULL);

			newNode->info = current->info;	//copy the info
			newNode->link = NULL;   	    //set the link of 
                                        //newNode to NULL
			last->link = newNode; 		//attach newNode after last
			last = newNode;   			//make last point to
										//the actual last node
			current = current->link;	//make current point to
       									//the next node
		}//end while
	}//end else
}//end copyList


	//copy constructor
template<class Type>
linkedListType<Type>::linkedListType
            	      (const linkedListType<Type>& otherList) 
{
	first = NULL;

	copyList(otherList);
	
}//end copy constructor

	//overload the assignment operator
template<class Type>
const linkedListType<Type>& linkedListType<Type>::operator=
   	 	 		(const linkedListType<Type>& otherList)
{ 
     
	if(this != &otherList) //avoid self-copy
	{
		copyList(otherList);
	}//end else

	return *this; 
}

int _tmain()
{
	return 0;
}

template<class Type>
linkedListType<Type>::linkedListType() // default constructor
{
	first = NULL;
	last = NULL;
	count = 0;
}

template<class Type>
void linkedListType<Type>::copyList
            	      (const linkedListType<Type>& otherList) 
{
   nodeType<Type> *newNode; //pointer to create a node
   nodeType<Type> *current; //pointer to traverse the list

   if(first != NULL)	//if list is nonempty, 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; 

int _tmain()
{
	return 0;
}

	nodeType *current = first->link;
	nodeType *trail = first;
    
	for (int i = 0; i < pos; i++)
	{
		current = current->link;
		trail = trail->link;
	}
	
	if (first == NULL)
	{
		cout << "List is Empty" << endl;
	}
	else 
	{
		if (current->link != NULL)
		{
			trail = current->link;
			delete current;
		}
		else (current->info == NULL)
		{
			trail->link = NULL;
			delete current;
		}
	}

nodeType *current = first->link;
nodeType *trail = first;

for (int i = 0; i < pos; i++)
{
	current = current->link;
	trail = trail->link;
}

if (first == NULL)
{
	cout << "List is Empty" << endl;
}

if (current->link != NULL)

using#ifndef H_LinkedListType
#define H_LinkedListType
#include "stdafx.h"
#include <string>
#include <fstream>
#include <iostream>
#include <cassert>
using namespace std;

struct nodeType
{
	string info;
	nodeType *link;
};

class linkedListType
{
	friend ostream& operator<<(ostream&, const linkedListType&);

public:
    const linkedListType& operator=(const linkedListType&); 
    void initializeList(); 
    bool isEmptyList();
    int length();
    void destroyList();
    void insertFirst(string name);
    void insertLast(string name);

///////////////////////////////H E L P ///////////////////////////
	void getKThElement(int pos); 
	void linkedListType::Display_List();
	void deteteKthElement(int pos);
//////////////////////////////////////////////////////////////////

    linkedListType(); 
    ~linkedListType();   
 
protected:
    int count;		
    nodeType *first; 
    nodeType *last;  
};

bool linkedListType::isEmptyList()
{
	return(first == NULL);
}

linkedListType::linkedListType()// default constructor
{
	first = NULL;
	last = NULL;
	count = 0;
}

void linkedListType::destroyList()
{
	nodeType *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->link; //advance first to the next node
	   delete temp;         //deallocate memory occupied by temp
	}

	last = NULL;	//initialize last to NULL; first has already
                   //been set to NULL by the while loop
 	count = 0;
}

void linkedListType::initializeList()
{
	destroyList(); //if the list has any nodes, delete them
}

int linkedListType::length()
{
 	return count;
}  // end length

////////////////////////////Help//////////////////////////////
void linkedListType::Display_List()
{  
	nodeType *temp;
	last = NULL;
    temp = first;
	
     
	cout << endl;
    if (first == NULL)
	cout << "The list is empty!" << endl;
    else
		{ 
			while (temp != NULL)
			{  
			// Display details for what temp points to
			cout << "Name: " << temp->info << flush;
		//	if (temp == current)
		//	cout << " <-- Current node";
		//	cout << endl;
			temp = temp->link;
	   }
	 cout << "End of list!" << endl;
     }
  }
/////////////////////////////H E L P///////////////////////////
void linkedListType::getKThElement(int pos)
{   
	nodeType *current = first->link;
	nodeType *trail = first;
	bool found;
	int count = 0;
    
	if (first == NULL)//First check if the list is empty....
	{
		cout << "The list is Empty!" << endl;
	}
	else
	{
		if (pos == count && pos == NULL)//Then check to see if pos is the last
		{								//node
			current = first; //set current to the first node
			first = first->link; //set first to the second node
			count--;//update count
			if(first == NULL)    //list had only one node
				last = NULL; //set last to NULL(0)
			delete current; //delete the current node
		}
		else
		{
			found = false;
			current = first->link;  //set current to point to the 
    
			//Search for node
			while((!found) && (current != NULL))//While found is false && current is 
			{									//not the last node 
  				    count++;  //get the total number of nodes
					current = current-> link; //advance through the list
			} 

			if(count >= pos) //Check to see if pos is found 
			{
				found = true; //if so its there
			}
			else
			{
				cout<<"Count > than pos";
			//	return 0;
			}

			if(found) //if found then delete the node
			{
				current=first;
				for(count=0; count != pos; count++)
				{
					trail=current;
					current = current-> link;
				}
				if(last == current)      //node to be deleted was 
                                     //the last node
					last = trail;  //Another special case update the value of last
				else
				{
					trail->link = current->link;
				}					
				cout << "You just found: " << current->info << endl;  
			}
			else
				cout<<"Item to be found is not in the list."<<endl;
		}
	} 
}
/////////////////////////////////////////////////////////////////

void linkedListType::insertFirst(string name)
{
	nodeType *newNode; //pointer to create the new node

	newNode = new nodeType; //create the new node

	assert(newNode != NULL);	//If unable to allocate memory, 
 								//terminate the program

	newNode->info = name; 	   //store the new item in the node
	newNode->link = first;        //insert newNode before first
	first = newNode;              //make first point to the 
                                 //actual first node
	count++; 			   //increment count

	if(last == NULL)   //if the list was empty, newNode is also 
                      //the last node in the list
		last = newNode;
}

/////////////////////////////////H E L P////////////////////////////
void linkedListType::deteteKthElement(int pos)
{
	nodeType *current = first->link;
	nodeType *trail = first;
	bool found;
	int count = 0;
    
	if (first == NULL)//First check if the list is empty....
	{
		cout << "The list is Empty!" << endl;
	}
	else
	{
		if (pos == count && pos == NULL)//Then check to see if pos is the last
		{								//node
			current = first; //set current to the first node
			first = first->link; //set first to the second node
			count--;//update count
			if(first == NULL)    //list had only one node
				last = NULL; //set last to NULL(0)
			delete current; //delete the current node
		}
		else
		{
			found = false;
			current = first->link;  //set current to point to the 
    
			//Search for node
			while((!found) && (current != NULL))//While found is false && current is 
			{									//not the last node 
  				    count++;  //get the total number of nodes
					current = current-> link; //advance through the list
			} 

			if(count >= pos) //Check to see if pos is found 
			{
				found = true; //if so its there
			}
			else
			{
				cout<<"Count > than pos";
			//	return 0;
			}

			if(found) //if found then delete the node
			{
				current=first;
				for(count=0; count != pos; count++)
				{
					trail=current;
					current = current-> link;
				}
				if(last == current)      //node to be deleted was 
                                     //the last node
					last = trail;  //Another special case update the value of last
				else
				{
					trail->link = current->link;
				}
					
				delete current;  //delete the node from the list

			}
			else
				cout<<"Item to be deleted is not in the list."<<endl;
		}
	} 
}
////////////////////////////////////////////////////////////////////

//Overloading the stream insertion operator
ostream& operator<<(ostream& osObject, const linkedListType& list)
{
	nodeType *current; //pointer to traverse the list

	current = list.first;   //set current so that it points to 
					   //the first node
	while(current != NULL) //while more data to print
	{
	   osObject<<current->info<<" ";
	   current = current->link;
	}
	return osObject;
}

linkedListType::~linkedListType() // destructor
{
	destroyList(); 
}//end destructor

//overload the assignment operator
const linkedListType& linkedListType::operator=
   	 	 		(const linkedListType& otherList)
{ 
     
	if(this != &otherList) //avoid self-copy
	{
				///copy list
	}//end else

	return *this; 
}

void displayMenu()
{
	cout << "Select one of the following:" << endl;
	cout << "1: To search for a node" << endl;
	cout << "2: To search and delete a node" << endl;
	cout << "3: Add Name" << endl;
	cout << "0: EXIT" << endl;
}

void controller(int i)
{
	string name;
	int pos;
	linkedListType link;

			if (i == 1)
			{
				cout << "Enter the number of the Node to Search For: ";
				cin >> pos;
				link.getKThElement(pos);
			}
			else if (i == 2)
			{
				cout << "Enter the Name of the Node you want to delete: ";
				cin >> pos;
				link.deteteKthElement(pos);
			}
			else if (i == 3)
			{
				cout << "Add Name: ";
				cin >> name;
				link.insertFirst(name);
			}			
			else
			{
				cout << "Invalid Selection" << endl;
			}
}

void GetInput()
{
	int i;
	linkedListType link;
do
	{
		link.Display_List();
		displayMenu();
		cout << "Please select a number from below: " << flush;
		cin >> i;
		controller(i);
	}
	while (i != 0);
}

int _tmain()
{
	GetInput();
	return 0;
}