컬렉션 프레임워크 - 순회, 정렬, 전체 정리

순회1 - 직접 구현하는 Iterable, Iterator

자료 구조에 순회는 자료 구조에 들어있는 데이터를 차례대로 접근해서 처리하는 것을 순회라 한다.

 

Iterable, Iterlator

Iterable: "반복 가능한"

Iterlator: "반복자"

 

Iterable 인터페이스의 주요 메서드

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

• 단순히 Iterator 반복자를 반환한다.

 

Iterator 인터페이스의 주요 메서드

public interface Iterator<E> {
    boolean hasNext();
    E next();
}

• hasNext(): 다음 요소가 있는지 확인한다. 다음 요소가 없으면 false를 반환한다.
• next(): 다음 요소를 반환한다. 내부에 있는 위치를 다음으로 이동한다.

 

 

 

---

순회2 - 향상된 for문

Iterable과 향상된 for문(Enhanced For Loop)

자바는 Iterable 인터페이스를 구현한 객체에 대해서 향상된 for문을 사용할 수 있게 해준다.

 

 

---

순회3 - 자바가 제공하는 Iterrable, Iterator

 

• Collection 인터페이스 상위에 Iterable이 있어 모든 컬렉션은 Iterable과 Iterator를 사용해서 순회할 수 있다.
• Map의 경우 Key 뿐만 아니라 Value까지 있기 땜누에 바로 순회를 할 수는 없다. 대신에 Key나 Value를 정해서 순회할 수 있는데, keySet(), values()를 호출하면 Set, Colletion을 반환하기 때문에 Key나 Value를 정해서 순회할 수 있다. 물론 Entry를 Set 구조로 반환하는 entrySet()도 순회가 가능하다.

 

참고: Iterator (반복자) 디자인 패턴은 객체 지향 프로그래밍에서 컬렉션의 요소들을 순회할 때 사용되는 디자인 패턴이다. 이 패턴은 컬렉션의 내부 표현 방식을 노출시키지 않으면서도 그 안의 각 요소에 순차적으로 접근할 수 있게 해준다. Iteraotr 패턴은 컬렉션의 구현과는 독립적으로 요소들을 탐색할 수 있는 방법을 제공하며, 이로 인해 코드의 복잡성을 줄이고 재사용성을 높일 수 있다.

 

 

---

정렬1 - Comparable, Comparator

정렬 알고리즘

자바는 초기에는 퀵소트를 사용했다가 지금은 데이터가 작을 때(32개 이하)는 듀얼 피벗 퀵소트(Dual-Pivot QuickSort)를 사용하고, 데이터가 많을 때는 팀소트(TimSort)를 사용한다. 이런 알고리즘은 평균 O(log n)의 성능을 제공한다.

 

비교자 - Comparator

public interface Comparator<T> {
	int compare(T o1, T o2);
}

• 두 인술르 비교해서 결과 값을 반환한다.
  • 첫 번째 인수가 더 작으면 음수, 예(-1)
  • 두 값이 같으면 0
  • 첫 번째 인수가 더 크면 양수, 예(1)

package collection.cmopare;

import java.util.Arrays;
import java.util.Comparator;

public class SortMain2 {

    public static void main(String[] args) {
        Integer[] array = {3, 2, 1};
        System.out.println(Arrays.toString(array));
        System.out.println("Comparator 비교");
        Arrays.sort(array, new AscComparator());
        System.out.println("AscComparator: " + Arrays.toString(array));


        Arrays.sort(array, new DscComparator());
        System.out.println("DescComparator: " + Arrays.toString(array));
        Arrays.sort(array, new AscComparator().reversed());
        System.out.println("AscComparator.reversed: " + Arrays.toString(array));
    }

    private static class AscComparator implements Comparator<Integer> {

        @Override
        public int compare(Integer o1, Integer o2) {
            System.out.println("o1=" + o1 + " o2=" + o2);
            return (o1 > o2) ? 1 : ((o1 == o2) ? 0 : -1);
        }
    }

    private static class DscComparator implements Comparator<Integer> {
        @Override
        public int compare(Integer o1, Integer o2) {
            System.out.println("o1=" + o1 + " o2=" + o2);
            return (o1 > o2) ? -1 : ((o1 == o2) ? 0 : 1);
        }
    }
}

 

실행 결과

[3, 2, 1]
Comparator 비교
o1=2 o2=3
o1=1 o2=2
AscComparator: [1, 2, 3]

