왜 이 주제가 중요한가

15편에서 List·Set·Map 인터페이스가 각각 어떤 계약을 강제하는지 정리했다. 그런데 같은 인터페이스라도 구현체에 따라 내부 동작 방식이 전혀 다르고, 이 차이가 실행 속도에 직접 영향을 준다. 독학사 시험은 “이 상황에는 어떤 컬렉션을 쓰는 것이 적절한가”를 묻는 유형이 자주 나오는데, 정답을 고르려면 왜 그 구현체가 그 상황에 유리한지 내부 구조로 설명할 수 있어야 한다. 이 편에서는 ArrayList vs LinkedList, HashSet vs TreeSet, HashMap vs TreeMap을 내부 구조부터 비교하고, 컬렉션 선택 판단 흐름을 정리한다.

ArrayList vs LinkedList: 배열이냐 연결이냐

쉽게 말하면: ArrayList는 크기가 자동으로 늘어나는 배열이고, LinkedList는 기차 칸처럼 앞뒤 칸의 위치만 알고 있는 노드들이 사슬처럼 연결된 구조다.

ArrayList(배열리스트)는 내부적으로 배열을 사용한다. 원소를 추가하다가 배열이 꽉 차면, 더 큰 배열을 새로 만들어 기존 원소를 전부 복사하는 방식으로 크기를 늘린다. 이 내부 구조 때문에 get(인덱스)로 특정 위치의 값을 읽는 것은 배열 인덱싱 한 번으로 바로 접근할 수 있어 매우 빠르다. 반면 리스트 중간에 원소를 끼워 넣거나 빼려면, 그 뒤에 있는 모든 원소를 한 칸씩 밀거나 당겨야 한다.

LinkedList(연결리스트)는 내부적으로 각 원소를 별도의 노드(node) 객체로 감싸고, 각 노드가 “다음 노드”와 “이전 노드”의 참조(04편에서 배운 객체 참조)만 갖고 있는 구조다. 특정 인덱스의 값을 읽으려면 첫 노드부터 하나씩 따라가야 하므로 ArrayList보다 느리지만, 이미 위치를 알고 있는 노드 앞뒤에 새 노드를 끼워 넣거나 빼는 것은 그 노드의 참조 몇 개만 바꾸면 되므로 상대적으로 유리하다.

import java.util.*;
 
public class ArrayListVsLinkedList {
    public static void main(String[] args) {
        List<String> arrayList = new ArrayList<>(List.of("A", "B", "C", "D"));
        List<String> linkedList = new LinkedList<>(List.of("A", "B", "C", "D"));
 
        arrayList.add(2, "X");
        linkedList.add(2, "X");
 
        System.out.println("ArrayList: " + arrayList);
        System.out.println("LinkedList: " + linkedList);
    }
}

ArrayList: [A, B, X, C, D]
LinkedList: [A, B, X, C, D]

두 코드 모두 List 인터페이스의 add(인덱스, 값)를 호출했으므로 최종 결과는 동일하다. 인터페이스가 같은 계약을 강제하기 때문이다. 하지만 내부적으로 일어나는 일은 다르다 — ArrayList는 인덱스 2 이후의 원소들(C, D)을 배열 안에서 한 칸씩 뒤로 밀어야 하고, LinkedList는 인덱스 2에 해당하는 노드를 찾아간 뒤 그 앞뒤 참조만 조정하면 된다. 원소 개수가 많고 삽입 위치가 앞쪽이나 중간일수록 이 차이는 실행 속도로 뚜렷하게 나타난다.

HashSet vs TreeSet: 해시냐 정렬이냐

쉽게 말하면: HashSet은 값을 빠르게 찾기 위해 순서를 포기한 집합이고, TreeSet은 항상 정렬된 순서를 유지하는 대신 약간의 속도를 양보한 집합이다.

HashSet(해시셋)은 각 원소의 hashCode()(해시코드, 객체를 정수로 요약한 값) 값을 이용해 데이터를 저장할 위치를 계산한다. 이 방식 덕분에 특정 값이 집합에 있는지 확인하는 contains() 연산이 원소 개수와 거의 무관하게 빠르다. 그 대가로 원소가 저장되는 순서는 해시값 계산 결과에 좌우되어 예측할 수 없다.

