컬렉션

📖 JCF

JCF란?

Java Collections Framework의 약어로, Java에서 데이터를 저장하는 기본적인 자료구조들을 한 곳에 모아 관리하고 편하게 사용하기 위해서 제공하는 것을 의미한다. 즉, 데이터를 담는 그릇들에 대한 정의를 모아놓은 프레임워크를 의미하며, 값의 성격이나 용도에 따라서 활용 방법에 따라 다양한 컨테이너를 제공한다.

 

JCF의 계층 구조

JCF의 상속 구조는 사용 용도에 따라 List, Set, Queue, Map 4가지로 요약할 수 있다.

 

📖 List 인터페이스

List 인터페이스

순서가 있는 데이터의 집합으로, 데이터의 중복을 허용한다. 구현체로는 LinkedList, Stack, Vector, ArrayList가 있다.

 

ArrayList

내부적으로 배열을 사용해 데이터를 저장하며, 각 요소는 인덱스로 접근할 수 있어 조회 속도가 빠르다. 하지만 중간에 데이터를 삽입하거나 삭제할 경우, 해당 위치 뒤의 모든 요소를 한 칸씩 이동시켜야 하기 때문에 성능이 떨어질 수 있다.

또한, 초기 용량보다 더 많은 데이터를 저장하려면 내부 배열의 크기를 늘리기 위한 새 배열 복사 작업이 발생하여 오버헤드가 생길 수 있다.

 

ArrayList가 동적으로 사이즈를 늘리는 방법

1. 기존 배열의 크기를 기준으로 새로운 배열을 만든다.
2. 기존 배열의 내용을 새로운 배열에 복사한다.
3. 내부 배열 참조를 새 배열로 바꾼다.

LinkedList

양방향 연결 리스트 구조로, 각 노드가 앞뒤 노드의 주소를 함께 저장하고 있다. 이 구조 덕분에 중간에 데이터를 삽입하거나 삭제할 때 배열처럼 데이터를 밀거나 당길 필요 없이 참조만 바꿔주면 되기에 효율적이다.

반면, 데이터를 인덱스로 바로 접근할 수 없기 때문에 조회 성능은 ArrayList보다 떨어지는 단점이 있다.

 

📖 LinkedList vs ArrayList

ArrayList

조회가 많고, 삽입/삭제는 거의 없는 경우 ArrayList를 사용한다.

ex) 게시판 목록, 상품 리스트, 정렬된 데이터 등

 

LinkedList

중간에 데이터 삽입/삭제가 자주 일어나는 경우 LinkedList를 사용한다.

ex) 대기열, 삽입이 잦은 큐 구조

📖 Vector & ArrayList

ArrayList와 Vector는 내부적으로 모두 동적 배열을 기반으로 동작하지만, 스레드 안전성(Thread-Safety) 측면에서 중요한 차이가 있다.

ArrayList는 동기화되지 않아서 멀티스레드 환경에서 데이터 충돌이 발생할 수 있다. 반면 Vector는 모든 메서드에 synchronized가 적용되어 있어 기본적으로 스레드 안전하지만, 이로 인해 성능 저하가 발생할 수 있다.

 

📖 Stack & Queue

Stack

후입선출(LIFO) 구조로, 나중에 넣은 데이터가 먼저 나오는 자료구조

 

Queue

선입선출(FIFO) 구조로, 먼저 넣은 데이터가 먼저 나오는 자료구조

 

📖 Set

Set

중복을 허용하지 않는 데이터의 집합으로, 일반적으로 순서를 보장하지 않는다. 대표적인 구현체로는 HashSet, LinkedHashSet, TreeSet 등이 있다.

 

HashSet

해시 알고리즘을 기반으로 데이터를 저장하며, 가장 빠른 데이터 접근 속도를 자랑한다. 하지만 저장 순서(입력 순서)는 예측할 수 없다. 만약 입력 순서를 유지하고 싶다면 LinkedHashSet을 사용한다.

 

TreeSet

