[Java] 17.5. Collection

1. 컬렉션

1. 컬렉션이란

1. 자료를 저장하기 위한 자료구조

2. 제네릭 기법으로 구현되어 있기 때문에 어떠한 타입의 데이터도 저장할 수 있다.

3. CRUD
1. 추가
2. 삭제
3. 검색
4. 수정

2. 컬렉션의 종류

1. 자바는 컬렉션 인터페이스와 컬렉션 클래스를 제공한다.

2. 컬렉션 인터페이스 계층 구조

                             ┌─────── Java ───────┐                     
                             │                    │                   
                          Collection             Map  



          ┌────────── Collection (인터페이스) ──────────────┐
          │                                                │
    ┌─────── List ───────┐                     ┌────────── Set ────────────────┐
    │                    │                     │                │              │
 ArrayList           LinkedList          HashSet          LinkedHashSet     TreeSet
				                              
     
     
                ┌──────────── Map (인터페이스) ─────────────┐
                │                   │                      │
           HashMap            LinkedHashMap              TreeMap
           

3. 컬렉션의 특징

1. 제네릭 사용

2. 기초 자료형 저장 불가능. 클래스(참조 자료형)만 가능.

3. 기초 자료형으로 저장하면 자동으로 wrapper 클래스의 객체로 변환(auto boxing)

4. 컬렉션 인터페이스의 주요 메서드

1. add()

2. addAll()

3. remove()

4. removeAll()

5. retainAll()

6. clear()

7. isEmpty()

8. contains()

9. containsAll()

10. size()

5. 컬렉션의 모든 요소 방문하기

String[] a = new String[] {"A", "B", "C", "D", "E"};
List<String> list = Arrays.asList(a);

1. for문

for(int i = 0; i < list.size(); i++){
    System.out.println(list.get(i));
}

2. for - each문

for (String s: list){
    System.out.println(s)
}

3. 반복자(Iterator)
1. 목적 : 특별한 타입의 객체로 컬렉션의 원소들을 접근
2. Iterator 인터페이스를 구현하는 객체
3. 메서드
1. hasNext() : 아직 방문하지 않은 원소가 있으면 true 리턴
2. next() : 다음 원소 리턴
3. remove() : 최근에 반환된 원소 삭제
4. ArrayList의 iterator() 메서드 호출 → iterator 객체 생성 → hasNext()와 next()를 통해 컬렉션의 각 원소들을 접근

String s;
Iterator e = list.iterator();
while(e.hasNext()){
    s = (String) e.next(); // 반복자는 Object 타입을 반환한다.
    System.out.println(s);
}

4. Stream 라이브러리 - forEach 메서드와 람다식

list.forEach((n) -> System.out.println(n));

2. List

1. ArrayList

1. 가변 크기의 배열을 구현하는 클래스

2. 동기화를 하지 않는다.

3. 메서드
1. add(value) : 데이터 저장
1. add(index,value) : 기존 데이터가 들어 있는 위치를 지정하면 새로운 데이터는 중간에 삽입된다.
2. set(index, value) : 특정한 위치에 있는 원소 수정
3. remove(index) : 데이터 삭제
4. get(index) : 인덱스를 받아서 그 위치에 저장된 원소 반환
5. size() : 저장된 원소의 개수 반환
❗
배열의 크기 vs 문자열의 크기 vs ArrayList의 크기
배열 : array.length
문자열 : string.length()
ArrayList : arrayList.size()
6. contains() : 어떤 값이 리스트에 포함되어 있는지를 검사

4. 배열을 리스트로 변경하기
1. Arrays.asList() : 배열을 받아서 리스트 형태로 반환
2. 예제 - 객체를 ArrayList에 저장하기

package ex17.collection;

import java.util.ArrayList;

class Point {
    int x;
    int y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    // 재정의
    public String toString() {
        return "(" + x + ", " + y + ")";
    }
}