o1=2 o2=1
o1=3 o2=2
DescComparator: [3, 2, 1]

o1=3 o2=2
o1=2 o2=1
AscComparator.reversed: [3, 2, 1]

 

 

---

정렬2 - Comparable, Comparator

package collection.cmopare;

public class MyUser implements Comparable<MyUser> {

    private String id;
    private int age;

    public MyUser(String id, int age) {
        this.id = id;
        this.age = age;
    }

    public String getId() {
        return id;
    }

    public int getAge() {
        return age;
    }

    @Override
    public int compareTo(MyUser o) {
        System.out.println(this + " vs " + o);
        return this.age < o.age ? -1 : (this.age == o.age ? 0 : 1);
    }

    @Override
    public String toString() {
        return "MyUser{" +
                "id='" + id + '\'' +
                ", age=" + age +
                '}';
    }
}
-----------------------------------------------------------------------------
package collection.cmopare;

import java.util.Comparator;

public class IdComparator implements Comparator<MyUser> {
    @Override
    public int compare(MyUser o1, MyUser o2) {
        return o1.getId().compareTo(o2.getId());
    }
}

----------------------------------------------------------------------------
import java.util.Arrays;

public class SortMain3 {

    public static void main(String[] args) {
        MyUser user1 = new MyUser("a", 30);
        MyUser user2 = new MyUser("b", 20);
        MyUser user3 = new MyUser("c", 10);

        MyUser[] array = {user1, user2, user3};
        System.out.println("기본 데이터");
        System.out.println(Arrays.toString(array));

        System.out.println("Comparable 기본 정렬");
        Arrays.sort(array);
        System.out.println(Arrays.toString(array));

        //추가
        System.out.println("IdComparator 정렬");
        Arrays.sort(array, new IdComparator());
        System.out.println(Arrays.toString(array));

        System.out.println("IdComparator.reversed 정렬");
        Arrays.sort(array, new IdComparator().reversed());
        System.out.println(Arrays.toString(array));
    }
}

 

Arrays.sort(array)

기본 정렬을 시도한다. 이때는 객체가 스스로 가지고 있는 Comparable 인터페이스를 사용해서 비교한다.

 

Arrays.sort(array, Comparator)

기본 정렬이 아니라 다른 정렬 방식을 지정하고 싶다면 Arrays.sort의 인수로 비교자(Comparator)를 만들어서 넘겨주면 된다. 이렇게 비교자를 따로 전달하면 객체가 기본으로 가지고 있는 Comparable을 무시하고 별도로 전달한 비교자를 사용해서 정렬한다.

 

---

정렬3 - Comparable, Comparator

정렬은 배열뿐만 아니라 List에도 사용할 수 있다.

package collection.cmopare;

import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class SortMain4 {

    public static void main(String[] args) {
        MyUser user1 = new MyUser("a", 30);
        MyUser user2 = new MyUser("b", 20);
        MyUser user3 = new MyUser("c", 10);

        List<MyUser> list = new LinkedList<>(List.of(user1, user2, user3));
        System.out.println("기본 데이터");
        System.out.println(list);

        System.out.println("Comparable 기본 정렬");
        list.sort(null);
//        Collections.sort(list);
        System.out.println(list);

        System.out.println("IdComparator 정렬");
        list.sort(new IdComparator());
//        Collections.sort(list, new IdComparator());
        System.out.println(list);
    }
}

 

Collections.sort(list)

• 리스트는 순서가 있는 컬렉션이므로 정렬할 수 있다.
• 이 메서드를 사용하면 기본 정렬이 적용된다.
• 하지만 이 방식보다는 객체 스스로 정렬 메서드를 가지고 있는 list.sort() 사용을 더 권장한다.

list.sort(null)

• 별도의 비교자가 없으므로 Comparable로 비교해서 정렬한다.
• 자연적인 순서로 비교한다.
• 자바 1.8부터 사용

Collections.sort(list, new Comparator())

• 별도의 비교자로 비교하고 싶으면 다음 인자에 비교자를 넘기면 된다.
• 하지만 이 방식보다는 객체 스스로 정렬 메서드를 가지고 있는 list.sort() 사용을 더 권장한다.

list.sort(new Comparator())

• 전달한 비교자로 비교한다.
• 자바 1.8부터 사용

 

Tree 구조와 정렬

