10 컬렉션 프레임워크

컬렉션 프레임워크(Collection Framework)

컬렉션 프레임워크는 자바에서 데이터를 효율적으로 저장하고 조작하기 위한 클래스와 인터페이스의 집합입니다. 여러 개의 데이터를 하나의 객체로 다루고, 데이터 추가, 삭제, 정렬, 검색 등의 작업을 쉽게 처리할 수 있도록 다양한 자료구조를 제공합니다.

컬렉션 프레임워크의 의미

• 컬렉션(Collection)

  • 객체의 그룹(모음)을 저장하고 조작하기 위한 인터페이스 또는 클래스를 의미

  • 예: 리스트, 집합(Set), 맵(Map) 등 포함

  • 컬렉션은 데이터의 추가, 삭제, 검색, 순회와 같은 작업을 효율적으로 처리할 수 있도록 설계된 데이터 구조를 제공함

• 프레임워크(Framework)

  • 여러 인터페이스와 클래스를 체계적으로 구조화하고 표준화한 집합

  • 개발자가 컬렉션을 쉽게 사용할 수 있도록 도와주는 일관된 API를 제공

  • 컬렉션 프레임워크는 컬렉션과 관련된 모든 것을 포함하며, 개발자가 데이터 구조를 설계하지 않고도 쉽게 사용할 수 있도록 정의된 일종의 도구 세트

컬렉션 프레임워크의 주요 요소

• 인터페이스(Interfaces): 컬렉션을 다루는 표준 규칙을 정의합니다. 주요 인터페이스로는 Collection, List, Set, Queue, Map 등이 있습니다.

• 구현 클래스(Implementations): 각 인터페이스에 대한 구체적인 구현을 제공합니다. 예를 들어, ArrayList, LinkedList, HashSet, HashMap 등이 있습니다.

• 알고리즘(Algorithms): 컬렉션에 적용할 수 있는 여러 가지 작업을 수행하는 정렬, 검색 등의 메소드를 제공합니다.

컬렉션 프레임워크의 역할

• 표준화된 API 제공

  • 개발자가 다양한 데이터 구조를 동일한 방식으로 다룰 수 있도록 일관된 메서드를 제공함

  • 예: add(), remove(), size() 등

• 다양한 데이터 구조 제공

  • ArrayList, HashSet, HashMap 등 데이터의 저장과 조작에 최적화된 자료구조를 제공함

  • 상황에 따라 적합한 자료구조를 선택해 사용할 수 있음

• 기본 알고리즘 제공

  • 정렬, 검색, 순회 등 자주 사용되는 알고리즘을 기본으로 제공함

• 효율성

  • 성능이 최적화된 자료구조를 제공하며, 개발자가 직접 구현할 필요를 줄여 줌

컬렉션 프레임워크의 주요 인터페이스와 클래스

1. List: 순서가 있는 데이터의 집합으로, 중복된 요소를 허용합니다. 배열과 유사하지만 크기가 동적으로 변합니다.

   • 구현 클래스: ArrayList, LinkedList, Vector, Stack

2. Set: 중복된 요소를 허용하지 않는 집합입니다. 순서가 유지되지 않을 수 있습니다.

   • 구현 클래스: HashSet, LinkedHashSet, TreeSet

3. Map: 키-값 쌍(key-value pair)으로 데이터를 저장하며, 키는 중복을 허용하지 않습니다.

   • 구현 클래스: HashMap, LinkedHashMap, TreeMap, Hashtable

4. Queue: FIFO(First In First Out, 선입선출) 방식으로 요소를 관리합니다.

   • 구현 클래스: LinkedList, PriorityQueue

List

List는 순서가 있는 요소의 집합으로, 중복된 요소를 허용합니다. 인덱스를 사용하여 요소에 접근할 수 있으며, 삽입된 순서를 유지합니다.

특징

• 순서가 유지됩니다.

• 중복된 요소를 허용합니다.

• 요소에 인덱스를 사용하여 접근할 수 있습니다.

구현 클래스

• ArrayList: 동적 배열을 사용하여 요소를 관리합니다. 인덱스를 통한 접근이 빠르지만, 중간 삽입 및 삭제는 느립니다. 가장 많이 사용되는 컬렉션 클래스입니다.