public class ArrayListTest {
    public static void main(String[] args) {
        ArrayList<Point> list = new ArrayList();
        list.toString();
        list.add(new Point(0, 0)); // 새로운 Point 객체 만들어서 list에 삽입
        list.add(new Point(4, 0));
        list.add(new Point(3, 5));
        list.add(new Point(-1, 3));
        list.add(new Point(13, 2));

        System.out.println(list);
    }
}



❗
list는 왜 바로 sout으로 출력 가능할까? (vs 배열)
 
ArrayList는 toString() 메서드가 오버라이딩되어 있어서 리스트 내부의 모든 요소가 자동으로 문자열로 변환되어 출력된다.
println() → valueOf() → toString()
배열은 toString() 이 재정의되어 있지 않기 때문에 System.out.println()를 호출하면 메모리 주소가 출력되므로 for문을 통해 직접적으로 원소를 방문해서 출력해야한다.
3. 예제 - 문자열을 ArrayList에 저장하기

package ex17.collection;

import java.util.ArrayList;

public class ArrayListTest2 {
    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList();
        list.add("Apple");
        list.add("Banana");
        list.add("Mango");
        list.add("Pear");
        list.add("Grape");

        int index = list.indexOf("Mango");

        System.out.println("망고의 위치: " + index);
    }
}

2. LinkedList

1. ArrayList의 중간에서 데이터의 삽입이나 삭제가 빈번하게 발생하는 경우 삽입이나 삭제 위치 뒤에 있는 원소들을 이동해야 됨 → 연결 리스트로 구현된 LinkedList 사용 추천!

2. 연결 리스트는 각 원소를 링크로 연결

3. 각 원소들은 다음 원소를 가리키는 링크를 저장

4. 삽입/ 삭제 시 그 위치 바로 앞에 있는 원소의 링크값만 변경

5. 위치(인덱스)를 가지고 원소를 접근하는 연산(위치적인 접근이 많다) : ArrayList가 낫다

6. 메서드
1. add(index, value)
2. addFirst(value)
3. addLast(value)
4. get(index)
5. getFirst()
6. getLast()
7. set(index, value)
8. peek()
9. size()

7. 예제

package ex17.collection;

import java.util.LinkedList;

public class LinkedListTest {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList();

        list.add("MILK");
        list.add("BREAD");
        list.add("BUTTER");
        list.add(1, "APPLE");
        list.set(2, "GRAPE");
        list.remove(3);
        //예상 - MILK APPLE GRAPE

        // System.out.println(list);
        // 문자열만 출력
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i) + " ");
        }
    }
}

3. ArrayList VS LinkedList

1. ArrayList
1. 인덱스를 가지고 원소에 접근할 경우, 항상 일정 시간만 소요
2. 리스트의 각각의 원소를 위해 노드 객체에 접근할 필요 없음
3. 동시에 많은 원소를 이동해야 하는 경우, System.arraycopy() 사용
4. 일반적으로 빠르다
5. 한 가지 튜닝 매개 변수(초기 용량(initial capacity))를 가진다
1. ArrayList는 배열 사용해서 데이터 저장 후 원소 추가 시 배열이 가득 차면 새 배열 만들고 기존 데이터를 복사하는 과정이 발생한다. (Resizing)
2. 초기 용량 : ArrayList가 저장할 수 있는 원소의 개수

2. LinkedList
1. 노드 기반 자료구조
2. 리스트의 처음에 빈번하게 원소를 추가하거나 내부의 원소 삭제를 반복하는 경우, 일정 시간만 소요 (↔ ArrayList : 원소의 개수에 비례)
3. 튜닝 매개 변수는 없지만 addFirst(), addLast(), getFirst(), getLast(), removeFirst(), removeLast()를 가진다.

3. Set

1. Set

1. 순서 상관없이 데이터를 저장하기 위한 자료구조

2. 중복 허용 X

