LinkedList

배열 리스트의 단점
배열리스트는 내부에 배열을 사용해서 데이터를 저장한다.

• 배열의 사용하지 않는 공간 낭비
  배열은 필요한 배열 크기를 미리 확보해야한다. 만약 부족하면 그때가서 size를 2배로 늘린다. 데이터가 얼마나 추가될지 모르는 경우 나머지는 사용되지 않는다.
• 배열의 중간에 데이터 추가
  중간에 데이터 추가를 하면 그 뒤부터 하나씩 모두 밀어야한다.
  O(n)

낭비되는 메모리없이 필요한 만큼만쓰고, 중간에 데이터 추가,삭제가 효율적인 자료구조가 노드를 서로 연결하는 방식이다.

노드 클래스

 public class Node {
 	Object item;
	 Node next;
	 public Node(Object item) {
 		this.item = item;
   	 }
 }

다음에 가르킬 노드의 참조값을 next 변수에 저장한다.

 public class NodeMain1 {
으로 선언하는 것이 좋지만, 이 예제에서는 설명을 단순하게 하기 위해 디폴트 
`
 public static void main(String[] args) {
 		//노드 생성하고 연결하기: A -> B -> C
		 Node first = new Node("A");
        first.next = new Node("B");
        first.next.next = new Node("C");
 }