• LinkedList: 이중 연결 리스트 구조로 구현되어 중간 삽입 및 삭제가 빠르지만, 인덱스를 통한 접근은 상대적으로 느립니다. Queue(큐, 선입선출)를 구현하는 용도로 사용 가능하며 기능상 ArrayList와 대다수 주요 기능 공유합니다.

• Vector: ArrayList와 유사하지만, 동기화된 구조를 제공합니다.

• Stack: 후입선출(LIFO) 방식으로 요소를 관리하는 클래스입니다.

List 사용 예시: ArrayList

edu.ch10 패키지

import java.util.ArrayList;
import java.util.List;

public class ListExample {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();

        // 요소 추가
        list.add("Apple");
        list.add("Banana");
        list.add("Orange");
        list.add("Apple");  // 중복된 요소 추가 가능

        // 요소 출력
        for (String item : list) {
            System.out.println(item);
        }
    }
}

출력 결과

Apple
Banana
Orange
Apple

ArrayList 내부 구조

• Java의 ArrayList는 내부적으로 배열을 사용합니다. 배열의 크기가 고정되어 있기 때문에 더 이상 데이터를 저장할 공간이 없으면, 새로운 배열을 생성하고, 기존 데이터를 새 배열로 복사한 후 새로운 데이터를 추가합니다.

• 배열은 연속된 메모리 공간에 데이터를 저장하며, 각 요소에 인덱스(index)를 통해 접근합니다.

1. 장점:

   • 랜덤 액세스(검색)가 빠릅니다. → 인덱스를 사용해 원하는 요소에 바로 접근 가능

   • 데이터 추가 시, 배열이 꽉 차지 않는 한 끝에 데이터를 추가하는 작업은 빠릅니다

2. 단점:

   • 중간에 데이터를 삽입하거나 삭제하려면, 해당 위치 이후의 모든 요소를 이동해야 합니다.

   • 배열의 크기를 초과할 경우, 새로운 배열을 생성하고 기존 데이터를 복사해야 합니다. → 이 작업은 성능에 영향을 줄 수 있습니다.

import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(1); // [1]
        list.add(2); // [1, 2]
        list.add(4); // [1, 2, 4]

        // 중간에 데이터 삽입
        list.add(2, 3); // [1, 2, 3, 4]
        System.out.println(list);
    }
}

• 문제점

  • 3을 삽입하려면, 기존의 4를 오른쪽으로 이동해야 합니다. → 삽입/삭제할수록 이동 비용이 커짐.

배열 크기 초과와 복사

1. 초기 배열 크기

• ArrayList는 처음에 기본 크기(예: 10)의 배열을 생성합니다.

• 예를 들어, 크기가 10인 배열에 데이터를 추가한다고 가정합니다.

ArrayList<Integer> list = new ArrayList<>();

1. 10개 데이터를 추가

• 데이터가 차례대로 추가됩니다.

• 10번째 데이터를 추가할 때까지 아무 문제가 없습니다.

list.add(1); // 배열 내부: [1, _, _, _, _, _, _, _, _, _]
list.add(2); // 배열 내부: [1, 2, _, _, _, _, _, _, _, _]
...
list.add(10); // 배열 내부: [1, 2, 3, ..., 10]

1. 11번째 데이터 추가:

• 배열의 크기가 이미 가득 찼으므로, ArrayList는 새로운 크기의 배열(기본적으로 기존 크기의 1.5~2배)로 확장합니다.

• 기존 데이터를 새로운 배열로 복사한 후, 새 데이터를 추가합니다.

// 내부적으로 다음과 같은 작업이 발생:
// 1. 크기가 증가된 새 배열 생성 (예: 크기 20)
// 2. 기존 배열의 데이터를 새 배열로 복사
// 3. 새로운 배열에 11번째 데이터를 추가

1. 예제 코드

import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>(2); // 초기 크기 2로 설정
        list.add(1);
        list.add(2);

        // 배열 크기가 초과되면, 새로운 배열을 생성하고 데이터를 복사
        list.add(3); // 이 시점에서 크기가 확장되고 복사가 발생
        System.out.println(list); // 출력: [1, 2, 3]
    }
}

List 사용 예시: LinkedList

• LinkedList는 이중 연결 리스트(Double Linked List)를 기반으로 합니다.

• 각 요소는 노드(Node)로 저장되며, 노드는 데이터를 저장하는 필드와 앞/뒤 노드를 가리키는 포인터를 가집니다.