3. Set 인터페이스는 Collection 인터페이스에 정의된 메서드를 데이터의 중복을 막도록 설계한 채로 제공한다.

4. HashSet
❗
원소들의 순서가 일정하지 않다.
1. 해시 테이블에 원소 저장한다.
2. 성능면에서 (HashSet, TreeSet, LinkedHashSet 중) 가장 우수하다.
3. 예제 - 문자열을 Set에 저장하기

package ex17.collection;

import java.util.HashSet;

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

        set.add("Milk");
        set.add("Bread");
        set.add("Butter");
        set.add("Cheese");
        set.add("Ham");
        set.add("Ham");

        System.out.println(set);

        if (set.contains("Ham")) {
            System.out.println("햄도 포함되어 있음");
        }
    }
}

5. LinkedHashSet
❗
입력된 순서대로 정렬
1. 해시 테이블과 연결 리스트를 결합한 것
2. 약간의 비용을 들여서 HashSet의 문제점인 순서의 불명확성을 제거한 방법
3. 예제

package ex17.collection;

import java.util.LinkedHashSet;

public class SetTest {
    public static void main(String[] args) {
        LinkedHashSet<String> set = new LinkedHashSet();

        set.add("Milk");
        set.add("Bread");
        set.add("Butter");
        set.add("Cheese");
        set.add("Ham");
        set.add("Ham");

        System.out.println(set);

        if (set.contains("Ham")) {
            System.out.println("햄도 포함되어 있음");
        }
    }
}

6. TreeSet
❗
알파벳 순서대로 정렬
1. 레드 - 블랙 트리(red - black tree)에 원소를 저장한다.
2. 값에 따라 순서가 결정된다.
3. HashSet보다 느리다.
4. 예제

package ex17.collection;

import java.util.TreeSet;

public class SetTest {
    public static void main(String[] args) {
        TreeSet<String> set = new TreeSet();

        set.add("Milk");
        set.add("Bread");
        set.add("Butter");
        set.add("Cheese");
        set.add("Ham");
        set.add("Ham");

        System.out.println(set);

        if (set.contains("Ham")) {
            System.out.println("햄도 포함되어 있음");
        }
    }
}

2. 합집합, 차집합, 교집합

1. addAll(): 합집합 계산

package ex17.collection;

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

public class SetTest2 {
    public static void main(String[] args) {
        Set<Integer> s1 = new HashSet(Arrays.asList(1, 2, 3, 4, 5, 7, 9));
        Set<Integer> s2 = new HashSet(Arrays.asList(2, 4, 6, 8));

        s1.addAll(s2); // 합집합 계산
        System.out.println(s1);
    }
}

2. removeAll(): 차집합 계산

package ex17.collection;

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

public class SetTest2 {
    public static void main(String[] args) {
        Set<Integer> s1 = new HashSet(Arrays.asList(1, 2, 3, 4, 5, 7, 9));
        Set<Integer> s2 = new HashSet(Arrays.asList(2, 4, 6, 8));

        s1.removeAll(s2); // 차집합 계산
        System.out.println(s1);
    }
}

3. retainAll(): 교집합 계산

package ex17.collection;

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

public class SetTest2 {
    public static void main(String[] args) {
        Set<Integer> s1 = new HashSet(Arrays.asList(1, 2, 3, 4, 5, 7, 9));
        Set<Integer> s2 = new HashSet(Arrays.asList(2, 4, 6, 8));
        
        s1.retainAll(s2); // 교집합 계산
        System.out.println(s1);
    }
}

3. 예제 - 중복된 단어 검출하기

package ex17.collection;

import java.util.*;

public class FindDupplication {
    public static void main(String[] args) {
        Set<String> s = new HashSet();
        String[] sample = {"사과", "사과", "바나나", "토마토"};
        for (String a : sample) {
            if (!s.add(a)) { // add() - boolean 타입으로 중복되어 추가하지 못하면 false 반환
                System.out.println("중복된 단어: " + a);
            }
        }
        System.out.println(s.size() + " 중복되지 않은 단어: " + s);
    }
}

