[JAVA] 컬렉션 프레임워크

1. 컬렉션(Collection)이란?

자바에서 컬렉션(Collection) 은 자료구조를 객체화해서 데이터를 효율적으로 저장, 검색, 관리할 수 있게 해주는 프레임워크입니다.

데이터를 배열처럼 모아두고 조작할 수 있지만 배열과 달리 동적으로 변경하는 것도 가능합니다.

다만 컬렉션은 기본자료형에서는 사용이 불가능하고 객체로 만들어서 사용해야합니다.

 

2. 장단점

1) 장점

컬렉션은 동적으로 변경하는 것이 가능하기 때문에 배열보다 유연하게 사용가능합니다. 또한 컬렉션의 종류에는 List, Set, Map, Queue등 다양한 자료구조가 있으며 add, remove,contains, sort 등 API도 많기 때문에 여러가지 상황에 맞춰서 사용이 가능합니다. 또한 제네릭과 함께 사용하기 때문에 타입 안정성도 있습니다.

2) 단점

아무래도 객체기반이다보니 기본 자료형이나 배열보다 메모리사용량이 많습니다. 그래서 단순반복 연산에는 불리합니다. 

3. 종류

1)  LIST 계열

먼저 리스트 계열에는 ArrayList, LinkedList, Vector 등이 있습니다.

 

ArrayList는 배열기반이기 때문에 배열의 장단점을 그대로 가지고 있습니다. 즉, 순서가 유지되고 인덱스를 사용하면 빠르게 접근이 가능하지만, 중간 삽입이나 삭제시 요소가 이동하기 때문에 느립니다. 따라서 접근의 시간복잡도는 O(1)이지만, 삽입, 삭제의 시간복잡도는 O(n)이 됩니다.

 

LinkedList는 연결리스트 기반입니다. 따라서 연결리스트의 장단점을 그대로 가지고 있습니다. 연결리스트는 다음 요소의 주소를 가지고 있기 때문에, 배열과 반대로 탐색은 오래 걸리지만, 삽입, 삭제는 매우 빠릅니다. 따라서 탐색의 시간복잡도는 O(n)이며 삽입, 삭제의 시간복잡도도 O(n)이지만, 조금 더 빠릅니다. 왜냐하면 삽입, 삭제할때도 탐색을 한 후 삽입이나 삭제를 하기 때문입니다. 당연히 연결리스트 기반이기 때문에 헤드와 테일은 시간복잡도는 O(1)이 됩니다.

 

Vector 도 배열기반입니다. 다만 ArrayList와 달리 동기화가 되어있습니다. 따라서 단일스레드에서는 불리하지만 멀티스레드에서는 안전하게 사용할 수 있습니다. 배열기반이기 때문에 시간복잡도는 ArrayList와 동일합니다.

 

import java.util.Scanner;
import java.util.*;

public class Solution {
    public static void main(String[] args) {
        // ArrayList
        List<String> arrayList = new ArrayList<>();
        arrayList.add("a");
        arrayList.add("b");
        System.out.println("ArrayList: " + arrayList); // ArrayList: [a, b]
        arrayList.remove("b");
        System.out.println("ArrayList: " + arrayList); // ArrayList: [a]
        arrayList.addFirst("c"); //첫번째 값에 c를 삽입
        System.out.println("ArrayList: " + arrayList); // ArrayList: [c, a]
        arrayList.clear();
        System.out.println("ArrayList: " + arrayList); // ArrayList: []

        // LinkedList
        List<String> linkedList = new LinkedList<>();
        linkedList.add("a");
        linkedList.add("b");
        System.out.println("LinkedList: " + linkedList); // LinkedList: [a, b]
        linkedList.remove("b");
        System.out.println("LinkedList: " + linkedList); // LinkedList: [a]
        linkedList.addFirst("c");
        System.out.println("LinkedList: " + linkedList); // LinkedList: [c, a]
        linkedList.clear();
        System.out.println("LinkedList: " + linkedList); // LinkedList: []


        // Vector
        List<String> vector = new Vector<>();
        vector.add("a");
        vector.add("b");
        System.out.println("Vector: " + vector); // Vector: [a, b]
        vector.remove("a");
        System.out.println("Vector: " + vector); // Vector: [b]
        vector.addFirst("c");
        System.out.println("Vector: " + vector); // Vector: [c, b]
        vector.clear();
        System.out.println("Vector: " + vector); // Vector: []

    }
}

 

2) SET 계열

셋 계열에는 HashSet, LinkedHashSet, TreeSet이 있습니다. 셋의 특징은 중복값을 저장할 수 없다는 것입니다.

 

HashSet은 해시테이블 기반이며 순서가 없다는 특징이 있습니다. HashSet의 시간복잡도는 탐색, 삽입, 삭제 시 평균은 O(1)이지만 최악일때는 O(n)이 됩니다.

 

