// CS2310 Exercise 22
// Chapter 18
//
// Name ________________________ SSN ____________________
//
// Chapter 18 p1051 - 10
// Write a recursive value-returning function that
// searches a dynamic linked list for the integer 
// value key. If the value is in the list, the
// function should return a pointer to the node
// where it was found. If the value is not in the
// list, the function should return NULL.
//
//  SPECIFICATION FILE  DYNAMIC-LINKED SORTED LIST( slist2.h )


typedef    int   ItemType ;  	// Type of each component
				    			// is simple type or string type		
struct  NodeType
{
	ItemType    item ;		// Pointer to person’s name
	NodeType*   link ;		//  link to next node in list
};


typedef  NodeType*  NodePtr;

class  SortedList2
{						
public : 		

	bool IsEmpty ( ) const ; 

	void Print ( ) const ; 

	void InsertTop ( /* in */  ItemType  item ) ;

	void DeleteTop ( /* out */ ItemType& item);

	void Delete ( /* in */  ItemType  item ); 

	bool IsPresent(/* in */ int key);

	SortedList2 ( ) ;				// Constructor
	~SortedList2 ( ) ;				// Destructor
	 
private :
	
	NodeType*  head;
	NodePtr PointerToKey( /* in */ NodePtr headp,
	                      /* in */ int     key  );
} ;