Collection - LinkedList

LinkedList<E>

LinkedList는 Node에 의해 데이터들이 연결되어 있는 리스트이다. 연결 리스트라고도 불린다.

 
LinkedList는 데이터를 배열에 저장하는 구조가 아니고 Node라는 객체에 데이터를 저장한다. 그리고 Node는 Node끼리 참조 값을 가지고 있는 이중 연결 리스트로 구성되어 있다.
Node next변수에는 다음 Node의 인스턴스 참조 값을 저장하고 있다. 
다음 Node에 접근하려면 Node next 변수에 저장된 참조 값을 이용해서 접근한다. 따라서 Node1에서 Node3으로 바로 접근할 수 없다. Node2를 통해서만 Node3으로 접근이 가능하다.
data2를 삭제하면 Node1에서는 Node3의 참조값을 저장하고 Node3에서는 Node1의 참조값을 저장한다.
LinkedList에서는 Node에서 참조값을 삭제하는 방식으로 데이터를 삭제한다. 그러므로 ArrayList보다 삭제시 지연시간이 짧다. 그리고 LinkedList에 저장된 데이터가 많다 하더라도 데이터 삭제 시간은 동일하다.
 
장점
- 데이터의 삽입이나 삭제 연산이 빠르다.
 
단점
- 특정 데이터를 찾으려면 최초 생성 Node부터 차례로 Node를 검색해야 하기 때문에 데이터 접근 속도가 ArrayList같은 index 방식보다 느리다.
 
사용 용도
- 데이터에 접근하는 빈도보다 삽입, 삭제가 많을 경우에 사용한다.
- 맨 앞의 데이터 삭제 또는 맨 뒤의 데이터 삭제가 빈번할 때 사용한다.
 
 
LinkedList의 생성

 
 
LinkedList의 데이터 삽입

 
 
LinkedList에 저장된 논리적 공간의 크기

 
 
LinkedList의 특정 index에 데이터를 삽입하기

 
논리적인 공간(size)은 3이기 때문에 인덱스 값이 논리적인 공간을 넘어 접근할 수 없다. 
논리적인 공간을 넘어 접근할 경우 IndexOutOfBoundsException이 발생한다.
 
 
LinkedList의 특정 index 사이에 데이터를 삽입하기
 

 
add(index, value) 메서드는 Node와 Node 사이에 삽입하는 방식이다.
add(index, value) 메서드에서 주의할 점은 논리적인 공간(size)은 3이기 때문에 인덱스 값이 논리적 공간을 넘어 접근할 수 없다. 논리적인 공간을 넘어 접근할 경우 IndexOutOfBoundsException이 발생한다.
 
 
LinkedList의 특정 값에 접근

 
인덱스는 0부터 시작한다.
 
 
LinkedList의 값 삭제
 

remove(index) 메서드는 맨 앞 또는 맨 뒤의 Node 중 접근하기 가장 가까운 Node에서 시작하여 찾아 삭제한다.
remove(value) 메서드는 index 0번부터 순차적으로 찾아 삭제한다.
removeFirst() 메서드는 맨 앞의 노드를 삭제하므로 굉장히 빠르다.
removeLast() 메서드는 맨 뒤의 노드를 삭제하므로 굉장히 빠르다.
 
 
List 인터페이스를 구현하는 LinkedList

다형성의 특징으로 LinkedList의 참조값을 List 자료형에 저장할 수 있다. 
다만 List의 공통적인 인터페이스만 선언되어 있기 때문에 LinkedList의 모든 메서드를 사용할 수는 없다.