[Java] 컬렉션 프레임워크

* 개념 복습과 학습 정도를 파악하고자 포스팅합니다

 

컬렉션 프레임워크(Collections Framework)

1. 컬렉션 프레임워크??

저도 사실 자바를 처음 접했을 때 컬렉션 프레임워크라는 명칭만 듣고 괜히 "아, 이거 너무 어려운거 아닐까?" 라며 겁을 먹곤 했었는데요!

사실 겁먹을게 아니고 그냥 학부생일 때, 또는 CS공부할 때 자료구조 배우잖아요? 컬렉션 프레임워크는 자료구조 형태를 자바 클래스로 구현한 모음이라고 생각하시면 편할 것 같습니다!

각 항목을 클릭해도 자세한 설명은 볼 수 없어요 ㅎㅎ.. :)

위 구조를 요약하자면, 최상단의 Iterable → Collection 에서 List, Set, Queue 세 갈래로 뻗어나가고, Map은 Collection과는 무관한 별도 계층입니다. 실선 화살표는 구현 관계, 점선은 상속 관계입니다.

 

util.*; 를 import하면 Iterable 인터페이스와 Map 인터페이스를 사용할 수 있습니다!

---

2. List - 순서가 있는 컬렉션

특징: 인덱스로 접근 가능, 중복 허용, 삽입 순서 유지

 

ArrayList

읽기 또는 검색이 많고, 끝에 추가가 대부분일 때 사용합니다.