LinkedHashSet은 해시테이블에 이중연결리스트 자료 구조를 더했습니다. 이에 따라 삽입순서가 유지된다는 특징이 있습니다. HashSet과 시간복잡도는 동일합니다.

 

TreeSet은 레드-블랙 트리 기반입니다. 따라서 자동으로 정렬된다는 특징이 있습니다. 트리의 특징을 가지고 있기 때문에 탐색, 삽입, 삭제의 시간복잡도는 O(log n)이 됩니다.

 

import java.util.Scanner;
import java.util.*;

public class Solution {
    public static void main(String[] args) {
        // HashSet
        Set<String> hashSet = new HashSet<>();
        hashSet.add("Apple");
        hashSet.add("Banana");
        hashSet.add("Apple"); // 중복 무시
        System.out.println("HashSet: " + hashSet); // HashSet: [Apple, Banana]
        hashSet.remove("Apple");
        System.out.println("HashSet: " + hashSet); // HashSet: [Banana]
        System.out.println(hashSet.size()); // 1
        System.out.println(hashSet.contains("Banana")); // true
        

        // LinkedHashSet
        Set<String> linkedHashSet = new LinkedHashSet<>();
        linkedHashSet.add("Apple");
        linkedHashSet.add("Banana");
        linkedHashSet.add("Apple"); // 중복 무시
        System.out.println("LinkedHashSet: " + linkedHashSet); // LinkedHashSet: [Apple, Banana]
        linkedHashSet.remove("Apple");
        System.out.println("LinkedHashSet: " + linkedHashSet); // LinkedHashSet: [Banana]
        System.out.println(linkedHashSet.size()); // 1
        System.out.println(linkedHashSet.contains("Apple")); // false

        // TreeSet
        Set<String> treeSet = new TreeSet<>();
        treeSet.add("Banana");
        treeSet.add("Apple");
        treeSet.add("Cherry");
        System.out.println("TreeSet: " + treeSet); // 자동 정렬 -> TreeSet: [Apple, Banana, Cherry]
        treeSet.remove("Banana");
        System.out.println("TreeSet: " + treeSet); // TreeSet: [Apple, Cherry]
        System.out.println(treeSet.size()); // 2
        System.out.println(treeSet.contains("Cherry")); // true
    }
}

 

3) Map 계열

map 계열에는 HashMap, LinkedHashMap, TreeMap등이 있습니다. map은 key와 value로 되어있습니다. 따라서 key만 알면 빠른 탐색이 가능합니다. 

 

HashMap은 해시테이블 기반입니다. 삽입시 요소의 순서를 고려하지않습니다. 탐색, 삽입, 삭제 모두 O(1)의 평균 시간복잡도를 가집니다.

 

LinkedHashMap은 해시테이블에 연결리스트를 더한 구조입니다. 따라서 삽입순서를 유지합니다. LinkedHashMap의 시간복잡도는 HashMap보다는 느리지만 그래도 평균 O(1)의 시간복잡도를 가집니다.

 

TreeMap은 레드-블랙 트린 기반입니다. 따라서 내부적으로 키 정렬을 유지합니다. 이에 대한 특징으로 범위탐색에 유리합니다.

TreeMap의 시간복잡도는 O(log n)입니다. 

import java.util.Scanner;
import java.util.*;

public class Solution {
    public static void main(String[] args) {
        // HashMap
        Map<String, Integer> hashMap = new HashMap<>();
        hashMap.put("Alice", 25);
        hashMap.put("Bob", 30);
        System.out.println("HashMap: " + hashMap); // HashMap: {Bob=30, Alice=25}
        System.out.println(hashMap.get("Alice")); // 25
        System.out.println("hashMap-keySet "+hashMap.keySet()); // hashMap-keySet [Bob, Alice]
        boolean hasBob = hashMap.containsKey("Bob");
        System.out.println("hasBob: " + hasBob); // hasBob: true

        // LinkedHashMap
        Map<String, Integer> linkedMap = new LinkedHashMap<>();
        linkedMap.put("Alice", 25);
        linkedMap.put("Bob", 30);
        System.out.println("LinkedHashMap: " + linkedMap); // LinkedHashMap: {Alice=25, Bob=30}
        System.out.println(linkedMap.get("Bob")); // 30
        System.out.println(linkedMap.values()); // [25, 30]
        System.out.println("linkedMap entrySet "+linkedMap.entrySet()); // linkedMap entrySet [Alice=25, Bob=30]

        // TreeMap
        Map<String, Integer> treeMap = new TreeMap<>();
        treeMap.put("Bob", 30);
        treeMap.put("Alice", 25);
        System.out.println("TreeMap: " + treeMap); // 키 정렬 -> TreeMap: {Alice=25, Bob=30}
        System.out.println(treeMap.containsKey(("Alice"))); // true
        treeMap.putIfAbsent("kal", 55);
        System.out.println("TreeMap: " + treeMap); // TreeMap: {Alice=25, Bob=30, kal=55}

    }
}