• 데이터가 연속된 메모리 공간에 저장되지 않고, 포인터를 통해 연결됩니다. -> 데이터가 메모리 여기 저기에 저장이되어 있기 때문에 데이터를 추가하면 마지막 데이터와 연결만 시켜주면 됨 -> 중간 추가, 제거시에도 제거 후 앞 뒤 데이터를 연결만 시켜주면 됨

1. 장점:

• 중간 삽입/삭제가 빠릅니다. → 단순히 포인터를 수정하면 되기 때문 (포인터 이동만 필요).

• 배열처럼 크기를 미리 설정할 필요가 없습니다.

1. 단점:

• 랜덤 액세스(검색)가 느립니다. → 특정 요소를 찾으려면 처음부터 순차적으로 탐색해야 함

• 각 노드가 포인터를 저장하므로, 메모리 사용량이 더 많음

예시코드

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        list.add(1); // [1]
        list.add(2); // [1, 2]
        list.add(4); // [1, 2, 4]

        // 중간에 데이터 삽입
        list.add(2, 3); // [1, 2, 3, 4]
        System.out.println(list);
    }
}

ArrayList vs LinkedList

특징	ArrayList	LinkedList
내부 구조	동적 배열	이중 연결 리스트
검색 속도	빠름 (인덱스를 통해 직접 접근)	느림 (순차 탐색 필요)
삽입/삭제 속도	느림 (중간 삽입/삭제 시 요소 이동)	빠름 (포인터 수정만 필요)
메모리 사용량	상대적으로 적음	상대적으로 많음 (포인터 저장 공간 필요)
데이터 추가	끝에 추가는 빠름	끝에 추가도 느림
적합한 용도	랜덤 액세스가 잦은 경우	삽입/삭제가 잦은 경우

실제 사용 예제

1. ArrayList : 검색 중심

import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < 100000; i++) {
            list.add(i); // 끝에 추가
        }

        // 검색 (랜덤 액세스)
        System.out.println(list.get(50000)); // 빠름
    }
}

1. LinkedList : 삽입/삭제 중심

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        for (int i = 0; i < 100000; i++) {
            list.add(i); // 끝에 추가
        }

        // 중간 삽입
        list.add(50000, 99999); // 빠름 (포인터 수정만 필요)
    }
}

Set

Set은 중복을 허용하지 않는 요소의 집합입니다. 순서가 중요하지 않거나 중복 요소를 허용하지 않을 때 사용합니다.

특징

• 중복된 요소를 허용하지 않습니다.

• 요소에 대한 순서가 유지되지 않습니다 (단, 특정 구현 클래스는 순서를 유지할 수 있습니다).

구현 클래스

• HashSet: 해시 테이블을 사용하여 요소를 관리하며, 순서를 보장하지 않습니다. 가장 빠른 검색 성능을 제공합니다.

• LinkedHashSet: HashSet과 비슷하지만, 요소의 삽입 순서를 유지합니다.

• TreeSet: 요소를 정렬된 순서로 저장합니다. 내부적으로 이진 검색 트리를 사용하므로 정렬된 요소가 필요할 때 유용합니다.

주요 클래스	장점	단점
HashSet	성능이 빠르고 메모리 적게 사용	순서 관련 기능 없음 (보장하지 않음)
LinkedHashSet	요소들을 입력 순서대로 정렬 (내부적으로 링크 사용)	HashSet보다는 성능 떨어짐
TreeSet	요소들을 특정 기준대로 정렬 (기본 오름차순)	데이터 추가/삭제에 시간 더 소모

Set 사용 예시

1. HashSet

• 특징:

  • 요소들의 순서가 없다.

  • 중복 요소를 허용하지 않음.

  • 요소들을 해시 테이블(Hash Table) 기반으로 저장하여 검색/삽입 속도가 빠름.

• 장점:

  • 빠른 데이터 접근 속도.

• 단점:

  • 입력된 순서를 보장하지 않음.

edu.ch10 패키지

import java.util.HashSet;
import java.util.Set;

public class SetExample {
    public static void main(String[] args) {
        Set<String> set = new HashSet<>();

        // 요소 추가
        set.add("Apple");
        set.add("Banana");
        set.add("Orange");
        set.add("Apple");  // 중복 요소 추가 시 무시됨

        // 요소 출력
        for (String item : set) {
            System.out.println(item);
        }
    }
}

