Java Collection Framework

Java Collection Framework 구조

java.util
 └─ Collection<E> (인터페이스)
     ├─ List<E>        → 순서 O, 중복 O
     ├─ Set<E>         → 순서 X, 중복 X
     ├─ Queue<E>       → FIFO, 우선순위 등
     └─ Deque<E>       → 양방향 큐

주요 자료구조 목록

List 계열 (순서 보장, 인덱스 접근 가능)

클래스	특징
ArrayList	배열 기반, 빠른 조회, 느린 삽입/삭제 (중간)
LinkedList	연결 리스트 기반, 빠른 삽입/삭제, 느린 조회
Vector	ArrayList와 유사하지만 동기화됨 (Thread-safe, 레거시)
Stack	Vector 기반 LIFO 스택 자료구조 (레거시)

Set 계열 (중복 허용 X)

클래스	특징
HashSet	해시 기반, 순서 보장 안 함, 가장 빠름
LinkedHashSet	입력 순서 유지
TreeSet	정렬된 Set (이진 탐색 트리 기반)

Queue/Deque 계열 (FIFO/ 양방향)

클래스	특징
PriorityQueue	우선순위 큐 (힙 기반)
ArrayDeque	양방향 큐, Stack과 Queue 대체 가능
LinkedList	Deque, Queue, List를 모두 구현

Map 계열 (Collection 아님)

클래스	특징
HashMap	가장 일반적인 Map, 순서 없음
LinkedHashMap	입력 순서 유지
TreeMap	정렬된 Map (이진 탐색 트리 기반)
Hashtable	동기화된 레거시 Map
ConcurrentHashMap	멀티스레드 환경에서 성능 좋음

ArrayList

ArrayList는 Java Collection Framework에서 List 인터페이스를 구현한 배열 기반 동적 자료구조입니다.

• 순서 보장 (index 접근 가능)
• 중복 허용
• 배열 기반 → 동적 크기 조절 가능
• null 값 허용

List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
System.out.println(list); // [A, B]

내부 구조

내부 필드 (JDK 17 기준)

transient Object[] elementData; // 실제 데이터를 저장하는 배열
private int size;               // 저장된 요소 수

초기 용량 및 확장

• 기본 초기 용량: 10
• 요소 추가 시 용량이 부족하면 자동으로 확장
• 확장 방식: 약 1.5배씩 증가

newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5배

확장 과정 (시간 소요 있음)

1. 새 배열 생성
2. 기존 배열 복사 (System.arraycopy)
3. 새 배열로 교체

   자주 resize가 일어나면 성능에 영향을 미치므로 초기 용량을 지정하는 것이 좋음

List<Integer> list = new ArrayList<>(100); // 초기 용량 설정

시간 복잡도

연산	시간 복잡도	설명
get(index)	O(1)	배열 기반이라 즉시 접근 가능
add(e) (끝)	O(1) amortized	대부분 빠르지만, resize 시 O(n)
add(i, e) (중간 삽입)	O(n)	뒤 요소들 이동 필요
remove(i)	O(n)	삭제 후 뒤 요소들 이동 필요, 끝은 O(1)
contains(e)	O(n)	선형 탐색 필요

주요 메서드

add(E e), add(int index, E e)

list.add("Java");
list.add(0, "Spring");

get(int index), set(int index, E e)

String s = list.get(1);
list.set(1, "Spring Boot");

remove(int index), remove(Object o)

list.remove(0);
list.remove("Spring");

contains(Object o), indexOf(Object o)

list.contains("Java"); // true
list.indexOf("Java");  // 0

clear(), isEmpty(), size()

list.clear();      // 모두 삭제
list.isEmpty();    // 비어 있는지 확인
list.size();       // 요소 개수

LinkedList

LinkedList는 Java Collection Framework에서 List, Queue, Deque 인터페이스를 모두 구현한 이중 연결 리스트 기반 자료구조입니다.

• 순서 유지 (List 인터페이스 구현)
• 중복 허용
• 빠른 삽입/삭제 성능 (특히 앞/뒤에서)

내부 구조

이중 연결 리스트 (Doubly Linked List)

각 노드는 다음과 같은 구조를 가집니다:

[prev] ← [ data ] → [next]

내부 노드 클래스 (JDK 17 기준)

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
}

주요 필드

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
}

• first, last: 양쪽 끝 노드를 참조
• next, prev 포인터로 양방향 이동 가능

시간 복잡도

연산	시간 복잡도	설명
get(index)	O(n)	앞/뒤에서 탐색 시작, 중간은 느림
addLast(), addFirst()	O(1)	끝에서 삽입
add(index, e)	O(n)	위치 찾아서 삽입
removeFirst(), removeLast()	O(1)	끝에서 삭제
remove(index)	O(n)	위치 찾아서 삭제
contains()	O(n)	순차 탐색

주요 메서드

기본 삽입/삭제

LinkedList<String> list = new LinkedList<>();
list.add("A");       // 끝에 삽입
list.addFirst("B");  // 앞에 삽입
list.addLast("C");   // 끝에 삽입
list.remove();       // 앞에서 제거
list.removeLast();   // 뒤에서 제거

인덱스 기반 접근

list.get(1);         // 두 번째 요소 조회 (O(n))
list.set(0, "X");     // 첫 번째 요소 수정
list.remove(1);      // 두 번째 요소 제거

기타 메서드

list.size();
list.contains("A");
list.isEmpty();
list.clear();

ArrayDeque

ArrayDeque는 Java Collection Framework에서 Stack, Queue, Deque 인터페이스를 구현한 배열 기반 양방향 큐(Deque) 자료구조입니다.