4. Map

          ┌────────── Collection (인터페이스) ──────────┐
          │                                            │
    ┌─────── List ───────┐                     ┌────── Set ────────────────────┐
    │                    │                     │                  │            │
 ArrayList           LinkedList          HashSet            LinkedHashSet   TreeSet
				                              
     
                ┌──────────── Map (인터페이스) ─────────────┐
                │                   │                      │
           HashMap            LinkedHashMap              TreeMap
           

1. Map

1. 키 - 값을 하나의 쌍으로 묶어서 저장하는 자료구조

2. = Dictionary

3. 키는 중복될 수 없다.

4. 동일한 키로 두 개의 값을 저장할 수 없다.

5. 키가 제시되면 Map은 값을 반환한다.

6. HashMap VS TreeMap
1. HashMap : 해시 테이블에 데이터 저장, 키 순서 정렬X → 약간 더 빠르다.
2. TreeMap : 탐색 트리에 데이터 저장, 키 순서 정렬O

7. 메서드
1. put() : 데이터 저장
1. 키가 이미 존재하는 경우 매핑되는 값이 변경

Map<Integer, String> freshman = new HashMap();
freshman.put("kim","1234");

2. get() : 값 추출

value = freshman.get("park");

3. Map.of() : 한 문장으로 HashMap 초기화

Map<Integer, String> map = Map.of("kim", "1234", "park", "pass", "lee", "word");

8. 예제 - Map에 학생들의 데이터 저장하기

package ex17.collection;

import java.util.*;

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

        map.put("kim", "1234");
        map.put("park", "pass");
        map.put("lee", "word");

        System.out.println("map = " + map);
        System.out.println("lee를 key로 가지는 value = " + map.get("lee"));

        //keySet() : 키들의 집합을 반환
        for (String key : map.keySet()) {
            String value = map.get(key);
            System.out.println("key = " + key + ", value = " + value);
        }
        System.out.println(map);
        map.remove("3");
        System.out.println("remove(3)이후 :" + map);
        map.put("choi", "password");
        System.out.println(map);
    }
}

2. Map의 모든 요소 방문하기

1. Collection 인터페이스를 구현하지 않기 때문에 Map에 저장된 데이터를 꺼내는 코드가 약간 다르다.

2. for - each 구문과 keySet() 사용하는 방법

for (String key : map.keySet()) {
    System.out.println("key = " + key + ", value = " + map.get(key));
}

• 변수 타입 추론 사용

for (var key : map.keySet()) {
   System.out.println("key = " + key + ", value = " + map.get(key));
}

1. 반복자를 사용하는 방법

Iterator it = map.keySet().iterator();
    while (it.hasNext()) {
        String key = (String) it.next();
        System.out.println("key = " + key + ", value = " + map.get(key));
    }

1. Stream 라이브러리를 사용하는 방법 (각 요소에 대해 반복하는 부분 → 람다식)

map.forEach((key, value) -> {
    System.out.println("key = " + key + ", value = " + value);
});

5. Queue

           ┌────────── Collection (인터페이스) ──────────┐
           │                                            │
    ┌─────── List ───────┐                     ┌────── Set ────────────────────┐
    │                    │                     │                  │            │
 ArrayList           LinkedList          HashSet            LinkedHashSet   TreeSet
				                              
     
                ┌──────────── Map (인터페이스) ──────────────┐
                │                   │                       │
           HashMap            LinkedHashMap              TreeMap
           

                  ┌────────── Queue (인터페이스) ────────────────────────┐
                  │                         │                           │
               ArrayDeque           PriorityQueue            LinkedList (Queue 구현)

1. Queue

1. 데이터를 처리하기 전에 잠시 저장하고 있는 자료구조