구조: [ "Apple" | "Banana" | "Cherry" | "Date ]
         -> index로 0(1) 접근이 가능

메서드	반환	시간복잡도	설명
add(E e)	boolean	O(1)*	끝에 요소 추가
add(int i, E e)	void	O(n)	중간 삽입 (뒤 요소 밀림)
get(int i)	E	O(1)	인덱스로 요소 조회
set(int i, E e)	E	O(1)	인덱스 요소 교체
remove(int i)	E	O(n)	인덱스 요소 제거
remove(Object o)	boolean	O(n)	객체 탐색 후 제거
size()	int	O(1)	요소 개수
contains(Object o)	boolean	O(n)	포함 여부
indexOf(Object o)	int	O(n)	첫 번째 인덱스 반환
subList(from, to)	List	O(1)	부분 리스트 (뷰)
sort(Comparator c)	void	O(n log n)	정렬
clear()	void	O(n)	전체 삭제

// 사용 예시
ArrayList<String> list = new ArrayList<>();
list.add("Apple");           // [Apple]
list.add("Banana");          // [Apple, Banana]
list.add(1, "Mango");        // [Apple, Mango, Banana]
String s = list.get(0);      // "Apple"
list.set(0, "Grape");        // [Grape, Mango, Banana]
list.remove(1);              // [Grape, Banana]
list.contains("Banana");     // true
list.sort(Comparator.naturalOrder()); // [Banana, Grape]

 

LinkedList

앞 / 뒤 삽입 또는 삭제가 빈번할 때, 스택/큐에 대응하고자 할 때 사용합니다.

구조: null ← [Apple] ⇄ [Banana] ⇄ [Cherry] → null
        앞/뒤 포인터로 연결된 이중 연결 리스트

메서드	반환	시간복잡도	설명
addFirst(E e)	void	O(1)	맨 앞에 추가
addLast(E e)	void	O(1)	맨 뒤에 추가
removeFirst()	E	O(1)	맨 앞 제거 후 반환
removeLast()	E	O(1)	맨 뒤 제거 후 반환
peekFirst()	E	O(1)	맨 앞 조회 (제거 안 함)
peekLast()	E	O(1)	맨 뒤 조회 (제거 안 함)
push(E e)	void	O(1)	스택처럼 앞에 push
pop()	E	O(1)	스택처럼 앞에서 pop
get(int i)	E	O(n)	인덱스 접근 (느림!)

// 사용 예시
LinkedList<String> ll = new LinkedList<>();
ll.addLast("Banana");    // [Banana]
ll.addFirst("Apple");    // [Apple, Banana]
ll.addLast("Cherry");    // [Apple, Banana, Cherry]
ll.peekFirst();          // "Apple" (제거 안 함)
ll.pollFirst();          // "Apple" 제거 후 반환 → [Banana, Cherry]
ll.push("Mango");        // [Mango, Banana, Cherry]
ll.pop();                // "Mango" 제거

 

ArrayList vs LinkedList 비교

작업	ArrayList	LinkedList
인덱스 조회	O(1)	O(n) - 느림
끝에 추가	O(1)	O(1)
중간 삽입 / 삭제	O(n) - 느림	O(1) - 포인터만 변경
검색	O(n) - 느림	O(n) - 느림
메모리	효율적	포인터 오버헤드

 

---

3. Set - 중복 없는 컬렉션

특징: 중복 허용 안함, 수학접 집합과 동일

 

HashSet

중복을 제거하거나 포함 여부를 빠르게 확인하거나 순서가 불필요할 때 사용합니다.

구조 (해시 테이블):
버킷[0]: → "Apple"
버킷[1]: → (비어있음)
버킷[2]: → "Cherry"→ "Mango" (해시 충돌 시 체이닝)
버킷[3]: → "Banana"

메서드반환시간복잡도설명

 

메서드	반환	시간복잡도	설명
add(E e)	boolean	O(1)*	추가 (중복이면 false)
remove(Object o)	boolean	O(1)*	제거
contains(Object o)	boolean	O(1)*	포함 여부
size()	int	O(1)	요소 수
addAll(Collection c)	boolean	O(n)	합집합 (union)
retainAll(Collection c)	boolean	O(n)	교집합 (intersection)
removeAll(Collection c)	boolean	O(n)	차집합 (difference)
containsAll(Collection c)	boolean	O(n)	부분집합 여부

// 집합 연산 예시
Set<Integer> A = new HashSet<>(Arrays.asList(1, 2, 3, 4));
Set<Integer> B = new HashSet<>(Arrays.asList(3, 4, 5, 6));

// 합집합
Set<Integer> union = new HashSet<>(A);
union.addAll(B);        // {1, 2, 3, 4, 5, 6}

// 교집합
Set<Integer> inter = new HashSet<>(A);
inter.retainAll(B);     // {3, 4}

// 차집합
Set<Integer> diff = new HashSet<>(A);
diff.removeAll(B);      // {1, 2}

 

 

LinkedHashSet

중복 제거 + 삽입 순서 유지가 동시에 필요할 때 사용합니다. 메소드는 HashSet과 동일하게 사용할 수 있어요!

LinkedHashSet<String> lhs = new LinkedHashSet<>();
lhs.add("Banana");
lhs.add("Apple");
lhs.add("Cherry");
lhs.add("Banana");  // 무시 (중복)
// 출력: [Banana, Apple, Cherry] ← 삽입 순서 유지

 

TreeSet

정렬된 집합이 필요합니다.

범위 검색, 최솟값 또는 최댓값을 빠르게 구해야할 때 사용합니다.

구조 (레드-블랙 트리):
                      [5]
                     /     \
                 [3]     [8]
                 / \        / \
              [1][4]  [6][9]
자동으로 오름차순 정렬 유지!

메서드	반환	설명
first()	E	최솟값
last()	E	최댓값
floor(E e)	E	e 이하인 최대 요소
ceiling(E e)	E	e 이상인 최소 요소
headSet(E to)	SortedSet	to 미만인 부분 집합
tailSet(E from)	SortedSet	from 이상인 부분 집합
subSet(from, to)	SortedSet	범위 부분 집합
pollFirst()	E	최솟값 제거 후 반환
pollLast()	E	최댓값 제거 후 반환

// 사용예시
TreeSet<Integer> ts = new TreeSet<>();
ts.add(5); ts.add(1); ts.add(8); ts.add(3);
// 자동 정렬: [1, 3, 5, 8]

ts.first();        // 1
ts.last();         // 8
ts.floor(4);       // 3  (4 이하 최대)
ts.ceiling(4);     // 5  (4 이상 최소)
ts.headSet(5);     // [1, 3]  (5 미만)
ts.tailSet(5);     // [5, 8]  (5 이상)
ts.subSet(3, 8);   // [3, 5]  (3이상 8미만)

---

4. Map - 키-값 쌍 컬렉션

특징: Key-Value 쌍, 키 중복 불가, 값 중복 허용

 

HashMap

빠른 키-값 조회, 캐싱, 빈도수 계산할 때 사용합니다.

메서드	반환	시간복잡도	설명
put(K, V)	V	O(1)*	키-값 저장 (기존 값 반환)
get(Object k)	V	O(1)*	키로 값 조회
remove(Object k)	V	O(1)*	키-값 제거
containsKey(Object k)	boolean	O(1)*	키 존재 여부
containsValue(Object v)	boolean	O(n)	값 존재 여부
getOrDefault(K, V)	V	O(1)*	없으면 기본값 반환
putIfAbsent(K, V)	V	O(1)*	키 없을 때만 저장
keySet()	Set<K>	O(1)	모든 키 집합
values()	Collection<V>	O(1)	모든 값 컬렉션
entrySet()	Set<Entry>	O(1)	키-값 쌍 집합
forEach(BiConsumer)	void	O(n)	전체 순회
merge(K, V, BiFunction)	V	O(1)*	키 있으면 병합, 없으면 추가
compute(K, BiFunction)	V	O(1)*	키의 값을 함수로 갱신

 

// 사용 예시
HashMap<String, Integer> scores = new HashMap<>();
scores.put("Alice", 90);
scores.put("Bob", 85);
scores.put("Alice", 95);   // Alice 값 덮어쓰기

scores.get("Alice");                   // 95
scores.getOrDefault("Eve", 0);         // 0 (없는 키)
scores.putIfAbsent("Bob", 100);        // Bob 이미 있으므로 무시

// 빈도수 계산 패턴
String[] words = {"apple", "banana", "apple", "cherry"};
Map<String, Integer> freq = new HashMap<>();
for (String w : words) {
    freq.merge(w, 1, Integer::sum);
}
// {apple=2, banana=1, cherry=1}

// 순회 (entrySet이 가장 효율적)
for (Map.Entry<String, Integer> e : scores.entrySet()) {
    System.out.println(e.getKey() + " → " + e.getValue());
}
scores.forEach((k, v) -> System.out.println(k + " → " + v));

 

LinkedHashMap

순서를 유지하는 Map, LRU 캐시를 구현할 때 씁니다.

구조: HashMap + 이중 연결 리스트
삽입 순서: "name"→"Alice" → "age"→25 → "city"→"Seoul" 유지

// LRU 캐시 구현 (accessOrder=true)
LinkedHashMap<String, Integer> lruCache =
    new LinkedHashMap<>(16, 0.75f, true) {
        @Override
        protected boolean removeEldestEntry(Map.Entry<String,Integer> e) {
            return size() > 3;  // 최대 3개 유지
        }
    };
lruCache.put("A", 1);
lruCache.put("B", 2);
lruCache.put("C", 3);
lruCache.get("A");    // A를 최근 사용으로 이동
lruCache.put("D", 4); // 가장 오래된 B 제거
// {C=3, A=1, D=4}

 

TreeMap

키 정렬이 필요하거나 범위를 검색할 때, 사전순으로 정렬할 때 주로 사용합니다.

구조 (레드-블랙 트리):
키 자동 정렬
"Apple"→1 < "Banana"→2 < "Cherry"→3

메서드	반환	설명
firstKey()	K	가장 작은 키
lastKey()	K	가장 큰 키
floorKey(K k)	K	k 이하인 최대 키
ceilingKey(K k)	K	k 이상인 최소 키
headMap(K to)	SortedMap	to 미만 부분 맵
tailMap(K from)	SortedMap	from 이상 부분 맵
subMap(from, to)	SortedMap	범위 부분 맵

TreeMap<String, Integer> tm = new TreeMap<>();
tm.put("Banana", 2);
tm.put("Apple", 1);
tm.put("Cherry", 3);
// 자동 정렬: {Apple=1, Banana=2, Cherry=3}

tm.firstKey();              // "Apple"
tm.floorKey("Be");          // "Banana"
tm.headMap("Cherry");       // {Apple=1, Banana=2}
tm.subMap("Apple","Cherry");// {Apple=1, Banana=2}

---

5. Queue / Deque - 줄 서기 자료구조

Queue (FIFO)

삽입(offer) → [ C | B | A(1) ] → 꺼내기(poll)
                         앞 ← 뒤
먼저 들어온 A가 먼저 나감

메서드	반환	설명
offer(E e)	boolean	뒤에 추가 (실패 시 false)
poll()	E	앞 제거 후 반환 (비면 null)
peek()	E	앞 조회, 제거 안 함 (비면 null)
add(E e)	boolean	뒤에 추가 (실패 시 예외)
remove()	E	앞 제거 후 반환 (비면 예외)
element()	E	앞 조회 (비면 예외)

Queue<String> queue = new LinkedList<>();
queue.offer("A");    // [A]
queue.offer("B");    // [A, B]
queue.offer("C");    // [A, B, C]
queue.peek();        // "A" (제거 안 함)
queue.poll();        // "A" 제거 → [B, C]
queue.poll();        // "B" 제거 → [C]

 

 

PriorityQueue (우선순위 큐)

다익스트라, 작업 스케줄링, top-K 문제를 해결할 때 사용합니다.

구조 (최소 힙):
                [1]
               /    \
            [3]  [5]
           /    \
        [4]  [8]
항상 가장 작은 값이 앞으로

// 기본: 오름차순 (최솟값 우선)
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(5); pq.offer(1); pq.offer(3);
pq.poll();   // 1 (최솟값)
pq.poll();   // 3
pq.poll();   // 5

// 내림차순 (최댓값 우선)
PriorityQueue<Integer> maxPq =
    new PriorityQueue<>(Comparator.reverseOrder());

// 객체 정렬
PriorityQueue<int[]> taskPq =
    new PriorityQueue<>((a, b) -> a[1] - b[1]); // 두 번째 값 기준

 

ArrayDeque (양방향 큐)

Stack을 대체해서 사용합니다. 양방향 큐, BFS/DFS 문제를 해결할 때 사용합니다.

구조:
앞(Front)   [ D | C | B | A ]    뒤(Rear)
     ↑ offerFirst/pollFirst           ↑ offerLast/pollLast
스택으로도, 큐로도 사용 가능!

메서드	설명
offerFirst(E e)	앞에 추가
offerLast(E e)	뒤에 추가
pollFirst()	앞 제거 후 반환
pollLast()	뒤 제거 후 반환
peekFirst()	앞 조회
peekLast()	뒤 조회
push(E e)	스택: 앞에 추가
pop()	스택: 앞 제거

---

핵심 정리

ArrayList	인덱스 접근 빠른 동적 배열
LinkedList	앞뒤 삽입 빠른 연결 리스트, 스택/큐 대용
HashSet	중복 제거, 순서 없음, O(1)
LinkedHashSet	중복 제거 + 삽입 순서 유지
TreeSet	중복 제거 + 자동 정렬 + 범위 검색
HashMap	키-값 빠른 저장/조회, O(1)
LinkedHashMap	키-값 + 삽입 순서 유지, LRU 캐시
TreeMap	키-값 + 키 자동 정렬 + 범위 검색
PriorityQueue	우선순위 큐, 최솟값 자동 정렬
ArrayDeque	양방향 큐, Stack/Queue 대체 권장