LinkedList
Collections의List 인터페이스와Deque 인터페이스를 상속받는다.UnSynchronized하다.멀티 쓰레드 환경에서 사용하면 원하는 결과와 다른 결과를 얻을 수 있다 (thread-safe 하지 않다)
📌 구조
- 데이터 끼리 연결되어 있지 않고, 떨어져 있다.
- 내부에 다음 데이터의 참조 주소를 가지고 있다. (데이터 조회 시 순차적으로 탐색해 나간다.)
class Node {
Node next; // 다음 노드의 주소
Object object; // 데이터 값
}- 일반 LinkedList는 다음 주소만 가지고 있기 때문에 단방향 접근만 가능하다. 이를 보완하도록 나온 것이
doubly linked list이다. 자바에서 제공하는 LinkedList는doubly linked list이다.
class Node {
Node next; // 다음 노드의 주소
Node previous; // 이전 노드의 주소
Object object; // 데이터 값
}📌 특징
- 장점 : 데이터의 비순차적인 수정 삭제가 빠르다 (인덱스로 접근해서 수정, 삭제)
참조하는 주소만 앞뒤로 바꿔주면 된다.
참고 ) ArrayList는 중간에 데이터 추가, 삭제 시 기존 데이터의 복사가 일어나서 느리다.
- 단점 : 데이터의 탐색이 느리다.
데이터가 연속적으로 저장되어 있지도 않고, 저장 위치가 각 노드에 있으므로, 인덱스 탐색이라고 할지라도 순차적으로 일어나게 된다.
참고 ) ArrayList는 인덱스 * 데이터크기 = 저장위치 로 탐색이 빠르다.
📌 ArrayList와 LinkedList 중 어떤걸 써야하나
데이터의 추가 삭제가 순차적으로 이루어지고(add, remove만 사용), 탐색이 잦은 경우 : ArrayList
데이터를 인덱스로 접근해서 수정하는 경우가 많은 경우 : LinkedList
📌 참고
- 자바의 정석
- Java api docs