TreeSet(트리셋)은 내부적으로 이진 탐색 트리(binary search tree, 각 노드가 왼쪽 자식보다 크고 오른쪽 자식보다 작은 값을 갖도록 정렬해 저장하는 트리 구조) 계열의 자료구조를 사용해, 원소를 넣는 즉시 정렬된 위치에 자리 잡는다. contains()도 트리를 타고 내려가며 찾으므로 HashSet보다는 느리지만 원소 개수 대비 여전히 효율적이며, 대신 항상 오름차순으로 정렬된 상태를 유지한다는 큰 장점이 있다.

import java.util.*;
 
public class HashSetVsTreeSet {
    public static void main(String[] args) {
        Set<Integer> hashSet = new HashSet<>();
        Set<Integer> treeSet = new TreeSet<>();
        int[] 입력값 = {50, 10, 30, 20, 40};
        for (int v : 입력값) {
            hashSet.add(v);
            treeSet.add(v);
        }
        System.out.println("HashSet: " + hashSet);
        System.out.println("TreeSet: " + treeSet);
        System.out.println("TreeSet 최솟값: " + ((TreeSet<Integer>) treeSet).first());
        System.out.println("TreeSet 최댓값: " + ((TreeSet<Integer>) treeSet).last());
    }
}

HashSet: [50, 20, 40, 10, 30]
TreeSet: [10, 20, 30, 40, 50]
TreeSet 최솟값: 10
TreeSet 최댓값: 50

hashSet은 입력 순서(50, 10, 30, 20, 40)와도 다르고 정렬된 순서와도 다른, 내부 해시 계산에 따른 임의의 순서로 출력된다(정수는 Integer의 hashCode()가 자기 자신의 값을 그대로 반환하지만, 저장 위치는 내부 버킷 배열의 크기에 따라 재배치되므로 겉보기엔 순서가 뒤섞인다). 반면 treeSet은 항상 오름차순으로 정렬되어 있으므로, “가장 작은 값”과 “가장 큰 값”을 트리의 맨 왼쪽·맨 오른쪽 끝에서 바로 얻는 first()/last() 같은 메서드를 추가로 제공한다.

HashMap vs TreeMap: Set의 구분이 Map에도 그대로 적용된다

쉽게 말하면: HashMap과 TreeMap의 차이는 HashSet과 TreeSet의 차이와 완전히 같은 논리이며, 다만 비교와 정렬의 기준이 “값”이 아니라 “키”라는 점만 다르다.

HashMap은 키를 기준으로 해시 테이블에 저장해 get(키)이 매우 빠르고, TreeMap은 키를 기준으로 정렬된 트리에 저장해 항상 키의 오름차순으로 순회할 수 있다.

import java.util.*;
 
public class HashMapVsTreeMap {
    public static void main(String[] args) {
        Map<String, Integer> hashMap = new HashMap<>();
        Map<String, Integer> treeMap = new TreeMap<>();
        String[] 학생 = {"철수", "영희", "민수"};
        int[] 점수 = {80, 95, 70};
        for (int i = 0; i < 학생.length; i++) {
            hashMap.put(학생[i], 점수[i]);
            treeMap.put(학생[i], 점수[i]);
        }
        System.out.println("HashMap: " + hashMap);
        System.out.println("TreeMap: " + treeMap);
    }
}

HashMap: {영희=95, 민수=70, 철수=80}
TreeMap: {민수=70, 영희=95, 철수=80}

hashMap은 입력 순서(철수, 영희, 민수)와 무관한 해시 기반 순서로 출력되지만, treeMap은 키(문자열)를 기준으로 가나다순으로 정렬되어 항상 “민수, 영희, 철수” 순서를 유지한다. 성적표처럼 키 기준 정렬 출력이 필요한 프로그램에는 TreeMap이 자연스러운 선택이다.

”어떤 컬렉션을 쓸까” 판단 흐름

시험에서 자주 나오는 유형은 상황을 문장으로 제시하고 그에 맞는 컬렉션을 고르게 하는 것이다. 다음 판단 순서를 코드와 함께 정리한다.

import java.util.*;
 