출력 결과 (순서는 보장되지 않음)

Apple
Banana
Orange

2. LinkedHashSet

• 특징:

  • 요소들의 입력 순서를 유지함.

  • 중복 요소를 허용하지 않음.

  • 해시 테이블과 이중 연결 리스트(Doubly Linked List)를 사용하여 요소를 저장.

• 장점:

  • 순서를 보장하며, 검색/삽입 속도도 비교적 빠름.

• 단점:

  • 메모리 사용량이 다소 많음.

java코드 복사import java.util.LinkedHashSet;

public class LinkedHashSetExample {
    public static void main(String[] args) {
        LinkedHashSet<String> linkedHashSet = new LinkedHashSet<>();
        linkedHashSet.add("Apple");
        linkedHashSet.add("Banana");
        linkedHashSet.add("Cherry");
        linkedHashSet.add("Apple"); // 중복 요소, 추가되지 않음

        System.out.println("LinkedHashSet: " + linkedHashSet); // 입력 순서 유지
    }
}

---

3. TreeSet

• 특징:

  • 요소들을 오름차순으로 정렬하여 저장.

  • 중복 요소를 허용하지 않음.

  • 이진 탐색 트리(Balanced Binary Search Tree) 기반으로 동작.

    15
   /  \
 10    20
/ \   /  \
8 12 17  25

• 장점:

  • 정렬된 상태로 데이터를 유지.

  • 범위 검색 및 정렬된 데이터가 필요할 때 유용.

• 단점:

  • 삽입/삭제 속도가 상대적으로 느림.

  • null 값을 허용하지 않음.

java코드 복사import java.util.TreeSet;

public class TreeSetExample {
    public static void main(String[] args) {
        TreeSet<String> treeSet = new TreeSet<>();
        treeSet.add("Apple");
        treeSet.add("Banana");
        treeSet.add("Cherry");
        treeSet.add("Apple"); // 중복 요소, 추가되지 않음

        System.out.println("TreeSet: " + treeSet); // 정렬된 순서 유지
    }
}

차이점 요약

특징	HashSet	LinkedHashSet	TreeSet
순서 유지	유지하지 않음	입력 순서 유지	정렬된 순서 유지
기본 구조	해시 테이블	해시 테이블 + 연결 리스트	이진 탐색 트리
속도	가장 빠름	빠름	느림
용도	빠른 데이터 접근	순서 보장이 필요한 경우	정렬된 데이터가 필요한 경우

Map

Map은 키-값 쌍(key-value pair)으로 데이터를 저장하는 자료 구조입니다. 키는 중복을 허용하지 않으며, 각 키는 하나의 값에 매핑됩니다. 이는 사전과 비슷한 구조로, 키를 사용하여 빠르게 값을 찾을 수 있습니다.

특징

• 키는 중복을 허용하지 않지만, 값은 중복될 수 있습니다.

• 키와 값이 매핑된 형태로 저장됩니다.

구현 클래스

• HashMap: 해시 테이블을 사용하여 키-값 쌍을 저장합니다. 요소의 순서를 보장하지 않으며, 가장 빠른 검색 성능을 제공합니다.

• LinkedHashMap: 요소의 삽입 순서를 유지하는 HashMap입니다.

• TreeMap: 요소를 키에 따라 정렬된 순서로 저장하며, 내부적으로 이진 검색 트리를 사용합니다.

Map 사용 예시

edu.ch10 패키지

1. HashMap

• 정의: HashMap은 데이터를 키(key)와 값(value) 쌍으로 저장하는 컬렉션으로, 해시 테이블 기반으로 동작합니다.

• 특징:

  • 순서 없음: 키-값 쌍이 저장된 순서가 유지되지 않음.

  • Null 허용: 하나의 null 키와 여러 null 값을 허용.

  • 빠른 검색: 평균적으로 O(1)의 시간 복잡도를 가지며, 효율적인 검색 및 삽입이 가능.

  • 비동기적: 멀티스레드 환경에서 동기화를 직접 처리해야 함.

• 장점:

  • 대량의 데이터에서 빠르게 데이터를 검색/삽입/삭제 가능.

• 단점:

  • 입력된 순서를 보장하지 않음.

  • 충돌(Collision)이 많을 경우 성능 저하 가능.