정렬된 상태로 데이터를 저장하는 Set이며, 내부적으로 레드-블랙 트리(Red-Black Tree) 구조로 구현되어 있다. 자동 정렬이 필요한 경우 유용하며, 입력 순서가 아닌 정렬 순서로 데이터를 유지한다.

 

✔️ Set에서 중복 요소를 걸러내는 방법

Set은 내부적으로 요소를 추가할 때, 먼저 그 요소가 기존에 있는지 판단한 뒤에만 저장한다.

1. hashCode()를 호출해 같은 해시값이 있는지 확인한다.
2. 해시값이 같을 경우, equals() 메서드를 사용해 정확히 같은 객체인지 비교한다.

Set<String> set = new HashSet<>();
set.add("A");
set.add("A");  // 중복 → 저장 안 됨
System.out.println(set.size());  // 출력: 1

 

📖 Map

key-value 쌍으로 구성된 데이터의 집합으로, key는 중복이 불가능하고 value는 중복이 가능하다.

대표적인 구현체로는 HashMap, TreeMap, HashTable이 있다.

 

✔️ HashMap 동작 과정

Key에 대해 해시 함수를 적용하여 배열의 인덱스를 계산하고, 그 인덱스에 값을 저장하는 구조이다.

1. put(key, value) 호출
2. key.hashCode() 호출 → 배열의 인덱스 계산
3. 해당 인덱스에 버킷이 비어 있으면 바로 저장
4. 이미 값이 있다면 equals()로 같은 key인지 확인 후, 같으면 덮어쓰고 다르면 충돌 처리

✔️ HashMap의 시간 복잡도

연산	평균 시간 복잡도	최악 시간 복잡도
get(), put()	O(1)	O(n)

 

📖 Iterable & Iterator

자바 컬렉션을 반복할 때 사용하는 인터페이스이다. Iterable은 반복할 수 있는 객체를 뜻하고, Iterator는 실제로 반복을 수행하는 도구이다.

 

Iterable

반복 가능한 객체임을 나타내는 인터페이스

public interface Iterable<T> {
    Iterator<T> iterator();
}

 

Iterator

컬렉션의 요소를 하나씩 꺼내기 위한 반복자로, 반복의 동작을 실제로 수행한다.

public interface Iterator<T> {
    boolean hasNext();   // 다음 요소가 있는지?
    T next();            // 다음 요소 반환
    void remove();       // 현재 요소 제거 (선택적)
}

 

📖 Collection & Collections

Collection Framework

다수의 객체를 다루기 위해 자바에서 제공하는 표준화된 프로그래밍 방식이다. 데이터를 저장하는 자료구조에 따라 List, Set, Map 등의 다양한 인터페이스를 정의하고 있다.

 

Collection

데이터를 모아놓은 집합의 공통 동작을 정의하는 최상위 인터페이스로, List, Set, Queue 등의 상위 인터페이스가 이를 확장한다. Map은 key-value 구조를 다루는 별도의 인터페이스이기 때문에, Collection Framework에는 포함되지만 Collection 인터페이스 계열은 아니다.

public interface Collection<E> extends Iterable<E> {

    int size();

    boolean isEmpty();

    boolean contains(Object o);

    Iterator<E> iterator();

    boolean add(E e);

    boolean remove(Object o);

    // ...생략
}

 

Collections

컬렉션에 대한 여러 연산을 지원하는 유틸성 클래스로서 java.util에 정의되어 있다. Collection 인터페이스와는 다르며, 모든 메서드가 static으로 정의되어 객체 생성 없이 사용할 수 있다.

public class Collections {
    
    public static <T>
    int binarySearch(List<? extends Comparable<? super T>> list, T key) {
        // ...
    }
    
    public static <T extends Comparable<? super T>> void sort(List<T> list) {
        // ...
    }
    
    public static void reverse(List<?> list) {
        // ...
    }
    
    public static final <T> List<T> emptyList() {
        // ...
    }

    public static final <K,V> Map<K,V> emptyMap() {
        return (Map<K,V>) EMPTY_MAP;
    }
    
    // ... 생략
}