1. List

List는 데이터의 순서를 유지하고 중복을 허용한다.

대표적인 구현체는 ArrayList와 LinkedList이다.

2. ArrayList

ArrayList는 내부적으로 배열을 사용한다.

예를 들어 다음과 같이 데이터를 추가하면

List<String> list = new ArrayList<>();

list.add("A");
list.add("B");
list.add("C");

내부에서는 개념적으로 다음과 같이 저장된다.

index

0     1     2     3     4
┌─────┬─────┬─────┬─────┬─────┐
│  A  │  B  │  C  │     │     │
└─────┴─────┴─────┴─────┴─────┘

배열은 인덱스를 이용해 원하는 위치에 바로 접근할 수 있다.

list.get(1);

index 1
   ↓
   B

따라서 인덱스를 이용한 조회는

O(1)

의 시간 복잡도를 가진다.

3. ArrayList의 크기 확장

배열은 크기가 고정되어 있지만 ArrayList에는 계속해서 데이터를 추가할 수 있다.

내부 배열의 공간이 부족해지면 더 큰 배열을 새로 생성하고 기존 데이터를 복사한다.

기존 배열

[A][B][C][D]

        ↓ 공간 부족

더 큰 배열 생성

[A][B][C][D][ ][ ]

OpenJDK 구현에서는 일반적으로 기존 배열 크기의 약 1.5배 정도로 확장한다.

다만 이는 내부 구현 방식이며 Java API가 반드시 1.5배 확장을 보장하는 것은 아니다.

4. ArrayList의 중간 삽입과 삭제

다음 데이터가 있다고 해보자.

[A][B][C][D]

B와 C 사이에 X를 넣으면

[A][B][X][C][D]

가 되어야 한다.

이를 위해 기존의 C, D를 뒤로 이동시켜야 한다.

[A][B][C][D]
       ↓
[A][B][X][C][D]

따라서 중간 삽입이나 삭제는 일반적으로

O(n)

의 시간이 걸린다.

ArrayList의 특징은 다음과 같다.

인덱스 조회
→ 빠름

맨 뒤 삽입
→ 대부분 빠름

중간 삽입과 삭제
→ 데이터 이동 필요

내부 구조
→ 배열

5. LinkedList

LinkedList는 배열이 아니라 Node를 연결하는 방식으로 데이터를 저장한다.

Java의 LinkedList는 양방향 연결 리스트이다.

null ← [A] ↔ [B] ↔ [C] ↔ [D] → null

각 Node는 다음 정보를 가진다.

이전 Node
현재 데이터
다음 Node

6. LinkedList 조회

LinkedList에는 배열처럼 특정 인덱스로 바로 이동하는 기능이 없다.

예를 들어 세 번째 데이터를 찾으려면 Node를 따라 이동해야 한다.

A
↓
B
↓
C

따라서 위치 탐색은 일반적으로

O(n)

이다.

ArrayList와 비교하면 다음과 같다.

ArrayList

index 3
   ↓
바로 접근


LinkedList

Node
 ↓
Node
 ↓
Node
 ↓
목표 Node

7. LinkedList 삽입과 삭제

LinkedList는 삽입할 위치의 Node를 이미 알고 있다면 연결만 변경하면 된다.

기존

A ↔ B ↔ C

삽입

A ↔ B ↔ X ↔ C

배열처럼 뒤의 모든 데이터를 이동할 필요는 없다.

다만 특정 위치를 찾기 위해 탐색해야 한다면 탐색 비용이 발생한다.

따라서

LinkedList는 삽입과 삭제가 항상 O(1)

이라고 이해하면 정확하지 않다.

위치를 이미 알고 있다면 연결 변경 자체는 빠르지만, 원하는 위치를 찾는 과정까지 포함하면 O(n)이 될 수 있다.

8. ArrayList와 LinkedList 비교

실제 일반적인 List 사용에서는 ArrayList가 더 자주 사용된다.

9. Set

Set은 중복 데이터를 허용하지 않는 구조이다.

대표적인 구현체는

HashSet
LinkedHashSet
TreeSet

이다.

10. HashSet

HashSet은 내부적으로 HashMap을 사용한다.

Set<String> set = new HashSet<>();

set.add("A");
set.add("B");
set.add("A");

결과는

A
B

만 남는다.

내부에서는 저장하려는 값을 HashMap의 Key로 사용한다.

HashSet 값
     ↓
HashMap의 Key

즉 HashSet의 내부 구조를 이해하려면 HashMap을 이해하는 것이 중요하다.

11. Map

Map은 데이터를 Key와 Value 형태로 저장한다.

Key → Value

대표적인 구현체는

HashMap
LinkedHashMap
TreeMap
ConcurrentHashMap

등이 있다.

그중 가장 많이 사용되는 것이 HashMap이다.

12. HashMap

HashMap은 내부적으로 Hash Table 구조를 사용한다.

Map<String, Integer> map = new HashMap<>();