public class ScenarioExample {
    public static void main(String[] args) {
        // 시나리오 1: 회원가입 순서대로 이름을 보여주되 중복 가입은 막고 싶다
        Set<String> 회원 = new LinkedHashSet<>();
        회원.add("민수");
        회원.add("영희");
        회원.add("민수");
        System.out.println("회원(가입 순서, 중복 제거): " + 회원);
 
        // 시나리오 2: 학생 이름과 점수를 이름 가나다순으로 항상 출력하고 싶다
        Map<String, Integer> 성적표 = new TreeMap<>();
        성적표.put("철수", 80);
        성적표.put("가영", 95);
        System.out.println("성적표(이름순 정렬): " + 성적표);
 
        // 시나리오 3: 대기열 앞쪽에서 자주 처리하고 중간에 새치기가 잦다
        List<String> 대기열 = new LinkedList<>();
        대기열.add("1번");
        대기열.add(0, "새치기");
        System.out.println("대기열(중간 삽입 잦음): " + 대기열);
    }
}

회원(가입 순서, 중복 제거): [민수, 영희]
성적표(이름순 정렬): {가영=95, 철수=80}
대기열(중간 삽입 잦음): [새치기, 1번]

시나리오 1은 “순서 유지”와 “중복 제거”가 동시에 필요하므로 LinkedHashSet이 정확히 들어맞는다. 시나리오 2는 “항상 정렬된 상태로 조회”가 핵심이므로 TreeMap을 골랐다. 시나리오 3은 “중간 삽입이 잦다”는 조건이 LinkedList를 가리킨다. 이처럼 컬렉션 선택은 정답 하나를 외우는 것이 아니라, 요구사항 문장에서 판단 근거가 되는 단서를 뽑아내는 연습이 핵심이다.

자주 틀리는 점

• ArrayList가 항상 LinkedList보다 빠르다거나 그 반대라고 절대적으로 암기한다. 연산 종류(조회 vs 중간 삽입·삭제)에 따라 유리한 쪽이 다르다.
• HashSet·HashMap의 출력 순서를 예측하려 한다. 이 둘은 순서를 아예 보장하지 않으므로, 출력 순서를 묻는 문제 자체가 이 두 클래스에는 성립하지 않는다(순서가 필요하면 Linked- 또는 Tree- 계열을 써야 한다는 신호다).
• TreeSet·TreeMap이 무조건 더 좋은 선택이라고 생각한다. 정렬 유지에는 비용이 따르므로, 정렬이 필요 없다면 HashSet·HashMap이 더 효율적이다.
• List의 add(인덱스, 값)가 ArrayList와 LinkedList에서 결과(최종 리스트 내용)는 같지만 내부 동작 비용은 다르다는 점을 놓치고, 둘의 최종 출력이 같으니 성능도 같다고 착각한다.

핵심 정리

• ArrayList는 배열 기반으로 인덱스 조회가 빠르고, LinkedList는 노드 연결 기반으로 중간 삽입·삭제가 상대적으로 유리하다. 어느 쪽이 “항상” 빠르다는 절대적 우열은 없다.
• HashSet/HashMap은 해시 기반으로 검색이 빠르지만 순서를 보장하지 않고, TreeSet/TreeMap은 정렬된 순서를 항상 유지하는 대신 상대적으로 더 큰 비용이 든다.
• 입력 순서를 유지하면서 중복만 제거하거나 키 중복만 막고 싶다면 LinkedHashSet/LinkedHashMap이 절충안이 된다.
• 컬렉션 선택은 “중복 허용 여부 → 정렬 필요 여부 → 순서 유지 필요 여부 → 삽입·삭제 위치 패턴” 순서로 요구사항을 따져 판단한다.
• 15편의 인터페이스 계약(무엇을 할 수 있는가)과 이 편의 구현체 특성(어떻게 동작하는가)을 함께 봐야 “이 상황에는 이 컬렉션” 유형 문제를 정확히 풀 수 있다.

마무리 복습

List<Integer> list = new ArrayList<>(List.of(1, 2, 3, 4, 5));
list.add(1, 100);
System.out.println(list);

Map<String, Integer> m = new TreeMap<>();
m.put("다", 3);
m.put("가", 1);
m.put("나", 2);
System.out.println(m);

참고 자료

• Oracle Java Tutorials - Collections Framework 
• 국가평생교육진흥원 독학학위제: https://bdes.nile.or.kr