TreeSet과 같은 이진 탐색 트리 구조는 데이터를 보관할 때, 데이터를 정렬하면서 보관한다. 따라서 정렬 기준을 제공하는 것이 필수다. 

 

package collection.cmopare;

import java.util.LinkedList;
import java.util.List;
import java.util.TreeSet;

public class SortMain5 {

    public static void main(String[] args) {
        MyUser user1 = new MyUser("a", 30);
        MyUser user2 = new MyUser("b", 20);
        MyUser user3 = new MyUser("c", 10);

        System.out.println("Comparable 기본 정렬");
        TreeSet<MyUser> treeSet1 = new TreeSet<>();
        treeSet1.add(user1);
        treeSet1.add(user2);
        treeSet1.add(user3);
        System.out.println(treeSet1);

        System.out.println("IdComparator 정렬");
        TreeSet<MyUser> treeSet2 = new TreeSet<>(new IdComparator());
        treeSet2.add(user1);
        treeSet2.add(user2);
        treeSet2.add(user3);

        System.out.println(treeSet2);
    }
}

 

new TreeSet<>()

• TreeSet을 생성할 때 별도의 비교자를 제공하지 않으면 객체가 구현한 Comparable을 사용한다.

 

new TreeSet<>(new Iterator())

• TreeSet을 생성할 때 별도의 비교자를 제공하면 Comparable 대신 비교자(Comparator)를 사용해서 정렬한다.

 

정리

자바의 정렬 알고리즘은 매우 복잡하고, 또 거의 완성형에 가깝다.

자바는 개발자가 복잡한 정렬 알고리즘은 신경쓰지 않으면서 정렬의 기준만 간단히 변경할 수 있도록, 정렬의 기준을 Comparable, Comparator 인터페이스를 통해 추상화해 두었다.

객체의 정렬이 필요한 경우 Comparable을 통해 기본 자연 순서를 제공하자. 자연 순서 외에 다른 정렬 기준이 추가로 필요하면 Comparator를 제공하자

---

컬렉션 유틸

정렬

package collection.utils;

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

public class CollectionSortMain {

    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);

        Integer max = Collections.max(list);
        Integer min = Collections.min(list);

        System.out.println("max = " + max);
        System.out.println("min = " + min);

        System.out.println("list = " + list);
        Collections.shuffle(list);
        System.out.println("shuffle list = " + list);
        Collections.sort(list);
        System.out.println("sort list = " + list);
        Collections.reverse(list);
        System.out.println("reverse list = " + list);
    }
}

 

편리한 컬렉션 생성

package collection.utils;

import java.util.List;
import java.util.Map;
import java.util.Set;

public class OfMain {

    public static void main(String[] args) {
        // 편리한 불변 컬렉션 생성
        List<Integer> list = List.of(1, 2, 3);
        Set<Integer> set = Set.of(1, 2, 3);
        Map<Integer, String> map = Map.of(1, "one", 2, "two");

        System.out.println("list = " + list);
        System.out.println("set = " + set);
        System.out.println("map = " + map);
        System.out.println("list.getClass() = " + list.getClass());

        //java.lang.UnsupportedOperationException 예외 발생
        //list.add(4);
    }
}

• List.of(...): 를 사용하면 컬렉션을 편리하게 생성할 수 있다. 단 이때는 가변이 아니라 불변 컬렉션이 생성된다.
  • List, Set, Map 모두 of() 메서드를 지원한다.
• 불변 컬렉션은 변경할 수 없다. 변경 메서드를 호출하면 UnsupportedOperationException 예외가 발생한다.

 

불변 컬렉션과 가변 컬렉션 전환

package collection.utils;

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

public class ImmutableMain {

    public static void main(String[] args) {
        //불변 리스트 생성
        List<Integer> list = List.of(1, 2, 3);

        //가변 리스트
        ArrayList<Integer> mutableList = new ArrayList<>(list);
        mutableList.add(4);
        System.out.println("mutableList = " + mutableList);
        System.out.println("mutableList class = " + mutableList.getClass());

        //불변 리스트
        List<Integer> unmodifiableList = Collections.unmodifiableList(mutableList);
        System.out.println("unmodifiableList class= " + unmodifiableList.getClass());
        //java.lang.UnsupportedOperationException 예외 발생
        //unmodifiableList.add(5);
    }
}

 

실행 결과

mutableList = [1, 2, 3, 4]
mutableList class = class java.util.ArrayList
unmodifiableList class= class java.util.Collections$UnmodifiableRandomAccessList

