자바 컬렉션 프레임워크 - List Set Map 선택 기준과 ArrayList vs LinkedList (자바 중급 12단원)

이 단원에서 배우는 것

11단원의 LoanDesk 는 Map<String, String> 과 Map<String, Integer> 를 쓰고 있었다. 왜 HashMap 인지, TreeMap 이면 뭐가 달라지는지는 설명하지 않았다. 이번 단원이 그 자리다.

컬렉션은 자바에서 가장 많이 쓰는 API고, 동시에 고르는 순간의 판단이 성능과 버그를 결정하는 영역이다. 문법은 열 줄이면 끝나지만 "언제 무엇을 쓸 것인가"는 그렇지 않다. 도서관의 대출 목록, 예약 대기열, 소장 수량을 소재로 한다.

• List / Set / Map 을 요구사항 문장에서 바로 골라낼 수 있다
• ArrayList 와 LinkedList 의 차이를 실제 측정값으로 이해한다
• equals/hashCode 를 안 맞췄을 때 컬렉션에서 무슨 일이 벌어지는지 안다

왜 필요한가

초급 4단원에서 배열의 한계를 봤다. 크기가 고정이라는 것이었다. 대출 목록을 배열로 만들면 이렇게 된다.

String[] loans = new String[10];
int size = 0;

void add(String isbn) {
    if (size == loans.length) {
        loans = Arrays.copyOf(loans, loans.length * 2);   // 직접 늘려야 한다
    }
    loans[size++] = isbn;
}

void removeAt(int index) {
    for (int i = index; i < size - 1; i++) loans[i] = loans[i + 1];   // 직접 당겨야 한다
    loans[--size] = null;
}

크기 관리, 삽입/삭제 시 원소 이동, 중복 검사, 정렬을 전부 직접 짜야 하고 그 과정에서 off-by-one 버그가 난다. 컬렉션 프레임워크는 이걸 대신해주는 라이브러리지만, 진짜 가치는 그게 아니다. 인터페이스(List, Set, Map)와 구현(ArrayList, HashSet, TreeMap)이 분리되어 있어서, 요구사항이 바뀌면 new 하는 한 줄만 바꾸면 된다는 점이다. 10단원에서 배운 인터페이스 설계의 실제 사례다.

List<String> loans = new ArrayList<>();    // 구현을 바꿔도 아래 코드는 그대로

문법과 예제

셋 중 무엇을 고를 것인가

요구사항 문장에서 다음 단어를 찾으면 답이 거의 정해진다.

요구사항에 나오는 말	고를 것	도서관 예
"빌린 순서대로", "몇 번째"	List	회원의 대출 이력
"중복 없이", "이미 있는지"	Set	최근 조회한 자료 목록
"~별", "~로 찾기", "~에 대응하는"	Map	등록번호별 대출자

그 다음 구현을 고른다.

인터페이스	구현	특징	고르는 이유
List	ArrayList	내부가 배열. 인덱스 접근 O(1)	기본값. 고민되면 이것
List	LinkedList	양방향 연결. 앞뒤 삽입/삭제 O(1)	사실상 ArrayDeque 로 대체된다
Set	HashSet	순서 없음. 조회 O(1)	중복만 막으면 될 때
Set	LinkedHashSet	넣은 순서 유지	중복 제거 + 순서 보존
Set	TreeSet	정렬 상태 유지. O(log n)	항상 정렬된 채로 필요할 때
Map	HashMap	순서 없음. 조회 O(1)	기본값
Map	LinkedHashMap	넣은 순서 유지	출력 순서가 중요할 때
Map	TreeMap	키 정렬 유지	범위 조회, 가나다순 출력
Queue/Deque	ArrayDeque	앞뒤 넣고 빼기 O(1)	예약 대기열

import java.util.*;

public class CollectionChoiceDemo {
    public static void main(String[] args) {
        // 최근 조회한 자료 — 순서 유지 + 중복 제거
        Set<String> recent = new LinkedHashSet<>();
        recent.add("자바의 정석");
        recent.add("매트릭스");
        recent.add("자바의 정석");          // 다시 조회해도 하나만 남는다
        System.out.println(recent);

        // 예약 대기열 — 먼저 예약한 사람이 먼저
        Deque<String> waiting = new ArrayDeque<>();
        waiting.addLast("M-01");
        waiting.addLast("M-02");
        waiting.addLast("M-03");
        System.out.println("다음 차례 " + waiting.pollFirst() + " / 남은 대기 " + waiting);

        // 분류 목록 — 가나다순 출력이 필요하면 TreeMap
        Map<String, Integer> counts = new LinkedHashMap<>();
        counts.put("영상", 1);
        counts.put("과학", 2);
        counts.put("컴퓨터", 3);
        System.out.println("LinkedHashMap=" + counts);
        System.out.println("TreeMap=" + new TreeMap<>(counts));
    }
}

