
public class LinkedList<T> {

	private Node<T> head=null;


	public void print(){
		Node<T> pos = head;
		if(pos==null){
			System.out.println("NO Nodes !!");
		}
		else{
			while(pos != null){
				System.out.println(pos.toString());
				pos=pos.getNext();
			}
		}
	}

	public int length(){
		Node<T> pos = head;
		int count=0;
		while(pos != null){
			++count;
			pos=pos.getNext();
		}
		return count;
	}

	public boolean isEmpty(){
		if(head==null)
			return true;
		else
			return false;
	}

	public void clearList(){
		this.head=null;
	}

	/*public void addInsertion(Integer data){
		Node<T> newNode = new Node<>(data);
		Node<T> pos = head;

		if(head==null){
			newNode.setNext(head);
			head = newNode;
		}
		else{

			if(pos.getData() > newNode.getData()){
				newNode.setNext(head);
				head=newNode;
			}
			else{

				while(pos.getNext()!=null && pos.getNext().getData() < newNode.getData())
					pos=pos.getNext();

				newNode.setNext(pos.getNext());
				pos.setNext(newNode);

			}

		}
	}
*/
	public boolean add(T value){
		Node<T> newNode = new Node<>(value);
		Node<T> pos = head;
		if(head==null){
			newNode.setNext(head);
			head = newNode;
			return true;
		}

		else{
			while(pos.getNext()!=null){
				pos=pos.getNext();
			}
			newNode.setNext(pos.getNext());
			pos.setNext(newNode);
			return true;
		}


	}



	public boolean remove(int index){
		if(index > this.length() || index <0 || this.isEmpty()){
			return false;
		}

		Node<T> pos =head;

		if(index==0){
			head = head.getNext();
			return true;
		}
		else{
			for(int count=0;count<index-1;++count){
				pos=pos.getNext();
			}
			pos.setNext(pos.getNext().getNext());
			return true;
		}
	}

	public LinkedList<T> merge(LinkedList<T> list2){
		LinkedList<T> finalList = new LinkedList<>();

		Node<T>pos1 = head;
		Node<T> pos2 = list2.getHead();

		while(pos1 !=null && pos2 != null){
			if(pos1.getData() > pos2.getData()){
				finalList.add(pos1.getData());
				pos1 = pos1.getNext();
			}

			else if(pos1.getData() < pos2.getData()){
				finalList.add(pos2.getData());
				pos2 = pos2.getNext();
			}

			else {
				finalList.add(pos1.getData());
				pos1 = pos1.getNext();
				pos2 = pos2.getNext();
			}
		}

		if(pos1 != null){
			while(pos1!=null){
				finalList.add(pos1.getData());
				pos1 = pos1.getNext();
			}
			return finalList;
		}
		else if(pos2 != null){
			while(pos2 !=null){
				finalList.add(pos2.getData());
				pos2 = pos2.getNext();
			}
			return finalList;
		}
		else{
			return finalList;
		}


	}

	public  void sort(Integer []a){

		LinkedList<Integer> [] list = new LinkedList[10];

		for (int i = 0; i < list.length; i++) {
			list[i] = new LinkedList<Integer>();
		}

		int maxDigit = noOfMaxDigit(a);
		int index=0,tempValue,m=1;
		

		for(int counter=1;counter<=maxDigit;++counter){

			for(int i=0;i<list.length;++i){
				list[i].clearList();
			}

			for(int i=0;i<a.length;++i){

				tempValue =a[i] % (int)Math.pow(10, counter);
				index=tempValue/ (int)(m*Math.pow(10, counter-1));
				list[index].add(a[i]);
			}
			
			
			int Length=0;

			for(int i=0;i<list.length;++i){
				for(int j=0;j<list[i].length();++j){
					a[Length++]=list[i].getData(j);
				}
			}
			
		}

		//return a;

	}
	/*public  void radixSort(LinkedList<Integer> list) {
		LinkedList<Integer>[] array = new LinkedList[10];
		int listSize = list.length();

		for (int i = 0; i < array.length; i++)
			array[i] = new LinkedList<>();
		LinkedList<Integer> list2 = new LinkedList<>();
		//list2 = list.copyList();
		int power = 1;
		for (int j = 0; j < 2; j++) {
			for (int i = 0; i < listSize; i++) {
				list2 = list.copyList();				
				array[(list2.getDataIndex(i).getData() / power) % 10].addLast(list2.getDataIndex(i).getData());
			}
		list2 = new LinkedList<>();
//			list2=list.copyList();
//			for (int i = 0; i < array.length; i++)
//				array[i] = new GenericList<>();
			for (int l = 0; l < 10; l++)
				if (array[l].getNumOfElements() > 0)
					array[l].printList();

			power = power * 10;
		}

	}
*/
	private  int noOfMaxDigit(Integer []a){
		int maxDigit = 0;
		int digits;

		for(int i=0;i<a.length;++i){
			digits=noOfDigits(a[i]);

			if(digits>maxDigit)
				maxDigit = digits;
		}
		return maxDigit;
	}

	private  int noOfDigits(int x){
		if(x<10)
			return 1;
		else
			return 1+noOfDigits(x/10);
	}

	
	public Integer getData(int index){
		Node<T> pos = head;

		for(int i =0;i<index;++i){
			pos=pos.getNext();
		}
		return pos.getData();

	}


	public Node<T> getHead() {
		return head;
	}
















}