import java.util.HashMap;
import java.util.Map;

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

        // 키-값 쌍 추가
        map.put("Apple", 3);
        map.put("Banana", 2);
        map.put("Orange", 5);
        map.put("Apple", 4);  // 같은 키로 추가하면 값이 덮어써짐

        // 요소 출력
        for (String key : map.keySet()) {
            System.out.println(key + ": " + map.get(key));
        }
    }
}

출력 결과

Apple: 4
Banana: 2
Orange: 5

2. LinkedHashMap

• 정의: LinkedHashMap은 해시 테이블과 **이중 연결 리스트(Doubly Linked List)**를 조합한 구조로, 키-값 쌍의 입력 순서를 유지합니다.

• 특징:

  • 입력 순서 유지: 데이터를 삽입한 순서대로 저장 및 반환.

  • Null 허용: 하나의 null 키와 여러 null 값을 허용.

  • 해시 테이블의 빠른 성능과 순서 유지를 결합.

  • HashMap보다 약간 더 많은 메모리를 사용.

• 장점:

  • 순서가 필요한 경우 유용.

  • 삽입 순서를 유지하며 데이터를 처리 가능.

• 단점:

  • 메모리 사용량 증가.

  • HashMap보다 약간 느림.

• 예제:

  java코드 복사import java.util.LinkedHashMap;
  
  public class LinkedHashMapExample {
      public static void main(String[] args) {
          LinkedHashMap<String, Integer> linkedHashMap = new LinkedHashMap<>();
          linkedHashMap.put("Apple", 3);
          linkedHashMap.put("Banana", 5);
          linkedHashMap.put("Cherry", 2);
  
          System.out.println("LinkedHashMap: " + linkedHashMap); // 입력 순서 유지
      }
  }

---

3. TreeMap

• 정의: TreeMap은 이진 탐색 트리(Balanced Binary Search Tree) 기반의 구현체로, 키(key)를 정렬된 상태로 유지하며 데이터를 저장합니다.

• 특징:

  • 정렬된 순서 유지: 키 값의 자연 순서(Comparable) 또는 사용자 정의 **정렬 기준(Comparator)**에 따라 정렬.

  • Null 키 불허용: null 키를 허용하지 않음.

  • 검색, 삽입, 삭제의 평균 시간 복잡도는 O(log n).

• 장점:

  • 정렬된 데이터가 필요할 때 유용.

  • 키 범위를 기반으로 데이터 검색 가능.

• 단점:

  • HashMap이나 LinkedHashMap보다 삽입/삭제/검색 속도가 느림.

• 예제:

  java코드 복사import java.util.TreeMap;
  
  public class TreeMapExample {
      public static void main(String[] args) {
          TreeMap<String, Integer> treeMap = new TreeMap<>();
          treeMap.put("Apple", 3);
          treeMap.put("Banana", 5);
          treeMap.put("Cherry", 2);
  
          System.out.println("TreeMap: " + treeMap); // 정렬된 순서 유지
      }
  }

차이점 요약

특징	HashMap	LinkedHashMap	TreeMap
순서 유지	없음	입력 순서 유지	키 값으로 정렬 유지
시간 복잡도	O(1) (평균)	O(1) (평균)	O(log n)
정렬 지원	없음	없음	정렬된 상태 유지
Null 허용	하나의 null 키, 여러 null 값 허용	하나의 null 키, 여러 null 값 허용	null 키 불허, 값은 허용
메모리 사용	상대적으로 적음	해시 테이블 + 연결 리스트로 다소 많음	상대적으로 더 많음
사용 목적	빠른 데이터 검색	순서 보장이 필요할 때	정렬된 데이터가 필요할 때

용도별 추천

1. HashMap: 빠른 검색 및 삽입이 필요한 경우.

2. LinkedHashMap: 삽입 순서를 유지하면서 빠른 성능이 필요한 경우.

3. TreeMap: 정렬된 데이터 또는 키 범위 검색이 필요한 경우.

---

List, Set, Map의 차이점 정리

특성	List	Set	Map
중복 허용	허용	허용하지 않음	키는 허용하지 않음
순서 유지	요소 삽입 순서 유지	순서 유지하지 않음 (LinkedHashSet 예외)	삽입 순서를 유지하지 않음 (LinkedHashMap 예외)
인덱스 접근	가능	불가능	키를 통해 접근 가능
요소 타입	단일 요소	단일 요소	키-값 쌍

Comparable 과 Comparator 추가할지?