[자바의 정석, 매트릭스]
다음 차례 M-01 / 남은 대기 [M-02, M-03]
LinkedHashMap={영상=1, 과학=2, 컴퓨터=3}
TreeMap={과학=2, 영상=1, 컴퓨터=3}

ArrayList vs LinkedList — 실제로 재보면

"중간 삽입이 많으면 LinkedList"라는 말을 자주 듣는다. 반은 맞고 반은 틀리다. 원소 10만 개로 Java 17에서 직접 재본 결과다.

import java.util.*;

public class ListBenchmark {
    public static void main(String[] args) {
        int n = 100_000;
        List<Integer> al = new ArrayList<>();
        List<Integer> ll = new LinkedList<>();
        for (int i = 0; i < n; i++) { al.add(i); ll.add(i); }

        long t = System.nanoTime();
        long s = 0;
        for (int i = 0; i < n; i++) s += al.get(i);
        System.out.println("ArrayList  get(i) 순회 : " + (System.nanoTime() - t) / 1_000_000 + "ms");

        t = System.nanoTime();
        s = 0;
        for (int i = 0; i < n; i++) s += ll.get(i);
        System.out.println("LinkedList get(i) 순회 : " + (System.nanoTime() - t) / 1_000_000 + "ms");

        t = System.nanoTime();
        s = 0;
        for (int v : ll) s += v;
        System.out.println("LinkedList for-each    : " + (System.nanoTime() - t) / 1_000_000 + "ms");

        List<Integer> al2 = new ArrayList<>();
        t = System.nanoTime();
        for (int i = 0; i < n; i++) al2.add(0, i);
        System.out.println("ArrayList  맨앞 삽입   : " + (System.nanoTime() - t) / 1_000_000 + "ms");

        List<Integer> ll2 = new LinkedList<>();
        t = System.nanoTime();
        for (int i = 0; i < n; i++) ll2.add(0, i);
        System.out.println("LinkedList 맨앞 삽입   : " + (System.nanoTime() - t) / 1_000_000 + "ms");
    }
}

ArrayList  get(i) 순회 : 1ms
LinkedList get(i) 순회 : 4572ms
LinkedList for-each    : 3ms
ArrayList  맨앞 삽입   : 463ms
LinkedList 맨앞 삽입   : 4ms

읽을 것이 많다.

• LinkedList 에 get(i) 로 순회하면 4.5초. get(i) 마다 앞에서부터 노드를 따라가므로 전체가 O(n²)이 된다. ArrayList 대비 4500배다. 실무에서 리스트 타입만 바꿨다가 화면 응답이 수 초로 늘어나는 사고가 실제로 이 지점에서 난다.
• 같은 LinkedList 라도 for-each(내부적으로 Iterator)로 돌면 3ms다. 자료구조가 아니라 접근 방식이 문제였다.
• 맨 앞 삽입은 LinkedList 가 100배 이상 빠르다. 이건 사실이다. 다만 이런 패턴이 정말 필요하다면 ArrayDeque 가 LinkedList 보다 대체로 더 빠르고 메모리도 덜 쓴다.
• 중간 삽입은 LinkedList 도 빠르지 않다. 노드 연결 자체는 O(1)이지만 그 위치까지 가는 데 O(n)이 든다. ListIterator 로 순회하면서 삽입하는 게 아닌 한 이득이 없다.

결론: 기본은 ArrayList. 예약 대기열처럼 앞뒤로 넣고 빼야 하면 ArrayDeque. LinkedList 를 골라야 할 상황은 실무에서 생각보다 드물다.

Map 을 제대로 쓰기

소장 수량 관리를 Map 으로 짤 때 초보 코드와 실무 코드가 확실히 갈린다.

import java.util.*;