map.put("Kim", 20);
map.put("Lee", 30);

개념적으로는

Kim → 20
Lee → 30

처럼 보이지만 실제로는 Key를 이용해 데이터를 저장할 위치를 계산한다.

Key
 ↓
hashCode
 ↓
Hash 계산
 ↓
Bucket 위치 결정
 ↓
데이터 저장

13. HashMap의 Bucket

HashMap 내부에는 데이터를 저장하기 위한 배열이 존재한다.

배열의 각 위치를 Bucket이라고 생각할 수 있다.

Bucket

0
1
2
3
4
5
6
7

예를 들어 "Kim"이라는 Key가 들어오면

Kim
 ↓
hashCode
 ↓
Hash 계산
 ↓
Bucket 3

처럼 저장할 위치가 결정된다.

0
1
2
3 → Kim, 20
4
5
6
7

조회할 때도 동일하게 Key의 Hash를 계산한다.

map.get("Kim");

Kim
 ↓
Hash 계산
 ↓
Bucket 찾기
 ↓
Key 비교
 ↓
Value 반환

따라서 HashMap의 평균적인 조회 시간은

O(1)

이다.

14. Hash Collision

서로 다른 Key가 같은 Bucket에 들어가는 경우도 있다.

Key A
 ↓
Bucket 3

Key B
 ↓
Bucket 3

이를 Hash Collision이라고 한다.

충돌이 발생하면 같은 Bucket 안에 여러 Node가 저장될 수 있다.

Bucket 3

[A] → [B] → [C]

Java 8 이후 HashMap에서는 충돌이 많이 발생하면 연결 구조를 Red-Black Tree 형태로 변경할 수 있다.

충돌이 적을 때

Node → Node → Node


충돌이 많을 때

       Node
      /    \
   Node    Node

일반적으로 하나의 Bucket에 Node가 일정 수준 이상 쌓이고 전체 용량도 충분히 크면 Tree 구조로 변경된다.

이렇게 하면 충돌이 많이 발생했을 때 탐색 성능 저하를 줄일 수 있다.

15. hashCode와 equals

HashMap은 Hash 값만으로 같은 Key인지 판단하지 않는다.

먼저 hashCode()를 이용해 Bucket을 찾고, 실제 Key가 같은지는 equals()를 이용해 확인한다.

hashCode
 ↓
어느 Bucket인가

equals
 ↓
실제로 같은 Key인가

따라서 사용자 정의 객체를 Key로 사용할 때는 hashCode()와 equals()를 올바르게 구현해야 한다.

Map<User, String> map = new HashMap<>();

두 메서드의 구현이 서로 맞지 않으면 저장했던 객체를 정상적으로 찾지 못하는 문제가 발생할 수 있다.

16. HashMap Resize

HashMap 내부 배열도 크기가 제한되어 있다.

데이터가 많아지면 더 큰 배열을 만든다.

HashMap에는 Load Factor라는 값이 있다.

기본값은 일반적으로

0.75

이다.

Bucket 수가 16이라면

16 × 0.75
= 12

정도가 Threshold가 된다.

데이터가 Threshold를 넘으면 내부 배열을 확장한다.

기존

16 Bucket

   ↓

Resize

32 Bucket

배열이 커지면서 기존 데이터의 위치도 다시 조정된다.

Resize는 비용이 발생하기 때문에 많은 데이터를 저장할 것이 확실한 경우 적절한 초기 크기를 설정하는 것도 중요하다.

17. LinkedHashMap과 LinkedHashSet

LinkedHashMap은 기본적으로 HashMap의 구조를 사용하면서 데이터의 순서까지 유지하기 위한 연결 구조를 추가한다.

HashMap 기능
+
순서 유지

따라서 입력한 순서를 유지하면서 Map을 사용하고 싶을 때 사용할 수 있다.

LinkedHashSet 역시 내부적으로 LinkedHashMap을 사용한다.

LinkedHashSet
     ↓
LinkedHashMap

따라서 중복을 제거하면서 입력 순서도 유지할 수 있다.

18. TreeMap

TreeMap은 Hash Table이 아니라 Red-Black Tree를 사용한다.

Map<Integer, String> map = new TreeMap<>();

Key를 기준으로 정렬된 상태를 유지한다.

        5
       / \
      3   8
     /   / \
    1   7   9

Red-Black Tree는 한쪽으로 지나치게 치우치지 않도록 균형을 유지하는 이진 탐색 트리이다.

따라서 조회, 삽입, 삭제는 일반적으로

O(log n)

이다.

HashMap의 평균 O(1)보다는 느릴 수 있지만 Key가 정렬된 상태로 유지된다는 장점이 있다.

19. TreeSet

TreeSet은 중복을 허용하지 않으면서 정렬된 상태도 유지하는 Set이다.

Set<Integer> set = new TreeSet<>();

set.add(5);
set.add(1);
set.add(3);

결과는

1
3
5

가 된다.

TreeSet은 내부적으로 TreeMap을 사용한다.

