#include <stdio.h>

template<class TYPE>
class linkedlist
{
	struct node
	{
		TYPE	data;
		node	*next;
	};

	node *first;
	int num;

	node *nav;

public:
	linkedlist()
	{
		num=0;
		first=new node;
		first->next=NULL;
		nav=new node;
	}
	~linkedlist()
	{
		removeall();
		delete first;
		delete nav;
	}

	void start()
	{
		nav=first->next;
	}
	bool notnull()
	{
		return nav!=NULL;
	}
	void next()
	{
		nav=nav->next;
	}
	TYPE *getnode()
	{
		return &nav->data;
	}

	void addnode(TYPE i)
	{
		node *n;
		n=new node;
		n->data=i;
		if (first->next==NULL)
			n->next=NULL;
		else
			n->next=first->next;
		first->next=n;
		num++;
	}

	int getnum() { return num; }

	void removefromfirst()
	{
		if (first->next!=NULL)
		{
			node *p;
			p=first->next;
			first->next=p->next;
			num--;
			delete p;
		}
	}
	void removefromlast()
	{
		if (first->next!=NULL)
		{
			node *p;
			p=first;

			while (p->next->next!=NULL)
			{
				p=p->next;
			}

			delete p->next->next;

			num--;

			p->next=NULL;
		}
	}
	void removeall()
	{
		for (int i=0;i<num;i++)
		{
			if (first->next!=NULL)
			{
				node *p;
				p=first->next;
				first->next=p->next;
				delete p;
			}
		}
		num=0;
	}
};

#define MAX 10

void main()
{
	linkedlist<int> radix[10];

	int i;
	int number[MAX]={54,34,22,11,56,77,86,23,45,19};

	for (i=0;i<MAX;i++)
	{
		int which=number[i]%10;
		radix[which].addnode( number[i] );
		printf("add %d to [%d]\n",number[i],which);
	}
	for (i=0;i<MAX;i++)
	{
		int count=0;
		for (radix[i].start();radix[i].notnull();radix[i].next())
		{
			number[count]=*radix[i].getnode();
			printf("%d ",number[count]);
			count++;
		}
		radix[i].removeall();
	}
}