• 불변 리스트를 가변 리스트로 전환 하려면 new ArrayList<>()를 사용하면 된다.
• 가변 리스트를 불변 리스트로 전환하려면 Collections.unmodifiableList()를 사용하면 된다.
• 물론 다양한 unmodifiableXx()가 존재한다.

빈 리스트 생성

package collection.utils;

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

public class EmptyListMain {

    public static void main(String[] args) {
        //빈 가변 리스트 생성
        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();

        //빈 불변 리스트 생성
        List<Object> list3 = Collections.emptyList(); //자바5
        List<Integer> list4 = List.of(); //자바9

        System.out.println("list3 = " + list3.getClass());
        System.out.println("list4 = " + list4.getClass());
    }
}

 

 

Arrays.asList()

• 위와 같이 리스트를 생성할 수 있다.
• 자바 1.2부터 존재했다. 자바 9를 사용한다면 List.of()를 권장한다.
• Arrays.asList()로 생성된 리스트는 고정된 크기를 가지지만, 요소들은 변경할 수 있다. 즉, 리스트의 길이는 변경할 수 없지만, 기존 위치에 있는 요소들은 다른 요소로 교체할 수 있다.
• 고정도 가변도 아닌 애매한 리스트이다.

정리하면 일반적으로 List.of()를 사용하는 것을 권장한다. 다음과 같은 경우 Arrays.asList()를 선택할 수 이싿.

• 변경 가능한 요소: 리스트 내부의 요소를 변경해야 하는 경우(단, 리스트의 크기는 변경할 수 없음)
• 하위 호환성: Java9 이전 버전에서 작업해야 하는경우 

 

멀티 스레드 동기화

package collection.utils;

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

public class SyncMain {

    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);

        System.out.println("list class = " + list.getClass());
        List<Integer> synchronizedList = Collections.synchronizedList(list);
        System.out.println("synchronizedList class = " + synchronizedList.getClass());
    }
}

 

실행 결과

list class = class java.util.ArrayList
synchronizedList class = class java.util.Collections$SynchronizedRandomAccessList

• Collections.synchronizedList를 사용하면 일반 리스트보다 멀티스레드 상황에서 동기화 문제가 발생하지 않는 안전한 리스트로 만들 수 있다.
• 동기화 작업으로 인해 일반 리스트보다 성능은 더 느리다.

---

컬렉션 프레임워크 전체 정리

Collection 인터페이스의 필요성

Collection 인터페이스는 자바 컬렉션 프레임워크의 가장 기본적인 인터페이스로, 자바에서 데이터 그룹을 다루는데 가장 필요한 기본적인 메서드들을 정의한다. 그리고 다양한 컬렉션들이 공통적으로 따라야하는 기본 규약을 저으이한다. List, Set, Queeu와 같은 더 구체적인 컬렉션 인터페이스들은 모두 Collection 인터페이스를 확장하여, 공통된 메서드를 상속받고 추가적인 기능이나 특성을 제공한다. 이러한 설계는 자바 컬렉션 프레임워크의 일관성과 재사용성을 높여준다.

 

• 일관성: 모든 컬렉션 타입들이 Collection 인터페이스를 구현함으로써, 모든 컬렉션들이 기본적인 동작을 공유한다는 것을 보장한다. 이는 개발자가 다양한 타입의 컬렉션을 다룰 때 일관된 방식으로 접근할 수 있게 해준다.
• 재사용성: Collection 인터페이스에 정의된 메서드들은 다양한 컬렉션 타입들에 공통으로 적용된다. 이는 코드의 재사용성을 높이고, 유지 보수를 용이하게 한다.
• 확장성: 새로운 컬렉션 타입을 만들 때 Collection 인터페이스를 구현함으로써, 기존에 정의된 알고리즘과 도구를 사용하 룻 있게 된다. 이는 프레임워크의 확장성을 향상시킨다.
• 다형성: Collection 인터페이스를 사용함으로써, 다양한 컬렉션 타입들을 같은 타입으로 다룰 수 있다. 이는 다형성을 활용해서 유연한 코드를 작성할 수 있게 해준다.

 

Collection 인터페이스의 주요 메서드

