#include <iostream>
using namespace std;

template <class T>
class Node
{
public:
  T value;     // e.g. int
  Node* next;  // pointer to the next element in the list
  Node* prev;
};


// templated function for class T
//
//  push_back() is O(n) for a linked list
//   (we could make this O(1) if we kept track
//     of the tail of the list, too....)
template <class T>
void push_back( Node<T>* head, const T& value )
{
  // find the last node of the list
  Node<T>* p = head;
  while ( p->next != 0 ) {
    p = p->next;   // kinda like p++
  }

  // add the element
  Node<T>* q = new Node<T>;
  q->value = value;
  q->next = 0;

  p->next = q;
}

// erase element pointed to by p
//  (return the value of the erased node)
template <class T>
T erase( Node<T>* & head, Node<T>* p )
{
  // find the node before p
  Node<T>* q = head;
  while ( q->next != p ) {
    q = q->next;  // q++
  }

  // erasing element p
  q->next = p->next;

  T temp = p->value;
  delete p;
  return temp;
}

// insert element pointed to by p
//   (insert after node q)
template <class T>
void insert( Node<T>* head, Node<T>* p, Node<T>* q )
{
  p->next = q->next;
  q->next = p;
}

// Insert element pointed to by p
//    as new head of the list
//  (therefore, the head pointer is passed by reference)
template <class T>
void push_front( Node<T>* & head, Node<T>* p )
{
  p->next = head;
  head = p;
}


int main()
{
  Node<int>* ll;       // ll is a pointer to a Node (initially non-existent)
  ll = new Node<int>;  // Create a Node
  ll->value = 1;       // (*ll).value = 1;
  ll->next = 0;        // a null pointer (end of list)

  // This is push_back():
  Node<int>* q = new Node<int>;
  q->value = 2;
  q->next = 0;
  ll->next = q;   // Link them together

  cout << "First value: " << ll->value << '\n';
  cout << "Second value: " << q->value << '\n';
  cout << "Second value: " << ll->next->value << '\n';

  // assume ll is the head of the list
  push_back( ll, 3 );
  cout << "Third value: " << ll->next->next->value << '\n';

//  q->next = ll;  // create a circular linked list

  return 0;
}