• 내부적으로 원형 배열 (circular array) 사용
• null 요소 허용 X
• Thread-safe X

내부 구조

배열 기반 (Object[] elements)

• 초기에 크기 16의 배열 생성
• 배열이 꽉 차면 2배로 자동 확장
• 앞뒤로 요소를 삽입/삭제할 수 있도록 원형 큐 방식 사용

내부 필드 (JDK 기준)

transient Object[] elements;
transient int head;
transient int tail;

• head: 첫 번째 요소의 위치
• tail: 다음에 삽입할 위치
• size: 별도로 없고 head/tail로 계산

시간 복잡도

연산	시간 복잡도	설명
addFirst, addLast	O(1) amortized	매우 빠름
removeFirst, removeLast	O(1)	매우 빠름
peekFirst, peekLast	O(1)
resize 발생 시	O(n)	배열 복사 필요

주요 메서드

삽입

deque.addFirst("A");
deque.addLast("B");
deque.offerFirst("C");
deque.offerLast("D");

삭제

deque.removeFirst();   // 큐가 비었을 때 NoSuchElementException 발생
deque.removeLast();
deque.pollFirst();     // 큐가 비었을 때 null 반환
deque.pollLast();

조회

deque.peekFirst();
deque.peekLast();

스택처럼 사용

Deque<String> stack = new ArrayDeque<>();
stack.push("X");   // = addFirst
stack.pop();       // = removeFirst
stack.peek();      // = peekFirst

PriorityQueue

PriorityQueue는 우선순위에 따라 요소를 정렬하는 힙(Heap) 기반의 큐입니다.

• 기본은 최소 힙(Min-Heap): 가장 작은 값이 먼저 나옴
• 커스텀 Comparator로 우선순위 변경 가능
• null 저장 불가, thread-safe 아님

내부 구조

• 내부 배열 (Object[] queue)을 사용
• 요소는 min heap backed by array 구조로 저장
• 삽입 시 siftUp(), 삭제 시 siftDown()을 통해 힙 속성 유지

시간 복잡도

연산	시간 복잡도	설명
add()	O(log n)	마지막에 삽입 후 정렬
poll()	O(log n)	루트 제거 후 재정렬
peek()	O(1)	최상단 요소 조회
remove(Object)	O(n)	특정 요소 제거
contains()	O(n)	선형 탐색

예제

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(3);
pq.add(1);
pq.add(2);
System.out.println(pq.poll()); // 1 (우선순위 가장 높음)

// 커스텀 정렬
PriorityQueue<String> pq = new PriorityQueue<>(
  Comparator.reverseOrder()
);

HashMap

HashMap은 키-값 쌍을 저장하는 해시 기반 Map입니다.

• 순서 보장 X
• null key 1개, null value 다수 허용
• 내부적으로 배열 + LinkedList or Tree 사용 (Java 8+부터)

내부 구조

• 배열(Node[]) + 체이닝(LinkedList → Tree)
• hashCode()로 인덱스 결정 → 충돌 발생 시 연결

static class Node<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
}

• Java 8+: 충돌이 많을 경우 LinkedList → Red-Black Tree 전환 조건
  • TREEIFY_THRESHOLD = 8
  • MIN_TREEIFY_CAPACITY = 64

시간 복잡도

연산	평균	최악 (충돌 심한 경우)
get/put	O(1)	O(n) (Java 7 이하)
		O(log n) (Java 8+)
remove()	O(1)	O(log n)

주요 메서드

map.put("key", "value");
map.get("key");
map.containsKey("key");
map.remove("key");

HashSet

HashSet은 중복 없는 요소 저장을 위한 Set 인터페이스 구현체입니다.

• 내부적으로 HashMap 사용
• 순서 보장 X
• null 1개 허용
• equals()와 hashCode()가 같아도 add() 시 덮어쓰지 않음

내부 구조

private transient HashMap<E,Object> map;
private static final Object PRESENT = new Object();

→ map.put(element, PRESENT) 구조

시간 복잡도

연산	평균 시간
add()	O(1)
remove()	O(1)
contains()	O(1)

주요 메서드

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

TreeMap

TreeMap은 키 정렬이 보장된 이진 탐색 트리 기반 Map입니다.

• 내부적으로 Red-Black Tree 사용
• Comparable 또는 Comparator 필수
• null key ❌ (NPE 발생), null value 허용

내부 구조

• 노드는 부모/자식 참조가 있는 Entry 객체
• 자동 정렬됨 (in-order 순회 기준)

시간 복잡도

연산	시간 복잡도	설명
get, put	O(log n)	이진 탐색 트리 경로 따라 탐색
remove	O(log n)	삭제 후 재균형화 필요
containsKey	O(log n)	get()과 동일
containsValue	O(n)	노드 전체 순회
firstKey	O(log n)	루트에서 왼쪽 최단 경로

주요 메서드

TreeMap<String, Integer> map = new TreeMap<>();
map.put("b", 2);
map.put("a", 1);
System.out.println(map); // {a=1, b=2}`

TreeSet

TreeSet은 정렬된 요소를 저장하는 이진 탐색 트리 기반 Set입니다.

• 내부적으로 TreeMap 사용
• 자동 정렬 (오름차순 기본), 중복 X
• null 요소 ❌

내부 구조

private transient NavigableMap<E,Object> m;

시간 복잡도

연산	시간 복잡도
add()	O(log n)
remove()	O(log n)
contains()	O(log n)

주요 메서드

TreeSet<Integer> set = new TreeSet<>();
set.add(3);
set.add(1);
set.add(2);
System.out.println(set); // [1, 2, 3]