#include <iostream>
using namespace std;

//singly linked list node
template<class T>
class Node{
public:
   T data;
   Node(T x):data(x){}
   Node *next;
};

// doubly linked list node
template<class T>
class NodeD{
public:
   T data;
   NodeD(T x):data(x){}
   NodeD *next;
   NodeD *prev;
};


void main(){
	// compiler controlled variables
    Node<int> n(1), p(2), q(3);
	n.next = &p;
	p.next = &q;
	q.next = 0;
	Node<int> *curr = &n;
	while(curr){
		cout << curr->data << endl;
		curr = curr->next;
	}
	
	// use the heap singly linked
	Node<int> *head;
	Node<int> *prev = 0;
	int i;
	for( i=0; i<10; i++){
		curr = new Node<int>(i+1);
		if(i==0){
			head = curr;
			prev = curr;
		}
		else{
		    prev->next = curr;
			prev = curr;
		}
	}
	curr->next = 0;
	curr = head;
	while(curr){
		cout << curr->data << endl;
		curr = curr->next;
	}

	// use the heap doubly linked
	NodeD<int> *headD;
	NodeD<int> *currD;
	NodeD<int> *prevD;
	for(i=10; i<20; i++){
		currD = new NodeD<int>(i+1);
        currD->next = 0;
		if(i==10){
			headD = currD;
			currD->prev = 0;
		}
		else{
			currD->prev = prevD;
			currD->prev->next = currD;
		}
		prevD = currD;
	}
	currD = headD;
	while(currD){
		cout << currD->data << endl;
		currD = currD->next;
	}
	curr = head;
	currD = headD;

	for(i = 0; i < 10; i++){
		Node<int> *tmp;
		NodeD<int> *tmpD;
		tmp = curr;
		curr = curr->next;
		delete tmp;
		tmpD = currD;
		currD = currD->next;
		delete tmpD;
	}

}