public class SingleLinkedList<E> {
	private class Node<T> {
		private T data;
		private Node<T> next;
		public Node(T data) {
			this.data = data;
			this.next = null;
		}
		
		public String toString() {
			return String.valueOf(data);
		}
	}
	
	Node<E> head = null;
	int size = 0;
	Node<E> tail = null;
	
	private void addFirst(E input){
	    Node<E> newNode = new Node<>(input);
	    newNode.next = head; //삭제하면 안됨
	    head = newNode;
	    size++;
	    if(head.next == null){
	        tail = head;
	    }
	}

	private void addLast(E input){
	    Node<E> newNode = new Node<>(input);
	    if(size == 0){
	        addFirst(input);
	    } else {
	        tail.next = newNode;
	        tail = newNode;
	        size++;
	    }
	}
	
	public void add(E input){
	    addLast(input);
	}
	
	public String toString() {
	    if(head == null){
	        return "[]";
	    }       
	    Node<E> temp = head;
	    String str = "[";
	    while(temp.next != null){
	        str += temp.data + ",";
	        temp = temp.next;
	    }
	    str += temp.data;
	    return str+"]";
	}

	public void add(int index, E input){
	    if(index == 0){
	        addFirst(input);
	    } else if(index == size) {
	    	addLast(input);
	    } else if(index > size || index < 0) {
	    	throw new IndexOutOfBoundsException(String.valueOf(index));
	    } else {
	        Node<E> prev = head;
//	        추가하려는 노드의 전전 노드를 알면 전전노드.next를 전노드에 할당
	        for (int i=0; i<index-1; i++) { 
	            prev = prev.next;
	        }
	        Node<E> newNode = new Node<>(input);
	        newNode.next = prev.next;
	        prev.next = newNode;
	        size++;
	        if(newNode.next == null){
	            tail = newNode;
	        }
	    }
	}// main에서 list.add(2, "F");로 테스트 해 보세요.
	
	public E removeFirst(){
	    Node<E> temp = head;
	    head = temp.next;
	    E data = temp.data;
	    temp = null;
	    size--;
	    return data;
	}
	
	public E remove(int index){
	    if(index == 0) {
	        return removeFirst();
	    }else if(index >= size || index < 0) {
	    	throw new IndexOutOfBoundsException(String.valueOf(index));
	    }
	    Node<E> prev = head;
        for (int i=0; i<index-1; i++) {
            prev = prev.next;
        }

        Node<E> todoDeleted = prev.next;
        prev.next = prev.next.next;

	    E returnData = todoDeleted.data; 
	    if(todoDeleted == tail){
	        tail = prev;
	    }

	    todoDeleted = null; 
	    size--;
	    return returnData;
	}
	
	public E get(int index){
		if(index < 0 || index >= size) {
			throw new IndexOutOfBoundsException(String.valueOf(index));
		}
	    Node<E> temp = head;
        for (int i=0; i<index; i++) {
            temp = temp.next;
        }
	    return temp.data;
	}
	
	public int size() {
		return size;
	}
	
	public int indexOf(E data){
	    Node<E> temp = head;
	    int index = 0;
 
	    while( (temp.data != data) && (!temp.data.equals(data)) ){
	        temp = temp.next;
	        index++;
	        if(temp == null) {
	            return -1;
	        }
	    }
	    return index;
	}
	
	public Object[] toArray() {
		Object[] listArray = new Object[size];
		for(int i=0; i<size; i++) {
			listArray[i] = get(i);
		}
		return listArray;
	}
	
	public E[] toArray(E[] e) {
		E[] listArray = e;
		for(int i=0; i<size; i++) {
			listArray[i] = get(i);
		}
		return listArray;
	}

	public static void main(String[] args) {
		SingleLinkedList<String> list = new SingleLinkedList<String>();
		list.add("A");
		System.out.println(list);
		list.add("B"); list.add("D");
		System.out.println(list);
		list.add(2, "F");
		System.out.println(list);
		System.out.println(list);
		list.removeFirst();
		System.out.println(list);
		list.remove(1);
		System.out.println(list);
		list.add("C"); list.add("R");
		System.out.println(list);
		System.out.println(list.get(0));
		System.out.println(list.get(1));
		System.out.println(list.get(2));
		System.out.println(list.get(3));
		System.out.println(list.indexOf("A"));
		System.out.println(list.indexOf("C"));
		System.out.println(list.indexOf(new String("C")));
		
		String[] strArray = list.toArray(new String[list.size]);
		for(String data : strArray) {
			System.out.print(data + ", ");
		}
		System.out.println();
	}
	
}