// Linked lists in C++

using namespace std;
#include<iostream>

class node
{
public:
  int head;   // also called item, data
  node *tail; // also called next

  node(int h, node* t)  // constructor
  { head=h;  tail=t; }

 
  bool member(int x) // determine if x is in list
  {
    node * i = this;
    bool answer = false;
    while (i!=NULL && !answer) 
      {
	if (i->head == x) answer = true;
	i = i->tail;
      }
    return answer;
  }

  /* alternative, recursive definition of member: */
 bool memb(int x) { return x==head || (tail!=NULL && tail->memb(x)); }
 
 int length()
  {  if (tail==NULL) return 1; else return 1+tail->length(); }


  void add(int x) // add new integer to end of list
  {
    node * i = this;
    while (i->tail != NULL)  i = i->tail;
    i->tail = new node(x,NULL);
  }

  int get(int n)  // get nth element starting from this node
  {
    node * i = this;
    for(;n>0 && i!=NULL; i=i->tail, n--);
    if (i == NULL) throw "index out of bounds";
    else return i->head;
  }

  ~node()   // destructor
  {
    if (tail != NULL) delete(tail); 
  }
};


int main(int argc, char** argv)
{
  node * N = new node(2, new node(4, new node(6, NULL)));
  N->add(8);
  cout << "the third element is " << N->get(2) << endl;
  cout << N->memb(5) << endl;
  delete(N);
  return 0;
}