class LinkedList{
	private Node head;
	private Node tail;
	private int size = 0;

	private class Node{
		private Object data;	//node 값

		private Node next;		//참조 값(다음 node의 주소)

		public Node(Object input){
			this.data = input;
			this.next = null;
		}
		public String toString(){	//참조값을 data 값으로 변환

			return String.valueOf(this.data);
		}
	}

	public void addFirst(Object input){	// head부터 데이터 추가

		Node newNode = new Node(input);
		newNode.next = head;
		head = newNode;
		size++;
		if(head.next ==null){
			tail = head;
		}
	}

	public void addLast(Object input){	// tail부터 데이터 추가

		Node newNode = new Node(input);

		if(size==0){	//리스트에 노드가 없을 경우

			addFirst(input);
		}
		else{
			tail.next = newNode;
			tail = newNode;
			size++;
		}
	}

	Node findNode(int index){	//특정 위치의 노드를 찾음

		Node x = head;
		for(int i=0 ; i<index ; i++){
			x = x.next;
		}
		return x;
	}

	public void add(int k, Object input){	//중간에 데이터 추가

		if(k == 0){
			addFirst(input);
		} else{
			Node temp1 = findNode(k-1);
			Node temp2 = temp1.next;
			Node newNode = new Node(input);
			temp1.next = newNode;
			newNode.next = temp2;
			size++;
			if(newNode == null){
				tail = newNode;
			}
		}
	}

	public String toString(){	//연결 리스트 출력

		if(head == null){
			return "[]";
		}
		else{
			Node temp = head;
			String str = "[";

			while(temp.next != null){
				str += temp.data + ", ";
				temp = temp.next;
			}
			str += temp.data;
			return str+"]";
		}
	}

	public Object removeFirst(){	//head부터 삭제

		Node temp = head;
		head = head.next;
		Object returnData = temp.data;
		temp = null;
		size--;
		return returnData;
	}

	public Object remove(int k){	//중간 데이터 삭제

		if(k == 0){
			return removeFirst();
		}

		Node temp = findNode(k-1);
		Node deleteNode = temp.next;
		temp.next = temp.next.next;
		Object returnData = deleteNode.data;

		if(deleteNode == tail){	//삭제할 노드가 마지막일 경우

			tail = temp;
		}
		size--;
		return returnData;
	}

	public Object removeLast(){	//tail부터 삭제

		return remove(size-1);	//tail 바로 전을 알아야 한다. 가장 마지막 삭제는 최악의 경우

	}

	public int size(){	//엘리먼트의 크기

		return size;
	}

	public Object get(int k){	//특정 엘리먼트 값 가져오기

		Object returnData = findNode(k) ;
		return returnData;
	}

	public int indexOf(Object data){	//특정값 탐색

		Node temp = head;
		int index = 0;
		while(temp.data != data){
			temp = temp.next;
			index++;
			if(temp == null){
				return -1;
				}
		}
		return index;
	}
}

public class LinkedList_ex2 {

	public static void main(String[] args) {
		LinkedList numbers = new LinkedList();


		System.out.println("단순 연결 리스트");
		numbers.addFirst(40);
		numbers.addFirst(30);
		numbers.addFirst(20);
		numbers.addFirst(10);
		System.out.println(numbers);
		System.out.println("Let's go test");
	}
}