TreeSet
   ↓
TreeMap
   ↓
Red-Black Tree

따라서 삽입, 삭제, 탐색은 일반적으로

O(log n)

이다.

20. Queue와 Deque

Queue는 데이터를 일정한 처리 순서에 따라 다루는 구조이다.

보통 먼저 들어온 데이터가 먼저 나오는 FIFO 구조를 생각할 수 있다.

입력

A → B → C

출력

A → B → C

하지만 Java의 Queue 구현체 중에는 우선순위를 기준으로 처리하는 PriorityQueue도 있다.

21. ArrayDeque

ArrayDeque는 내부적으로 배열을 사용한다.

앞쪽과 뒤쪽 모두 데이터를 추가하거나 제거할 수 있다.

Deque<String> deque = new ArrayDeque<>();

deque.addFirst("A");
deque.addLast("B");

deque.removeFirst();
deque.removeLast();

개념적으로는 다음과 같다.

앞쪽 ← [A][B][C] → 뒤쪽

따라서 Queue와 Stack 양쪽 용도로 사용할 수 있다.

Java에서는 단순 Stack 용도로 오래된 Stack 클래스보다 ArrayDeque를 사용하는 것이 일반적으로 권장된다.

22. PriorityQueue

PriorityQueue는 들어온 순서가 아니라 우선순위에 따라 데이터를 꺼내는 Queue이다.

Queue<Integer> queue = new PriorityQueue<>();

queue.add(5);
queue.add(1);
queue.add(3);

queue.poll();

을 실행하면 가장 작은 값인

1

이 먼저 나온다.

PriorityQueue 내부에서는 Heap을 사용한다.

Java의 기본 PriorityQueue는 가장 작은 값이 우선되는 형태로 동작한다.

       1
      / \
     5   3

일반적인 시간 복잡도는 다음과 같다.

삽입
O(log n)

삭제
O(log n)

최상위 값 조회
O(1)

23. 그 외 주요 컬렉션

자주 사용되는 핵심 컬렉션 외에도 다양한 구현체가 존재한다.

이런 컬렉션은 일반적인 상황보다 특정 요구사항이 있을 때 사용한다.

예를 들어

동시성 필요
→ ConcurrentHashMap

입력 순서 유지
→ LinkedHashMap

정렬 필요
→ TreeMap

우선순위 필요
→ PriorityQueue

처럼 선택할 수 있다.

24. 주요 컬렉션 내부 구조 비교

25. 어떤 컬렉션을 사용해야 할까

컬렉션은 어떤 데이터를 저장하느냐보다 데이터를 어떻게 사용할 것인지가 더 중요하다.

인덱스로 데이터를 자주 조회한다면

ArrayList

을 고려할 수 있다.

Key를 이용해 빠르게 값을 찾고 싶다면

HashMap

이 적합하다.

중복을 제거하고 싶다면

HashSet

을 사용할 수 있다.

중복을 제거하면서 입력 순서도 유지해야 한다면

LinkedHashSet

을 사용할 수 있다.

Key를 정렬된 상태로 유지하고 싶다면

TreeMap

을 사용할 수 있다.

양쪽에서 데이터를 추가하거나 제거해야 한다면

ArrayDeque

를 사용할 수 있다.

우선순위에 따라 데이터를 처리해야 한다면

PriorityQueue

를 사용할 수 있다.

멀티스레드 환경에서 여러 Thread가 하나의 Map을 공유해야 한다면

ConcurrentHashMap

같은 동시성 컬렉션을 고려할 수 있다.

26. 핵심 정리

Java 컬렉션은 같은 데이터를 저장하더라도 내부에서 사용하는 자료구조가 다르다.

ArrayList
→ 배열

LinkedList
→ 양방향 연결 리스트

HashMap
→ Hash Table

HashSet
→ HashMap

LinkedHashMap
→ HashMap + 순서 유지 구조

LinkedHashSet
→ LinkedHashMap

TreeMap
→ Red-Black Tree

TreeSet
→ TreeMap

ArrayDeque
→ 배열

PriorityQueue
→ Heap

따라서 컬렉션을 공부할 때는 단순히 클래스 이름을 외우는 것보다 내부 구조와 연결해서 이해하는 것이 중요하다.

특히 다음 질문에 답할 수 있어야 한다.

왜 ArrayList 조회는 O(1)인가

왜 LinkedList 조회는 O(n)인가

왜 HashMap 조회는 평균 O(1)인가

Hash Collision은 무엇인가

HashMap에서 hashCode와 equals는 왜 중요한가

HashMap은 언제 Resize되는가

TreeMap은 왜 O(log n)인가

PriorityQueue는 왜 Heap을 사용하는가

한 문장으로 정리하면

Java 컬렉션은 배열, 연결 리스트, Hash Table, Tree, Heap 등의 자료구조를 기반으로 동작하며 내부 구조에 따라 조회, 삽입, 삭제 성능과 사용 목적이 달라진다.