public class StockDemo {
    public static void main(String[] args) {
        Map<String, Integer> stock = new HashMap<>();

        // 초보 코드
        if (stock.containsKey("B-001")) {
            stock.put("B-001", stock.get("B-001") + 3);
        } else {
            stock.put("B-001", 3);
        }

        // 실무 코드 — 해시 조회가 한 번이고 의도가 드러난다
        stock.merge("B-001", 2, Integer::sum);

        System.out.println(stock);                                // {B-001=5}
        System.out.println(stock.getOrDefault("D-014", 0));       // 0 (null 아님)

        // 값이 리스트인 Map — 분류별 자료 목록
        Map<String, List<String>> byCategory = new LinkedHashMap<>();
        byCategory.computeIfAbsent("컴퓨터", k -> new ArrayList<>()).add("자바의 정석");
        byCategory.computeIfAbsent("컴퓨터", k -> new ArrayList<>()).add("이펙티브 자바");
        byCategory.computeIfAbsent("영상",   k -> new ArrayList<>()).add("매트릭스");
        System.out.println(byCategory);

        for (Map.Entry<String, List<String>> e : byCategory.entrySet()) {
            System.out.println(e.getKey() + " : " + e.getValue().size() + "종");
        }
    }
}

{B-001=5}
0
{컴퓨터=[자바의 정석, 이펙티브 자바], 영상=[매트릭스]}
컴퓨터 : 2종
영상 : 1종

keySet() 을 돌면서 get() 을 부르는 코드를 자주 보는데, 해시 조회를 두 번 한다. 키와 값이 둘 다 필요하면 entrySet() 을 쓴다.

equals / hashCode — 컬렉션의 전제 조건

9단원에서 equals 오버로딩 실수를 봤다. 컬렉션 관점에서 다시 본다. HashSet 과 HashMap 은 원소를 찾을 때 먼저 hashCode() 로 버킷을 고르고, 그 안에서 equals() 로 비교한다. 그래서 둘 다 맞춰야 한다.

import java.util.Objects;

public class Book {
    private final String isbn;
    private final String title;

    public Book(String isbn, String title) { this.isbn = isbn; this.title = title; }

    public String isbn() { return isbn; }
    public String title() { return title; }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Book other)) return false;    // Java 16+ 패턴 매칭
        return isbn.equals(other.isbn);                  // 동일성 판단 기준은 등록번호
    }

    @Override
    public int hashCode() { return Objects.hash(isbn); }  // equals 와 같은 필드로

    @Override
    public String toString() { return title; }
}

Set<Book> set = new HashSet<>();
set.add(new Book("B-001", "자바의 정석"));
set.add(new Book("B-001", "자바의 정석 3판"));
System.out.println("size=" + set.size() + " " + set);

size=1 [자바의 정석]

hashCode() 를 지우면 위 결과가 size=2 가 된다. 두 객체의 해시가 달라 아예 다른 버킷으로 들어가고 equals() 는 호출조차 되지 않기 때문이다.

실무에서 자주 틀리는 것

1. for-each 중에 원소를 지운다 — 그런데 예외가 안 날 때도 있다

이건 예외가 나는 것보다 안 나는 경우가 더 무섭다.

import java.util.*;

public class CmeDemo {
    static void tryReturn(String target) {
        List<String> loans = new ArrayList<>(List.of("B-001", "B-002", "B-003"));
        try {
            for (String isbn : loans) if (isbn.equals(target)) loans.remove(isbn);
            System.out.println(target + " 반납 -> 예외 없음, 결과 " + loans);
        } catch (ConcurrentModificationException e) {
            System.out.println(target + " 반납 -> ConcurrentModificationException");
        }
    }
    public static void main(String[] args) {
        tryReturn("B-001"); tryReturn("B-002"); tryReturn("B-003");
    }
}

B-001 반납 -> ConcurrentModificationException
B-002 반납 -> 예외 없음, 결과 [B-001, B-003]
B-003 반납 -> ConcurrentModificationException

끝에서 두 번째 원소를 지울 때만 예외가 나지 않는다. Iterator 의 hasNext() 가 cursor != size 로만 판단하는데, 지우고 나면 cursor 와 줄어든 size 가 우연히 같아져 반복문이 조용히 끝나버리기 때문이다. 남은 원소를 건너뛴 채로. 테스트 데이터로는 통과하고 운영 데이터에서만 터지는 전형적인 버그다. 지울 때는 removeIf 나 Iterator.remove() 를 쓴다.

loans.removeIf(isbn -> isbn.equals("B-002"));   // 가장 간단

Iterator<String> it = loans.iterator();          // 조건이 복잡할 때
while (it.hasNext()) {
    if (it.next().startsWith("D-")) it.remove();
}

2. List.of() 와 Arrays.asList() 를 수정 가능한 리스트로 안다

List<String> a = List.of("B-001");
a.add("B-002");                 // UnsupportedOperationException — 완전 불변

List<String> b = Arrays.asList("B-001", "B-002");
b.add("B-003");                 // UnsupportedOperationException — 크기 고정
b.set(0, "B-009");              // 이건 된다. 원본 배열을 수정한다