• add(E e): 컬렉션에 요소를 추가한다.
• remove(Object o): 주어진 객체를 컬렉션에서 제거한다.
• size(): 컬렉션에 포함된 요소의 수를 반환한다.
• isEmpty(): 컬렉션이 비어 있는지 확인한다.
• contains(Object o): 컬렉션이 특정 요소를 포함하고 있는지 확인한다.
• iterator(): 컬렉션의 요소에 접근하기 위한 반복자를 반환한다
• clear(): 컬렉션의 모든 요소를 제거한다.

 

Colleciotn은 Map을 제외한 모든 컬렉션 타입의 부모이다. 따라서 모든 컬렉션을 받아서 유연하게 처리할 수 있다.

대표적으로 컬렉션 인터페이스는 iterator를 제공한다. 따라서 데이터를 단순히 순회할 목적이라면 Collection을 사용하면 모든 컬렉션 타입의 데이터를 순회할 수 있다.

 

컬렉션 프레임워크는 크게 인터페이스, 구현, 알고리즘을 제공한다.

 

인터페이스

• Collection: 단일 루프 인터페이스로, 모든 컬렉션 클래스가 이 인터페이스를 상속받는다.
  • List, Set, Queue 등의 인터페이스가 여기에 포함된다.
• List: 순서가 있는 컬렉션을 나타내며, 중복 요소를 허용한다. 인덱스를 통해 요소에 접근할 수 있다.
  • 예: ArrayList, LinkedList
• Set: 중복 요소를 허용하지 않는 컬렉션을 나타낸다. 특정 윙치가 없기 때문에 인덱스를 통해 요소에 접근할 수 없다.
  • 예: HashSet, LinkedHashSet, TreeSet
• Queue: 요소가 처리되기 전에 보관되는 컬렉션을 나타낸다.
  • 예: ArrayDeque, LinkedDList, PriorityQueue
• Map: 키와 값 쌍으로 요소를 저장하는 객체이다. Map은 Collection 인터페이스를 상속받지 않는다.
  • 예: HashMap, LinkedHashMap, TreeMap

 

구현

• List: ArrayList는 내부적으로 배열을 사용하며, LinkedList는 연결 리스트를 사용한다.
• Set: HashSet은 해시 테이블을, LinkedHashSet은 해시 테이블과 연결 리스트를, TreeSet은 레드-블랙 트리를 사용한다.
• Map: HashMap은 해시 테이블을, LinkedHashMap은 테이블과 연결 리스트를, TreeMap은 레드-블랙 트리를 사용한다.
• Queue: LinkedList는 연결 리스트를 사용한다. ArrayDeque는 배열 기반의 원형 큐를 사용한다. 대부분의 경우 ArrayDeque가 빠르다.

 

알고리즘

컬렉션 프레임워크는 데이터를 처리하고 조작하기 위한 다양한 알고리즘을 제공한다. 이러한 알고리즘은 각각의 자료 구조 자체적으로 기능을 제공하기도 하고 또 Collections와 Arrays 클래스에 정적 메소드 형태로 구현되어 있다. 이를 통해 정렬, 검색, 순환, 변환 등의 작업을 수행할 수 있다.

 

선택 가이드

• 순서가 중요하고 중복이 허용되는 경우: List 인터페이스를 사용하자. ArrayList가 일반적인 선택이지만, 추가/삭제 작업이 앞쪽에서 번번한 경우에는 LinkedList가 성능상 더 좋은 선택이다.
• 중복을 허용하지 않고 순서가 중요하지 않는 경우: HashSet을 사용하자. 순서를 유지해야 하면 LinkedHashSet을, 정렬된 순서가 중요하면 TreeSet을 사용하자
• 요소를 키-값 쌍으로 저장하려는 경우: Map 인터페이스를 사용하자. 순서가 중요하지 않다면 HashMap을, 순서를 유지해야 하면 LinkedHashMap을, 정렬된 순서가 필요하면 TreeMap을 사용하자.
• 요소를 처리하기 전에 보관해야 하는 경우: Queue, Deque 인터페이스를 사용하자. 스택, 큐 구조 모두 ArrayDeque를 사용하는 것이 가장 빠르다. 만약 우선순위에 따라 요소를 처리해야 한다면 PriorityQueue를 고려하자.

 

실무 선택 가이드

• List의 경우 대부분 ArrayList를 사용한다.
• Set의 경우 대부분 HashSet을 사용한다.
• Map의 경우 대부분 HashMap을 사용한다.
• Queue의 경우 대부분 ArrayDeque를 사용한다.

 

 

 

출처 - 김영한의 실전 자바 중급 2편