public class LinkedList
{

	/*
	private class Data
	{
		int val;
		
		public Data()
		{
			val = 0;
		}
		
		public static int getVal()
		{
			return val;
		}
		
		public static void setVal(int n)
		{
			val = n;
		}
	}
	*/
		
	public Node head;
	
	public LinkedList(int length)
	{
		head = null;
				
		for (int i = 0; i < length; i ++)
			insert(i);
			
	}

	/*public void insert(Node node)
	{
		Node cur = new Node(node);
		
		cur.next = head.next;
		
		head = cur;
	}*/
	
	public void insert(int n)
	{
		Node cur = new Node(n);
		
		cur.next = head;
		
		head = cur;
	}
	
	//Delete the node at the zero-based index.
	public void delete(int index)
	{
		int cur;
		Node curnode = head;
		
		for (cur = index; cur > 1; cur --) 
			curnode = curnode.next;
			
		if (curnode == head)
			head = head.next;
		else
			curnode.next = curnode.next.next;
	}
	
	public int getVal(int index)
	{
		int cur;
		Node curnode = head;
		
		for (cur = index; cur > 0; cur --) 
			curnode = curnode.next;
			
		//curnode should point to the node whose value we want.
		return curnode.getVal();
	}
	
	public void print()
	{
		System.out.println();
		
		head.print();
	}
	
	private void swap(Node pa, Node a, Node pb, Node b)
	{
		Node temp = b.next;
		pa.next = b;
		if (a.next != b)
		{
			b.next = a.next;
			pb.next = a;
		}
		else
			b.next = a;
			
		a.next = temp;
	}

	public void selectionSort()
	{
		Node cur, a, prev, pos;
		pos = new Node(0);
		pos.next = head;
		head = pos;
		
		while (pos.next  != null)
		{	
			cur = prev = pos.next;
			a = pos.next;
			while(a != null)
			{
				if (a.getVal() < cur.getVal())
				{
					cur = a;
					while(prev.next != cur)
						prev = prev.next;
				}
				a = a.next;
			}
		
			if (cur != prev)
			{
				Node t = pos.next;
				swap(pos, t, prev, cur);
			}
			
			
			//System.out.println("****************");
			//head.print();
			
			pos = pos.next;
		}
		head = head.next; //to lose the initial node.
		
		//System.out.println("end of sorting, head.print is");
		//head.print();
	}
}