2. FIFO (first - in - first - out)형식으로 데이터 저장

3. 예외적으로 우선순위 큐의 경우 원소들을 우선순위에 따라 저장한다.(우선순위 디폴트는 원소들의 값)

4. Queue 인터페이스 구현한 클래스 : ArrayDeque, LinkedList, PriorityQueue

5. Deque
1. 전단과 후단에서 모두 원소를 추가하거나 삭제할 수 있다.
2. Deque 인터페이스로 추가되었다.
3. Deque 인터페이스는 ArrayDeque와 LinkedList 클래스로 구현된다.

2. Queue 메서드

package ex17.collection;

import java.util.*;

public class QueueTest {
    public static void main(String[] args) {
        Queue<Integer> q = new LinkedList();

        for (int i = 0; i < 5; i++) {
            q.add(i);
        }

        System.out.println("큐의 요소: " + q);

        int e = q.remove();
        System.out.println("삭제된 요소: " + e);
        System.out.println(q);
    }
}

3. 우선순위 큐

1. 원소가 무작위로 삽입되었더라도 정렬된 상태로 원소들을 추출한다.
→ remove() 호출할 때마다 가장 작은 원소가 추출된다.

2. heap 자료구조를 내부적으로 사용한다.

3. heap은 이진 트리의 일종으로 add()와 remove()를 호출하면 가장 작은 원소가 효과적으로 트리의 루트로 이동한다.

4. 우선순위 큐는 기본적으로 최소 힙이다. 즉 가장 작은 값이 항상 루트에 위치하도록 Heapify 과정을 수행한다.

5. 그러나 자식 노드들은 반드시 오름차순으로 정렬되는 것은 아니다.
⇒ 따라서 우선순위 큐는 항상 정렬된 상태로 원소들을 저장하고 있는 것은 아니다.

6. 대표적인 예시 - 작업 스케줄링 : 각 작업은 우선 순위를 가지고 있고 가장 높은 우선 순위의 작업이 큐에서 먼저 추출되어서 시작된다.

7. 예제

package ex17.collection;

import java.util.*;

public class PriorityQueueTest {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue();
        pq.add(30);
        pq.add(80);
        pq.add(20);

        System.out.println(pq);
        System.out.println("삭제된 원소: " + pq.remove());
        System.out.println("삭제된 원소: " + pq.remove());
    }
}



• 코드 실행 흐름
1. pq.add(30);

[30]

2. pq.add(80);

   30
  /
 80
 
 [30, 80]

3. pq.add(20);

   20
  /  \
 80   30
 
[30, 80, 20] -> [20, 80, 30]

 

6. Collections 클래스

1. Collections 클래스

1. 여러 알고리즘을 구현한 메서드 제공

2. 이 메서드들은 제네릭 기술을 사용하여 작성되었으며 정적 메소드 형태이다.

3. 메서드의 첫 번째 매개 변수는 알고리즘이 적용되는 컬렉션이 된다.
e.g.) Collections.sort(list)

4. 정렬(Sorting), 섞기(Shuffling), 탐색(Searching)

2. 정렬(Sorting)

1. 정렬이란 데이터를 어떤 기준에 의하여 순서대로 나열하는 것이다.

2. Collections 클래스의 정렬은 속도가 비교적 빠르고 안정성이 보장되는 합병 정렬을 이용한다.

3. 시간복잡도 : O(nlog(n))

4. 거의 정렬되어 있는 리스트에 대해서는 상당히 빠르다.

5. Comparable 인터페이스를 이용한다. → String과 Date는 Comparable 인터페이스를 구현한다. → 정렬하고자 하는 리스트에 들어 있는 원소가 String 타입이라면 알파벳 순서대로 정렬, Date 타입이라면 시간적인 순서대로 정렬 가능하다.

6. 예제 - 문자열 정렬하기

package ex17.collection;

import java.util.*;