List<String> c = new ArrayList<>(List.of("B-001", "B-002"));   // 수정하려면 이렇게
c.add("B-003");                 // OK

List.of() 는 완전 불변이라 set() 도 안 되고 null 원소도 못 넣는다. Arrays.asList() 는 배열을 감싼 뷰라서 크기만 고정이고 set() 은 된다. 둘의 차이를 모르고 쓰다가 운영에서 UnsupportedOperationException 을 만난다.

3. List<Integer>.remove() 의 오버로딩 함정

List<Integer> nums = new ArrayList<>(List.of(10, 20, 30));

nums.remove(Integer.valueOf(20));   // 값 20 을 지운다  -> [10, 30]
nums.remove(0);                     // 인덱스 0 을 지운다 -> [30]

List 에는 remove(int index) 와 remove(Object o) 가 둘 다 있다. List<Integer> 에서 remove(20) 이라고 쓰면 오버로딩 규칙상 int 쪽이 선택되어 인덱스 20 을 지우려 하고, 크기가 작으면 IndexOutOfBoundsException 이 난다. 값을 지우려면 Integer.valueOf() 로 감싼다. 회원번호나 자료 ID를 Integer 로 다루는 코드에서 실제로 자주 걸린다.

4. HashMap 의 키로 가변 객체를 쓴다

class MutableKey {
    String isbn;
    MutableKey(String isbn) { this.isbn = isbn; }
    @Override public boolean equals(Object o) {
        return o instanceof MutableKey k && isbn.equals(k.isbn);
    }
    @Override public int hashCode() { return isbn.hashCode(); }
}

Map<MutableKey, Integer> map = new HashMap<>();
MutableKey key = new MutableKey("B-001");
map.put(key, 5);
key.isbn = "B-999";                // 키의 상태를 바꿨다
System.out.println(map.get(key));  // null — 넣어둔 값을 못 찾는다

put 시점의 해시로 버킷에 넣었는데 해시의 근거가 되는 필드가 바뀌면 다른 버킷을 뒤지게 된다. 값은 맵 안에 남아 있는데 get 으로도 remove 로도 꺼낼 수 없는 상태가 된다. 키로 쓸 객체의 equals/hashCode 근거 필드는 반드시 final 로 만든다. 위 Book 의 isbn 이 final 인 이유가 이것이다.

스스로 확인하기

1. 다음 요구사항 각각에 맞는 컬렉션 구현을 하나씩 고르고 이유를 쓴다. (가) 회원이 최근 조회한 자료 20건을 조회한 순서대로, 같은 자료는 한 번만 보여준다. (나) 관리자 화면에서 분류명을 가나다순으로 정렬해 출력한다. (다) 인기 자료 예약자를 예약한 순서대로 한 명씩 꺼내 알림을 보낸다.
2. 아래 코드의 출력은?

   List<String> list = new ArrayList<>(List.of("a", "b", "c", "d"));
   for (String s : list) {
       if (s.equals("c")) list.remove(s);
   }
   System.out.println(list);

3. Book 클래스에서 equals() 는 재정의했는데 hashCode() 를 빠뜨렸다. List.contains() 와 HashSet.contains() 중 어느 쪽이 정상 동작하고 어느 쪽이 실패하는가. 이유는?

정답

1. (가) LinkedHashSet. 중복 제거와 삽입 순서 유지가 동시에 필요하다. (나) TreeMap 또는 TreeSet. 매번 정렬하지 않고 항상 정렬 상태를 유지한다. 다만 분류가 몇십 개뿐이고 출력 직전에만 정렬이 필요하다면 List 에 담아 sort() 하는 편이 단순하다. (다) ArrayDeque. FIFO 큐로 쓰기에 LinkedList 보다 빠르고 메모리를 덜 쓴다.
2. [a, b, d] 가 출력되고 예외는 나지 않는다. "c"는 끝에서 두 번째 원소라서 지운 뒤 cursor(3)와 size(3)가 같아져 hasNext() 가 false 를 반환하고 반복이 조용히 끝난다. 결과는 맞아 보이지만 "d"는 검사되지 않았다. 이 코드가 우연히 동작한다는 사실이 더 위험하다.
3. List.contains() 는 정상 동작하고 HashSet.contains() 는 실패한다. List 는 원소를 앞에서부터 equals() 로만 비교하지만, HashSet 은 hashCode() 로 버킷을 먼저 고른다. hashCode() 를 재정의하지 않으면 Object 의 기본 구현(객체마다 다른 값)이 쓰여 다른 버킷을 뒤지고, equals() 는 호출조차 되지 않는다.