이 글은 평상시에 크게 구분하지 않고 사용하던 컬렉션 자료구조를 명확하게 정리하고, 성능 향상을 위해 조사한 글이다.

Java Collections Framework

컬렉션 프레임워크는 다수의 요소를 하나의 그룹(Collection)으로 묶어 효율적으로 저장하고, 관리할 수 있는 기능을 제공하는 프레임워크(Framework)다.
크기가 고정되어있는 배열과 다르게 가변적인 크기를 갖는 특징이 있고, 데이터 삽입, 탐색, 정렬, 삭제 등 데이터를 처리하는 알고리즘을 구조화하여 클래스로 구현해 놓은 것이 컬렉션 프레임워크다.

그래서 이게 뭐가 좋은건데?

컬렉션 프레임워크를 쓰지않고 C언어처럼 직접 자료 구조 클래스를 만들어 사용할 수 있겠지만,
알고리즘의 속도와 안정성에 있어서 수많은 개발자들이 최적화를 시켜놓았기 때문에 우리는 잘 만들어진 도구를 사용해서 더 효율적으로 작업할 수 있다.

컬렉션 프레임워크의 장점

• 데이터 구조 및 알고리즘의 고성능 구현을 제공하여 프로그램의 성능과 품질을 향상시킨다.
• 가변적인 저장 공간을 제공한다. 고정적인 저장 공간을 제공하는 배열과 가장 대비되는 특징이다.
• 이미 구현되어있는 API를 사용할 수 있기 때문에, 목적에 맞게 선택하여 사용할 수 있다.

컬렉션 프레임워크의 종류

컬렉션 프레임워크는 3가지 요소로 구성된다.

1. 인터페이스 (Interface) : 각 컬렌션을 나타내는 추상 데이터에 인터페이스 (List, Set, Map 등)
   클래스는 이 인터페이스를 구현하는 방식으로 작성되었기 때문에 상세 동작은 다라도 일관된 조작법으로 사용할 수 있다.

2. 클래스 (cClasses) : 컬렉션 별 인터페이스의 구현 (Implementation).
   같은 List 컬렉션이더라도 목적에 따라 ArrayList, LinkedList 등으로 상세 구현이 달라질 수 있다.

3. 알고리즘 (Algorithms) : 컬렉션이 제공하는 연산, 검색, 정렬, 셔플 등에 대한 메소드

이 중 가장 핵심적인 인터페이스에 대해 자세히 알아보자

List 인터페이스

• 저장 순서가 유지되는 컬렉션을 구현하는데 사용
• 같은 요소의 중복 저장을 허용
• 배열과 마찬가지로 index로 요소에 접근
• 리스트와 배열의 가장 큰 차이는 가변적인 크기를 가진다는 점
• 요소 사이에 빈공간을 허용하지 않기 때문에, 삽입/삭제 시 배열 이동이 일어난다.

ArrayList 클래스

• 배열을 이용하여 만든 리스트
• 데이터의 저장순서가 유지되고 중복을 허용한다.
• 데이터의 양에 따라 공간(Capacity)이 자동으로 변한다.
• 순차적인 접근에 강점이 있어 조회가 빠르다.
• 삽입/삭제는 느리다. 하지만 순차적인 작업의 경우에는 빠르다.

Stack 클래스

• 후입선출 LIFO(Last-In-First-Out) 자료구조
• 마지막에 들어온 원소가 처음으로 나간다.
• 들어올때는 push, 나갈때는 pop을 사용한다.

Queue 인터페이스

• 선입선출 FIFO(First-In-First-Out) 자료구조
• 처음 들어온 원소가 가장 먼저 나간다.
• 자바에서는 필요에따라 Queue 컬렉션을 골라서 사용한다.

Priority Queue 클래스

