#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
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;
}

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;
}