


public class LinkedList<T> {

	private Node<T> head=null;
	private int size;

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

	public boolean isEmpty(){
		return head==null;
	}

	public LinkedList<T> reverse(LinkedList<T> list){
		return reverse(list, 0);
	}
	

	private LinkedList<T> reverse(LinkedList<T> list,int times){
		if(list==null || list.getSize()==1 || times==list.getSize()){
			return list;
		}
		Node<T> pos=list.getNode(list.getSize()-1);
		list.add(pos.getData(), times);
		list.delete(list.getSize()-1);
		
		return reverse(list,++times);
		
		
	}
	
	
//	public Node<T> reverseList(Node<T> head) {
//	    if(head==null || head.getNext() == null)
//	        return head;
//	 
//	    //get second node    
//	    Node<T> second = head.getNext();
//	    //set first's next to be null
//	    head = null;
//	 
//	    Node<T> rest = reverseList(second);
//	    second.setNext(head);
//	 
//	    return rest;
//	}
//	public Node<T> reverseList(Node<T> head) {
//		if(head==null || head.next == null)
//		return head;
//		
//		Node<T> second = head.getNext();
//		Node<T> rest = reverseList(second);
//		head.next.next = head;
//		head.next = null;
//
//		return rest;
//		}
	public Node<T> getNode(int index){
		Node<T> pos=head;
		for (int i = 0; i < index; i++) {
			pos=pos.getNext();
		}
		return pos;
	}
	
	public boolean add(T data){
		Node<T> newNode = new Node<>(data);
		Node<T> pos=head;
		if(head==null){
			head=newNode;
			++size;
			return true;
		}
		while(pos.getNext()!=null){
			pos=pos.getNext();
		}

		pos.setNext(newNode);
		++size;
		return true;

	}


	public boolean add(T data,int index){
		Node<T> newNode = new Node<>(data);
		Node<T> pos=head;
		if(index <0 || index > size)
			return false;

		if(index==0){
			++size;
			newNode.setNext(head);
			head=newNode; 
			return true;

		}
		for(int i=0;i<index-1;++i){
			pos=pos.getNext();
		}
		newNode.setNext(pos.getNext());
		pos.setNext(newNode);
		++size;
		return true;

	}

	public boolean delete(int index){
		if(index <0 || index > size)
			return false;
		Node<T> pos=head;
		if(index==0){
			--size;
			head=head.getNext();
			return true;
		}
		for(int i=0;i<index-1;++i){
			pos=pos.getNext();
		}
		--size;
		pos.setNext(pos.getNext().getNext());
		return true;

	}

	public boolean deleteData(T data){

		int index = getIndex(data);
		if(index==-1)
			return false;
		Node<T> pos=head;
		if(index==0){
			--size;
			head=head.getNext();
			return true;
		}
		for(int i=0;i<index-1;++i){
			pos=pos.getNext();
		}
		--size;
		pos.setNext(pos.getNext().getNext());
		return true;


	}

	public int getIndex(T data){
		Node<T> pos=head;
		int index=0;

		while(pos!=null){

			if(pos.equal(data)){
				return index;
			}

			pos=pos.getNext();
			++index;

		}
		return -1;
	}


	public T getIndexData(int index){
		if(index<0 || index>=size)
			return null;
		Node<T> pos= head;
		if(index==0){
			return pos.getData();
		}
		for(int i=0;i<index;++i){
			pos=pos.getNext();
		}
		return pos.getData();
	}



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

	public int getSize() {
		return size;
	}





}
