전체 목록
JavaMedium#57

Java Collections Framework에서 List, Set, Map의 차이와 주요 구현체를 설명해주세요.

#Java#컬렉션#자료구조#핵심개념
힌트

순서, 중복, 키-값 구조의 차이를 생각해보세요.

정답 및 해설

Java Collections Framework에서 List, Set, Map의 차이와 주요 구현체를 설명해주세요.

Java Collections Framework는 데이터를 효율적으로 저장하고 조작하기 위한 자료구조 인터페이스와 구현체의 집합입니다. 크게 List, Set, Map 세 가지 인터페이스로 나뉘며, 각각 고유한 특성을 가집니다.

List — 순서 있음, 중복 허용

List는 삽입 순서를 유지하며 중복 요소를 허용합니다. 인덱스로 접근할 수 있습니다.

ArrayList

내부적으로 동적 배열을 사용합니다.

  • 인덱스로 조회: O(1)
  • 중간 삽입/삭제: O(n) — 이후 요소들을 이동해야 함
  • 끝에 추가(add(e)): 평균 O(1) (용량 초과 시 O(n) 재할당)
List<String> arrayList = new ArrayList<>();
arrayList.add("Java");
arrayList.add("Python");
arrayList.add("Java"); // 중복 허용

System.out.println(arrayList.get(0)); // "Java" — O(1) 조회
System.out.println(arrayList);        // [Java, Python, Java]

// 초기 용량 지정 (재할당 비용 절감)
List<Integer> withCapacity = new ArrayList<>(100);

LinkedList

**이중 연결 리스트(Doubly Linked List)**를 사용합니다.

  • 앞/뒤 삽입/삭제: O(1)
  • 인덱스 조회: O(n) — 순차 탐색 필요
  • Deque 인터페이스도 구현하여 큐/스택으로 활용 가능
LinkedList<String> linkedList = new LinkedList<>();
linkedList.addFirst("Python"); // O(1)
linkedList.addLast("Java");    // O(1)
linkedList.add(1, "Kotlin");   // 중간 삽입

// Deque로 활용
Deque<String> deque = new LinkedList<>();
deque.push("first");
deque.push("second");
System.out.println(deque.pop()); // "second" — 스택처럼 동작

ArrayList vs LinkedList

연산ArrayListLinkedList
조회 (get)O(1)O(n)
끝에 삽입O(1) 평균O(1)
중간 삽입/삭제O(n)O(1)*
메모리연속 배열노드+포인터
캐시 효율높음낮음

*중간 삽입 자체는 O(1)이지만 위치 탐색에 O(n)이 소요됩니다.

Set — 순서 없음(예외 있음), 중복 불허

Set은 중복 요소를 허용하지 않습니다. 요소를 추가할 때 equals()와 hashCode()로 중복 여부를 판단합니다.

HashSet

내부적으로 HashMap을 사용합니다.

  • 추가/삭제/포함 여부: O(1) 평균
  • 순서 보장 없음
Set<String> hashSet = new HashSet<>();
hashSet.add("banana");
hashSet.add("apple");
hashSet.add("cherry");
hashSet.add("apple"); // 중복 — 무시됨

System.out.println(hashSet.size()); // 3
System.out.println(hashSet.contains("apple")); // true — O(1)
// 출력 순서 불규칙: [banana, cherry, apple] 등

LinkedHashSet

HashSet에 삽입 순서를 유지하는 연결 리스트가 추가됩니다.

  • 추가/삭제/포함 여부: O(1) 평균
  • 삽입 순서 보장
  • HashSet보다 약간 더 많은 메모리 사용
Set<String> linkedHashSet = new LinkedHashSet<>();
linkedHashSet.add("banana");
linkedHashSet.add("apple");
linkedHashSet.add("cherry");

System.out.println(linkedHashSet); // [banana, apple, cherry] — 삽입 순서 유지

TreeSet

내부적으로 **레드-블랙 트리(Red-Black Tree)**를 사용합니다.

  • 추가/삭제/포함 여부: O(log n)
  • 자연 정렬 순서 보장 (또는 Comparator 지정 가능)
Set<Integer> treeSet = new TreeSet<>();
treeSet.add(5);
treeSet.add(1);
treeSet.add(3);

System.out.println(treeSet); // [1, 3, 5] — 정렬 순서