public class Sort {
    public static void main(String[] args) {
        String[] sample = {"i", "walk", "the", "line"};
        List<String> list = Arrays.asList(sample);
        System.out.println(list);
        // 알파벳 순으로 정렬
        Collections.sort(list);
        System.out.println(list);
    }
}

7. 예제 - 사용자 클래스의 객체 정렬하기

package ex17.collection;

import java.util.*;

class Student implements Comparable<Student> {
    int number;
    String name;

    public Student(int number, String name) {
        this.number = number;
        this.name = name;
    }

		// System.out.println(list); -> Student 객체의 toString 메서드가 호출된다.
		// 출력 시 객체 자체가 아닌 name만 출력된다.
    public String toString() {
        return name;
    }

		// number 기준 내림차순으로 정렬
		// 양수(크면), 음수(작으면), 0(같으면)
		// this.number - s.number - 오름차순
    public int compareTo(Student s) {
        return s.number - number; // 내림차순
    }
}

public class SortTest {
    public static void main(String[] args) {
        Student arr[] = {
                new Student(2, "김철수"),
                new Student(3, "이철수"),
                new Student(1, "박철수")
        };

        List<Student> list = Arrays.asList(arr);
        Collections.sort(list);
        System.out.println(list);
    }
}



• 정렬 과정
1. 초기 리스트 : [김철수(2), 이철수(3), 박철수(1)]
2. 정렬 기준: compareTo(Student s) → s.number - number
• 이철수(3) vs 김철수(2) → 3 - 2 = 1 (순서 유지)
• 김철수(2) vs 박철수(1) → 2 - 1 = 1 (순서 유지)
3. 최종 정렬된 리스트 : [이철수(3), 김철수(2), 박철수(1)]

3. 섞기(Shuffling)

1. 정렬의 반대 동작

2. 리스트에 존재하는 정렬을 파괴해서 원소들의 순서를 랜덤하게 만든다.

3. 예제

package ex17.collection;

import java.util.*;

public class Shuffle {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList();
        for (int i = 0; i < 10; i++) {
            list.add(i);
        }
        System.out.println("shuffle 전 list: " + list);
        Collections.shuffle(list);
        System.out.println("shuffle 후 list: " + list);
    }
}

4. 탐색(Searching)

1. 리스트 안에서 원하는 원소를 찾는 것

2. 선형 탐색 : 리스트가 정렬되어 있지 않다면 처음부터 모든 원소를 방문해야 한다.

3. 이진 탐색 : 리스트가 정렬되어 있다면 중간에 있는 원소와 먼저 비교하는 것이 좋다.

4. Collections.binarySearch 알고리즘
1. 정렬된 리스트에서 지정된 원소를 이진 탐색
2. binarySearch()는 리스트와 탐색할 원소를 받는다.
3. 리스트는 정렬되어 있다고 가정한다.

index = Collections.binarySearch (collec, element); // 리스트, 탐색할 원소

4. 반환값이 양수이면 탐색이 성공한 객체의 위치
5. collec.get(index)하면 원하는 객체를 얻을 수 있다.
6. 반환값이 음수이면 탐색 실패 → 반환값에서 현재의 데이터가 삽입될 수 있는 위치 파악 가능 (반환값이 pos이면 (-pos - 1)이 삽입 위치)

int pos = Collections.binarySearch(list, key);
if (pos < 0){
    l.add(-pos - 1);
}

5. 예제 - 숫자들의 리스트 탐색하기

package ex17.collection;

import java.util.*;

public class Search {
    public static void main(String[] args) {
        int key = 50;
        List<Integer> list = new ArrayList();
        for (int i = 0; i < 100; i++) {
            list.add(i);
        }
        int index = Collections.binarySearch(list, key);
        System.out.println("탐색의 반환값 = " + index);
    }
}

7. 문제 풀기(실습)

1. Set으로 로또 만들기

2. 영어 사전

3. 카드 게임