• 우선 순위를 가지는 큐
• 일반적인 큐와는 조금 다르게, 원소에 우선 순위(priority)를 부여하여 우선 순위가 높은 순으로 정렬되고 꺼낸다.
• 수행할 작업이 여러 개 있고 시간이 제한되어 있을 때 우선순위가 높은 것부터 수행할때 쓰인다.
• 우선 순위 큐에 저장할 객체는 필수적으로 Comparable 인터페이스를 구현해야 한다.
• 저장공간으로 배열을 사용하며, 각 요소를 힙(heap) 형태로 저장한다.
• null 저장이 불가능하다

Set 인터페이스

• 데이터의 중복을 허용하지 않고 순서를 유지하지 않는 데이터의 집합 리스트
• 순서 자체가 없으므로 index를 객체로 검색해서 가져오는 메서드도 존재하지 않는다.
• 중복 저장이 불가능하기 때문에 null값도 하나만 저장할 수 있다.

HashSet 클래스

• 배열과 연결 노드를 결합한 자료구조 형태
• 가장 빠른 임의 검색 접근 속도를 가진다.
• 추가, 삭제, 검색, 접근성이 매우 뛰어나다
• 하지만 순서를 예측할 수 없다.

TreeSet 클래스

• 이진 검색 트리 자료구조의 형태로 데이터를 저장한다.
• 중복을 허용하지 않고, 순서를 가지지 않는다.
• 대신 데이터를 정렬하여 저장한다는 특징이 있다.
• 정렬, 검색, 범위 검색에서 높은 성능을 가진다.

Map 인터페이스

• Key-Value 형태로 저장된 데이터의 집합
• 값(Value)은 중복될 수 있지만, 키(Key)는 중복 될 수 없다.
• 저장 순서가 유지되지 않는다.

HashMap 클래스

• 배열과 연결이 결합된 Hashing형태로, 키(Key)와 값(Value)를 묶어 하나의 데이터로 저장한다.
• 중복을 허용하지 않고 순서를 보장하지 않는다.
• 키와 값으로 null값이 허용된다
• 추가, 삭제, 검색, 접근성이 모두 뛰어나다.
• 비동기로 작동한다.

TreeMap 클래스

• 이진 검색 트리의 형태로 키와 값의 쌍으로 이루어진 데이터를 저장한다.
• TreeMap은 SortedMap 인터페이스를 구현하고 있어 Key값을 기준으로 정렬되는 특징이 있다.
• 정렬된 순서로 키/값 쌍을 저장하므로 빠른 검색이 가능하다.
• 단, 저장시간이 다소 오래 걸린다.
• 정렬되는 순서는 숫자 -> 알파벳 대문자 -> 알파벳 소문자 순이다.

그래서 어떤걸 써야 하는데?

컬렉션 프레임워크는 위에 적은 것보다 종류가 매우 많고, 쓰임새와 특징이 조금씩 다르기 때문에 어떤 상황에 어떤 자료구조를 선택해야 하는지 어렵다.
대략적으로 정리하자면

ArrayList

1. 리스트 자료구조의 기본적인 선택지
2. 임의의 요소에 대한 접근성이 뛰어나다
3. 순차적인 추가/삭제가 가장 빠르다.
4. 요소의 추가/삭제에 불리하다.

LinkedList

1. 요소의 추가/삭제 유리
   임의의 요소에 대한 접근성이 좋지 않음
2. HashMap / HashSet

HashMap / HashSet

1. 해싱을 이용해 임의의 요소에 대한 추가/삭제/검색/접근성 모두 뛰어남
2. 검색에 최고성능 ( get 메서드의 성능이 O(1) )

TreeMap / TreeSet

1. 요소 정렬이 필요할때
2. 검색(특히 범위검색)에 적합
3. 그래도 검색 성능은 HashMap보다 떨어짐

inkedHashMap / LinkedHashSet

1. HashMap과 HashSet에 저장 순서 유지 기능을 추가

Queue

1. 스택(LIFO) / 큐(FIFO) 자료구조가 필요하면 ArrayDeque 사용

Stack, Hashtable

1. 가급적 사용 X (deprecated)