#include <iostream>
#include <string>
using namespace std;

struct node
{	string item;
	node *nextPtr;

	node(string str)   // constructor
	{	item = str;
		nextPtr = NULL;
	}
};   // note semicolon

class linkList
{
private:
	node *headPtr;

public:
	linkList()		// constructor
	{	headPtr = NULL;   }


	void addToFront(string str)
	{
		node *tempPtr = new node(str);   // get space
		tempPtr->nextPtr = headPtr;
		headPtr = tempPtr;
	}  //end addToFront function	

	void displayList()
	{
		node *currPtr = headPtr;
		while(currPtr != NULL)
		{
			cout << currPtr->item << endl;
			currPtr = currPtr->nextPtr;
		}  // end while
	}  // end displayList function		

	void addToEnd(string str)
	{
		node *tempPtr = new node(str);
		node *currPtr = headPtr;
			
		if(headPtr == NULL) 
		{	headPtr = tempPtr;}
		else 
		{
			while(currPtr->nextPtr != NULL)
				currPtr= currPtr->nextPtr;
			currPtr->nextPtr = tempPtr;
		}
	}// end addToEnd function
	
	void deleteNode(string str)
	{
       if (headPtr == NULL)
	     cout << "No nodes to delete";
 	   else		
       {   node *currPtr = headPtr;
           node *prevPtr = currPtr;
           // transverse until we find the item, or we are at the end of the list
           while ((currPtr->item != str) || (currPtr->nextPtr != NULL))
           {    prevPtr = currPtr;
                currPtr = currPtr->nextPtr;
           }
           if (currPtr == NULL)   // we got to the end of the list without finding item
               cout << "Item was not in the list";
           else if(currPtr=headPtr)  // the item was first in the list
           {      headPtr = headPtr->nextPtr;
                  cout<< "Item " << currPtr->item << " deleted." << endl;      
                  delete currPtr;  }
           else   // found the item anywhere but first
           {   prevPtr->nextPtr = currPtr->nextPtr;
                cout<< "Item " << currPtr->item << " deleted." << endl;          
               delete currPtr; 

           }
        } // end else               
	}  // end deleteNode function
};//  note semicolon at the end class linkList

int main()
{   string str;
	linkList ourList;
	ourList.addToEnd("How ");
	ourList.addToEnd("now ");
	ourList.addToEnd("brown ");
	ourList.addToEnd("cow ");
	ourList.displayList();	
	ourList.deleteNode("now ");
	ourList.displayList();
	cin >> str;
	return 0;
}