#include <iostream.h>

#define NULL 0
#define TOP 32767

class list
{

  private:
    struct list_struct {
      int contents;
      list_struct *tl;
    } *hd;

  public:
    list (void);				// constructor
    ~list (void);				// destructor
    int  head (void) const;			// head
    list tail (void) const;			// tail
    list cons (int) const;			// cons
    int operator == (const list &) const;	// list equality
    int operator != (const list &) const;	// list inequality
};

list::list (void) { hd = NULL; }

list::~list (void) { }

int list::head (void) const
{
  if (hd != NULL)
    return hd -> contents;
  else {
    cerr << "*****ERROR***** head applied to empty list" << endl;
    return TOP;
  }
}

list list::tail (void) const
{
  list tl;
  if (hd != NULL && hd -> tl != NULL) 
    tl . hd = hd -> tl;
  return tl;
}

list list::cons (int r) const
{
    list newlist;
    newlist . hd = new list_struct;
    newlist . hd -> contents = r;
    newlist . hd -> tl = hd;
    return newlist;
}

int list::operator == (const list & list2) const
{
  struct list_struct *p1, *p2;
  if (hd == NULL)
    if (list2 . hd == NULL)
      return 1;
    else
      return 0;
  else {
    if (list2 . hd == NULL)
      return 0;
    else {
      if (hd -> contents != list2 . hd -> contents)
	return 0;
      else {
	for (p1 = hd -> tl, p2 = list2 . hd -> tl;
	     p1 != NULL && p2 != NULL;
	     p1 = p1 -> tl, p2 = p2 -> tl)
	  if (p1 -> contents != p2 -> contents) return 0;
	if (p1 == NULL)
	  if (p2 == NULL)
	    return 1;
	  else
	    return 0;
	else
	  return 0;
      }
    }
  }
}

int list::operator != (const list & list2) const
{
  return ! (*this == list2);
}

list nil;