Eric's Garden🌳

컬렉션 프레임워크 - 언제 List, Set, Map 을 쓰나

5 min read

1. 개요

ArrayList 와 LinkedList 중 뭘 써야 하냐는 질문에 “중간 삽입이 잦으면 LinkedList” 라고 외워둔 사람이 많다. 실무에서는 거의 항상 ArrayList 가 이긴다. 이 글은 왜 그런지, 그리고 Map 구현체 세 가지를 언제 나눠 쓰는지 정리한다.

2. 핵심 내용

2-1. ArrayList vs LinkedList

ArrayList 는 내부적으로 배열이다. 인덱스로 접근하면 O(1)이고, 배열이 꽉 차면 더 큰 배열로 복사해서 늘린다. LinkedList 는 이중 연결 리스트라 특정 노드를 이미 가리키고 있다면 그 위치에 O(1)로 삽입·삭제할 수 있다.

문제는 “그 위치를 찾아가는” 과정이다. 인덱스로 중간 위치에 접근하려면 LinkedList 도 처음부터 노드를 따라가야 해서 O(n)이다. 실제로 중간 삽입이 잦은 대부분의 코드는 이미 순회 중인 이터레이터 위치에 삽입하는 게 아니라 인덱스나 값으로 위치를 찾아 삽입한다. 그 순간 LinkedList 의 장점이 사라진다. 게다가 배열은 메모리가 연속이라 CPU 캐시 적중률이 높은데, 연결 리스트는 노드가 흩어져 있어 캐시 미스가 잦다. 그래서 실무 기준은 단순하다: 거의 항상 ArrayList, 이터레이터로 순회하면서 계속 앞뒤로 삽입·삭제하는 특수한 큐/덱 용도가 아니면 LinkedList 를 고를 이유가 거의 없다.

2-2. HashMap, LinkedHashMap, TreeMap

세 Map 은 순서 보장과 성능이 다르다.

Map<String, Integer> hash = new HashMap<>();
Map<String, Integer> linked = new LinkedHashMap<>();
Map<String, Integer> tree = new TreeMap<>();
 
for (String key : List.of("banana", "apple", "cherry")) {
    hash.put(key, 1);
    linked.put(key, 1);
    tree.put(key, 1);
}
 
System.out.println(hash.keySet());   // 순서 보장 안 됨 (해시값 기반 배치)
System.out.println(linked.keySet()); // [banana, apple, cherry] 삽입 순서
System.out.println(tree.keySet());   // [apple, banana, cherry] 정렬 순서
  • HashMap: 키의 hashCode() 로 버킷을 찾는다. 평균 O(1)이지만 순서는 보장하지 않는다. hashCode/equals 계약이 깨지면 조회가 실패하는 건 앞선 글에서 다뤘다.
  • LinkedHashMap: HashMap 에 이중 연결 리스트를 얹어 삽입 순서(또는 접근 순서)를 유지한다. removeEldestEntry 를 오버라이드하면 간단한 LRU 캐시로 쓸 수 있다.
  • TreeMap: 레드-블랙 트리로 키를 정렬 상태로 유지한다. 조회는 O(log n)으로 HashMap 보다 느리지만, 범위 검색(headMap, tailMap)이나 정렬된 순회가 필요하면 이게 유일한 선택지다.

Set 도 마찬가지 구조다. HashSet 은 내부적으로 HashMap 을 그대로 쓰고(값은 더미), LinkedHashSet/TreeSet 도 각각 대응하는 Map 을 내부에 두고 있다.

2-3. 고르는 기준

순서가 필요 없고 조회 속도가 중요하면 HashMap/HashSet. 입력 순서를 그대로 보여줘야 하면(예: 화면에 보여줄 메뉴 목록) LinkedHashMap. 정렬된 상태를 유지하거나 범위 조건이 필요하면 TreeMap. 리스트는 거의 항상 ArrayList 로 시작하고, 정말 양쪽 끝에서만 넣고 빼는 큐라면 ArrayDeque 를 먼저 고려한다.

3. 마무리

요약

  • LinkedList 의 “중간 삽입 O(1)“은 이미 그 위치를 가리키고 있을 때만 유효하다. 실무에서는 대부분 ArrayList 가 낫다.
  • HashMap 은 순서 없이 평균 O(1), LinkedHashMap 은 삽입/접근 순서 유지, TreeMap 은 정렬 상태를 O(log n)에 유지한다.
  • Set 계열은 대응하는 Map 을 내부적으로 그대로 쓴다.
  • 다음은 이 컬렉션들을 함수형으로 다루는 람다식과 함수형 인터페이스 얘기로 이어진다.

최신글

그래프 뷰

백링크