// 역순 정렬
Set<Integer> descSet = new TreeSet<>(Comparator.reverseOrder());
descSet.addAll(List.of(5, 1, 3));
System.out.println(descSet); // [5, 3, 1]

// 범위 조회 (TreeSet 특화 기능)
NavigableSet<Integer> nav = (NavigableSet<Integer>) treeSet;
System.out.println(nav.headSet(3)); // [1] — 3 미만
System.out.println(nav.tailSet(3)); // [3, 5] — 3 이상

Map — 키-값 쌍, 키는 중복 불허

Map은 키(key)와 값(value)의 쌍으로 데이터를 저장합니다. 키는 중복될 수 없으며, 값은 중복 가능합니다.

HashMap

  • 조회/삽입/삭제: O(1) 평균
  • 순서 보장 없음
  • null 키 하나, null 값 여러 개 허용
  • Java 8+: 해시 충돌이 많을 경우 연결 리스트 → 트리(TreeNode)로 전환
Map<String, Integer> hashMap = new HashMap<>();
hashMap.put("Alice", 30);
hashMap.put("Bob", 25);
hashMap.put("Alice", 31); // 키 중복 — 값이 업데이트됨

System.out.println(hashMap.get("Alice")); // 31
System.out.println(hashMap.getOrDefault("Charlie", 0)); // 0 — 키 없을 때 기본값

// 편리한 조작 메서드
hashMap.putIfAbsent("Dave", 28);
hashMap.computeIfAbsent("Eve", k -> k.length()); // 키가 없으면 함수로 값 계산

LinkedHashMap

  • 삽입 순서(또는 접근 순서) 보장
  • LRU 캐시 구현에 활용 가능
Map<String, Integer> linkedHashMap = new LinkedHashMap<>();
linkedHashMap.put("banana", 1);
linkedHashMap.put("apple", 2);
linkedHashMap.put("cherry", 3);

// 삽입 순서 보장
linkedHashMap.forEach((k, v) -> System.out.println(k + ": " + v));
// banana: 1, apple: 2, cherry: 3

// LRU 캐시 구현
Map<String, Integer> lruCache = new LinkedHashMap<>(16, 0.75f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry<String, Integer> eldest) {
        return size() > 3; // 최대 3개 유지
    }
};

TreeMap

  • 키의 자연 정렬 순서 보장
  • 조회/삽입/삭제: O(log n)
  • 범위 조회 기능 제공
TreeMap<String, Integer> treeMap = new TreeMap<>();
treeMap.put("banana", 1);
treeMap.put("apple", 2);
treeMap.put("cherry", 3);

System.out.println(treeMap); // {apple=2, banana=1, cherry=3} — 키 정렬
System.out.println(treeMap.firstKey()); // apple
System.out.println(treeMap.lastKey());  // cherry
System.out.println(treeMap.subMap("apple", "cherry")); // {apple=2, banana=1}

ConcurrentHashMap

멀티스레드 환경에서 안전하게 사용할 수 있는 HashMap입니다.

  • 세그먼트(Segment) 단위 잠금 (Java 8+: 버킷 단위 잠금)으로 높은 동시성 지원
  • Collections.synchronizedMap()보다 성능 우수
  • null 키/값 허용하지 않음
Map<String, Integer> concurrentMap = new ConcurrentHashMap<>();

// 멀티스레드 환경에서 안전
ExecutorService executor = Executors.newFixedThreadPool(10);
for (int i = 0; i < 100; i++) {
    final int count = i;
    executor.submit(() -> concurrentMap.put("key" + count, count));
}

// 원자적 연산
concurrentMap.putIfAbsent("key", 1);
concurrentMap.compute("key", (k, v) -> v == null ? 1 : v + 1);

전체 비교 정리

구분구현체순서중복시간복잡도특징
ListArrayList삽입 순서허용조회 O(1)일반적인 목록
ListLinkedList삽입 순서허용삽입/삭제 O(1)빈번한 삽입/삭제
SetHashSet없음불허O(1)중복 제거
SetLinkedHashSet삽입 순서불허O(1)순서 있는 중복 제거
SetTreeSet정렬 순서불허O(log n)정렬된 집합
MapHashMap없음키 불허O(1)일반적인 맵
MapLinkedHashMap삽입 순서키 불허O(1)LRU 캐시
MapTreeMap키 정렬키 불허O(log n)정렬된 맵
MapConcurrentHashMap없음키 불허O(1)스레드 안전
이전 질문다음 질문