개요
여러 데이터를 구조화하여 다루는 것을 자료 구조라고 한다.
자바 컬렉션 프레임워크는 다양한 자료 구조를 제공하는 클래스와 인터페이스의 집합이다.
주요 인터페이스로는 List, Set, Map, Stack, Queue 등이 있다.
List
순서를 보장하고, 중복을 허용한다.
-
ArrayList
- 동적 배열로 구성되어 있다.
- 기본 CAPACITY는 10이고 CAPACITY를 넘어가면 배열을 50% 증가한다.
- 인덱스로 빠른 접근이 가능하다.
- 데이터 추가 시 모든 요소를 한 칸씩 뒤로 이동시켜야 하기 때문에 삽입의 성능이 느리지만 자바의 메모리 고속 복사 연산을 통해 최적화 되어 있다.
-
LinkedList
- 이중 연결 리스트로 구현되어 있어 다음 노드 뿐만 아니라 이전 노드로도 이동할 수 있다.
- 삽입과 삭제가 빠르다.
- 이전 노드로 이동이 가능하기 때문에 역방향 조회로 인해 인덱스 조회 성능이 최적화 되어 있다.
이론적으로 LinkedList의 중간 삽입 연산은 ArrayList보다 빠를 수 있다. 그러나 실제 성능은 요소의 순차적 접근 속도, 메모리 할당 및 해제 비용, CPU 캐시 활용도 등 다양한 요소에 의해 영향을 받는다.
Set
순서를 보장하지 않고, 중복을 허용하지 않는다.
-
HashSet
- 해시 테이블로 구현되어 있다.
- 순서를 보장하지 않고, 빠른 검색, 삽입, 삭제가 가능하다.
- 데이터의 유일성만 중요하고, 순서가 중요하지 않은 경우에 적합하다.
-
LinkedSet
- HashSet에 연결 리스트를 추가해서 요소들의 순서를 유지한다.
- 빠른 검색, 삽입, 삭제가 가능하다.
- 데이터의 유일성과 함께 삽입 순서를 유지해야 할 때 적합하다.
- 연결 링크를 유지해야 되기 때문에 HashSet보다는 조금 더 무겁다.
-
TreeSet
- 이진 검색 트리를 개선한 레드-블랙 트리를 내부에서 사용한다.
- 요소들은 정렬된 순서로 저장된다. 순서의 기준은 비교자(Comparator)로 변경할 수 있다.
- 범위 검색 같이 데이터들을 정렬된 순서로 유지하면서 집합의 특성을 유지해야 할 때 사용한다.
Map
키-값으로 이루어져 있고 순서를 보장하지 않는다.
키는 맵 내에서 유일해야 한다. 그리고 키를 통해 값을 빠르게 검색할 수 있다.
키는 중복될 수 없지만, 값은 중복될 수 있다.
-
HashMap
- 해시를 사용해서 요소를 저장한다. 키(Key)값은 해시 함수를 통해 해시 코드로 변환되고, 이 해시 코드는 데이터를 저장하고 검색하는 데 사용된다.
- 삽입, 삭제, 검색 작업은 해시 자료 구조를 사용하므로 성능이 빠르다.
- 순서를 보장하지 않는다.
-
LinkedHashMap
- 연결 리스트를 사용하여 삽입 순서 또는 최근 접근 순서에 따라 요소를 유지한다.
- 입력 순서에 따라 순회가 가능하다.
- HashMap과 유사한 성능을 가지만, 입력 순서를 링크로 유지해야 되기 때문에 조금 더 무겁다.
- 입력 순서를 보장한다.
-
TreeMap
- 레드-블랙 트리를 기반으로 구현되어 있다.
- 모든 키는 자연 순서 또는 생성자에 제공된 Comparator에 의해 정렬된다.
- 키는 정렬된 순서로 저장된다.
Stack
후입 선출(LIFO, Last In First Out) 구조를 가진 자료 구조이다.
Stack 에 값을 넣는 것을 push 라고 하고, 값을 꺼내는 것을 pop 이라고 한다.
자바의 Stack 클래스는 내부에서 성능이 느려 지금은 사용하지 않는 Vector 라는 자료 구조를 사용한다. 따라서 Stack 도 사용하지 않는 걸 권장한다.
Queue
선입 선출(FIFO, First In First Out) 구조를 가진 자료 구조이다.
Queue 에 값을 넣는 것을 offer 라고 하고, poll 이라고 한다.
Deque
Double Ended Queue 의 약자로, 양쪽 끝에서 요소를 추가하거나 제거할 수 있다.
일반적인 Queue 와 Stack 의 기능을 모두 포함하고 있어, 매우 유연한 자료 구조이다.
대표적인 구현체는 ArrayDeque, LinkedList 가 있다. 이 둘 중에 ArrayDeque 가 모든 면에서 더 빠르다.
