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

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

순회라는 단어는 여러 곳을 돌아다닌다는 뜻이다. 자료 구조에 순회는 자료 구조에 들어 있는 데이터를 차례대로 접근해서 처리하는 것을 순회라고 한다. 그런데 다양한 자료 구조가 있고, 각각의 자료 구조마다 데이터를 접근하는 방법이 모두 다르다.

예를 들어서 배열 리스트는 index 를 size 까지 차례로 증가하면서 순회해야 하고, 연결 리스트는 node.next 를 사용해서 node 의 끝이 null 일 때 까지 순회해야 한다. 이렇듯 각 자료 구조의 순회 방법이 서로 다르다.

배열 리스트, 연결 리스트, 해시 셋, 연결 해시 셋, 트리 셋 등등 다양한 자료 구조가 있다. 각각의 자료 구조마다 순회하는방법이 서로 다르기 때문에, 각 자료 구조의 순회 방법을 배워야 한다. 그리고 순회 방법을 배우려면 자료 구조의 내부 구조도 알아야 한다. 결과적으로 너무 많은 내용을 알아야 하는 것이다. 하지만 자료 구조를 사용하는 개발자 입장에서 보면 단순히 자료 구조에 있는 모든 데이터에 순서대로 접근해서 출력하거나 계산하고 싶을 뿐이다.

자료 구조의 구현과 관계 없이 모든 자료 구조를 동일한 방법으로 순회할 수 있는 일관성 있는 방법이 있다면, 자료 구조 를 사용하는 개발자 입장에서 매우 편리할 것이다.

자바는 이런 문제를 해결하기 위해 Iterable 과 Iterator 인터페이스를 제공한다.

Iterable, Iterator

Iteratble 인터페이스 주요 메서드

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

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

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

• hasNext() : 다음 요소가 있는지 확인한다. 다음 요소가 없으면 false 를 반환한다.

• next() : 다음 요소를 반환한다. 내부에 있는 위치를 다음으로 이동한다.

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

Iterator 의 구현체 예제

• 생성자를 통해 반복자가 사용할 배열을 참조한다. 여기서 참조한 배열을 순회할 것이다.

• currentIndex : 현재 인덱스, next() 를 호출할 때마다 하나씩 증가한다.

• hasNext() : 다음 항목이 있는지 검사한다. 배열의 끝에 다다르면 순회가 끝났으므로 false 를 반환한다.

  • 참고로 인덱스의 길이는 0부터 시작하므로 배열의 길이에 1을 빼야 마지막 인덱스가 나온다.

• next() : 다음 항목을 반환한다.

  • currentIndex 를 하나 증가하고 항목을 반환한다.

  • 인덱스는 0부터 시작하기 때문에 currentIndex 는 처음에는 -1 을 가진다. 이렇게 하면 다음 항목을 조회했을 때 0 이 된다. 따라서 처음 next() 를 호출하면 0 번 인덱스를 가리킨다.

package collection.iterable;

import java.util.Iterator;

public class MyArrayIterator implements Iterator<Integer> {

    private int currnetIndex = -1;
    private int[] targetArr;

    public MyArrayIterator(int[] targetArr) {
        this.targetArr = targetArr;
    }

    @Override
    public boolean hasNext() {
        return currnetIndex < targetArr.length - 1;
    }

    @Override
    public Integer next() {
        return targetArr[++currnetIndex];
    }
}

Iterator는 단독으로 사용할 수 없다. Iterator 를 통해 순회의 대상이 되는 자료 구조를 만들어보자. 여기서는 매우 간단한 자료 구조를 하나 만들자. 내부에는 숫자 배열을 보관한다.

• 배열을 가지는 매우 단순한 자료 구조이다.

• Iterable 인터페이스를 구현한다.

  • 이 인터페이스는 이 자료 구조에 사용할 반복자( Iterator )를 반환하면 된다.

  • 앞서 만든 반복자인 MyArrayIterator 를 반환한다.

  • 이때 MyArrayIterator 는 생상자를 통해 MyArray 의 내부 배열인 numbers 를 참조한다.

package collection.iterable;

import java.util.Iterator;

public class MyArray implements Iterable<Integer> {

    private int[] numbers;

    public MyArray(int[] numbers) {
        this.numbers = numbers;
    }

    @Override
    public Iterator<Integer> iterator() {
        return new MyArrayIterator(numbers);
    }
}

MyArray 는 Iterable (반복할 수 있는) 인터페이스를 구현한다. 따라서 MyArray 는 반복할 수 있다는 의미가 된다.Iterable 인터페이스를 구현하면 iterator() 메서드를 구현해야 한다.

이 메서드는 Iterator 인터페이 스를 구현한 반복자를 반환한다. 여기서는 MyArrayIterator 를 생성해서 반환했다.

package collection.iterable;

import java.util.Iterator;

public class MyArrayMain {

    public static void main(String[] args) {

        MyArray myArray = new MyArray(new int[]{1, 2, 3, 4, 5});

        System.out.println("==iterator 사용==");
        Iterator<Integer> iterator = myArray.iterator();
        while (iterator.hasNext()) {
            Integer value = iterator.next();
            System.out.println("value = " + value);
        }
        
        // 향상된 for문
        System.out.println("==for-each 사용==");
        for (Integer value : myArray) {
            System.out.println("value = " + value);
        }
    }
}

순회2 - 향상된 for문

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

Iterable , Iterator 를 사용하면 또 하나의 큰 장점을 얻을 수 있다. 다음 코드를 보자.

// 향상된 for문
System.out.println("==for-each 사용==");
for (Integer value : myArray) {
    System.out.println("value = " + value);
}

for-each 로 불리는 향상된 for 문은 자료 구조를 순회하는 것이 목적이다. 자바는 Iterable 인터페이스를 구현한 객체에 대해서 향상된 for 문을 사용할 수있도록 해준다.

실제 위 코드는 컴파일 시점에 컴파일러가 다음과 같이 코드를 변경해준다.

while (iterator.hasNext()) {
      Integer value = iterator.next();
      System.out.println("value = " + value);
}

따라서 두 코드는 같은 코드이다. 물론 모든 데이터를 순회한다면 둘 중에 깔끔한 향상된 for문을 사용하는 것이 좋다.

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

• 자바 컬렉션 프레임워크는 배열 리스트, 연결 리스트, 해시 셋, 연결 해시 셋, 트리 셋 등등 다양한 자료 구조를 제공한다.

• 자바는 컬렉션 프레임워크를 사용하는 개발자가 편리하고 일관된 방법으로 자료 구조를 순회할 수 있도록 Iterable 인터페이스를 제공하고, 이미 각각의 구현체에 맞는 Iterator 도 다 구현해두었다.

• 자바 Collection 인터페이스 상위에 Iteratble 이 있다는 것은 모든 컬렉션을 Iterable 과 Iterator 를 사용해서 순회할 수 있다는 뜻이다.

• Map의 경우 Key 뿐만아니라 Value 까지 있기 때문에 바로 순회를 할 수는 없다.

• 대신에 Key 나 Value 를 정해서 순회할 수 있는데, keySet() , values() 를 호출하면 Set , Collection 을 반환하기 때문에 Key 나 Value 를 정해서 순회할 수 있다. 물론 Entry 를 Set 구조로 반환하는 entrySet() 도 순회가 가능하다.

정리하면 자바가 제공하는 컬렉션 프레임워크의 모든 자료 구조는 Iterable 과 Iterator 를 사용해서 편리하고 일 관된 방법으로 순회할 수 있다. 물론 Iterable 을 구현하기 때문에 향상된 for문도 사용할 수 있다.

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

정렬1 - Comparable, Comparator

배열에 들어있는 데이터를 순서대로 정렬하는 방법

• Arrays.sort() 를 사용하면 배열에 들어있는 데이터를 순서대로 정렬할 수 있다. 원래 3, 2, 1 순서로 데이터가 들어있었는데, 정렬 후에는 1, 2, 3의 순서로 데이터가 정렬된 것을 확인할 수 있다.

• 실제로 정렬 성능을 높이기 위한 다양한 정렬 알고리즘이 존재한다. 자바는 초기에는 퀵소트를 사용했다가 지금은 데이터가 작을 때(32개 이하)는 듀얼 피벗 퀵소트(Dual-Pivot QuickSort)를 사용하고, 데이터가 많을 때는 팀소트(TimSort)를 사용한다. 지금은 기본형 배열의 경우 듀얼 피벗 퀵 소트(Dual-Pivot QuickSort)를 사용하고, 객체 배열의 경우 팀소트(TimeSort)를 사용한다. 이런 알고리즘은 평균 O(n log n)의 성능을 제공한다.

package collection.compare;

import java.util.Arrays;

public class SortMain1 {

    public static void main(String[] args) {
        Integer[] array = {3, 2, 1};
        System.out.println(Arrays.toString(array));

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

비교자 - Comparator

그런데 정렬을 할 때 1, 2, 3 순서가 아니라 반대로 3, 2, 1로 정렬하고 싶다면 어떻게 해야할까? 이때는 비교자( Comparator )를 사용하면 된다. 이름 그대로 두 값을 비교할 때 비교 기준을 직접 제공할 수 있다.

• 두 인수를 비교해서 결과 값을 반환하면 된다.

  • 첫 번째 인수가 더 작으면 음수, 예(-1 )

  • 두 값이 같으면 0

  • 첫 번째 인수가 더 크면 양수, 예( 1 )

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

package collection.compare;

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 DescComparator());
        System.out.println("DescComparator = " + Arrays.toString(array));
        Arrays.sort(array, new AscComparator().reversed());
        System.out.println("AscComparator().reversed() = " + Arrays.toString(array));
    }

    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);
        }
    }

    static class DescComparator 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)) * -1;
        }
    }
}

정렬2 - Comparable, Comparator

자바가 기본으로 제공하는 Integer , String 같은 객체를 제외하고 MyUser 와 같이 직접 만든 객체를 정렬하려면 어떻게 해야 할까? 내가 만든 객체이기 때문에 정렬을 할 때 내가 만든 두 객체 중에 어떤 객체가 더 큰지 알려줄 방법이 있어야 한다.

이때는 Comparable 인터페이스를 구현하면 된다. 이 인터페이스는 이름 그대로 비교 가능한, 비교할 수 있는 이라는 뜻으로, 객체에 비교 기능을 추가해 준다.

public interface Comparable<T> {
      public int compareTo(T o);
}

package collection.compare;

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 String toString() {
        return "MyUser{" +
                "id='" + id + '\'' +
                ", age=" + age +
                '}';
    }

    @Override
    public int compareTo(MyUser o) {
        return this.age < o.age ? -1 : (this.age == o.age ? 0 : 1);
    }
}

package collection.compare;

import java.util.Arrays;

public class SortMain3 {

    public static void main(String[] args) {
        MyUser myUser1 = new MyUser("A", 30);
        MyUser myUser2 = new MyUser("B", 20);
        MyUser myUser3 = new MyUser("C", 10);

        MyUser[] array = {myUser1, myUser2, myUser3};
        System.out.println("기본 데이터");
        System.out.println(Arrays.toString(array));

        System.out.println("정렬 후 데이터");
        Arrays.sort(array);
        System.out.println(Arrays.toString(array));
    }
}

Arrays.sort(array)

기본 정렬을 시도한다. 이때는 객체가 스스로 가지고 있는 Comparable 인터페이스를 사용해서 비교한다. MyUser 가 구현한 대로 나이( age ) 오름차순으로 정렬된 것을 확인할 수 있다. MyUser 의 자연적인 순서를 사용했다.

다른 방식으로 정렬

만약 객체가 가지고 있는 Comparable 기본 정렬이 아니라 다른 정렬을 사용하고 싶다면 어떻게 해야할까? 나이가 아니라 아이디로 비교하는 예제를 추가로 만들어보자.

package collection.compare;

import java.util.Comparator;

public class IdComparator implements Comparator<MyUser> {

    @Override
    public int compare(MyUser o1, MyUser o2) {
        return o1.getId().compareTo(o2.getId());
    }
}

package collection.compare;

import java.util.Arrays;

public class SortMain3 {

    public static void main(String[] args) {
        MyUser myUser1 = new MyUser("A", 30);
        MyUser myUser2 = new MyUser("B", 20);
        MyUser myUser3 = new MyUser("C", 10);

        MyUser[] array = {myUser1, myUser2, myUser3};
        System.out.println("기본 데이터");
        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));
    }
}

Array.sort(array, Comparator)

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

여기서는 기본으로 나이를 기준으로 정렬하지만, 아이디로 정렬하고 싶다면 IdComparator 를 넘겨주면 된다. 결과를 보면 아이디( id ) 순으로 정렬된 것을 확인 할 수 있다.

정렬3 - Comparable, Comparator

정렬은 배열 뿐 아니라, 순서가 있는 List 같은 자료 구조에도 사용할 수 있다.

List 와 정렬

package collection.compare;

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

public class SortMain4 {

    public static void main(String[] args) {
        MyUser myUser1 = new MyUser("A", 30);
        MyUser myUser2 = new MyUser("B", 20);
        MyUser myUser3 = new MyUser("C", 10);

        List<MyUser> list = new LinkedList<>();
        list.add(myUser1);
        list.add(myUser2);
        list.add(myUser3);
        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);

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

Collections.sort(list)

• 리스트는 순서가 있는 컬렉션이므로 정렬할 수 있다.

• 이 메서드를 사용하면 기본 정렬이 적용된다.

• 하지만 이 방식보다는 객체 스스로 정렬 메서드를 가지고 있는 list.sort() 사용을 더욱 권장한다. (참고로 둘의 결과는 같다)

list.sort(null)

• 별도의 비교자가 없으므로 Comparable 로 비교해서 정렬한다.

• 자연적인 순서로 비교한다.

• 자바 1.8 부터 사용

Collections.sort(list, new IdComparator())

• 별도의 비교자로 비교하고 싶다면 다음 인자에 비교자를 넘기면 된다.

• 하지만 이 방식보다는 객체 스스로 정렬 메서드를 가지고 있는 list.sort() 사용을 더 권장한다. (참고로 둘의 결과는 같다)

list.sort(new IdComparator())

• 전달한 비교자로 비교한다.

• 자바 1.8 부터 사용

Tree 구조와 정렬

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

이진 탐색 트리는 데이터를 저장할 때 왼쪽 노드에 저장해야 할 지, 오른쪽 노드에 저장해야 할 지 비교가 필요하다. 따라서 TreeSet , TreeMap 은 Comparable 또는 Comparator 가 필수이다.

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

• 만약 Comparable 도 구현하지 않고, Comparator 도 제공하지 않으면 다음과 같은 런타임 오류가 발생한다.

  

package collection.compare;

import java.util.Set;
import java.util.TreeSet;

public class SortMain5 {

    public static void main(String[] args) {
        MyUser myUser1 = new MyUser("A", 30);
        MyUser myUser2 = new MyUser("B", 20);
        MyUser myUser3 = new MyUser("C", 10);

        Set<MyUser> treeSet1 = new TreeSet<>();
        treeSet1.add(myUser1);
        treeSet1.add(myUser2);
        treeSet1.add(myUser3);

        System.out.println("Comparable 기본 정렬");
        System.out.println(treeSet1);

        Set<MyUser> treeSet2 = new TreeSet<>(new IdComparator());
        treeSet2.add(myUser1);
        treeSet2.add(myUser2);
        treeSet2.add(myUser3);
        System.out.println("IdComparator 기본 정렬");
        System.out.println(treeSet2);

        Set<MyUser> treeSet3 = new TreeSet<>(new IdComparator().reversed());
        treeSet3.add(myUser1);
        treeSet3.add(myUser2);
        treeSet3.add(myUser3);
        System.out.println("IdComparator.reversed() 기본 정렬");
        System.out.println(treeSet3);

    }
}

컬렉션 유틸

정렬

package collection.utils;

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

public class CollectionsSortMain {

    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);
    }
}

편리한 컬렉션 생성

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

• 불변 컬렉션은 변경할 수 없다. 변경 메서드를 호출하면 UnsupportedOperationException 예외가 발생 한다.

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 class = " + list.getClass());
        System.out.println("set class = " + set.getClass());
        System.out.println("map class = " + map.getClass());
    }
}

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

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);
        
        // 가변 리스트 변경
        List<Integer> mutableList = new ArrayList<>(list);
        mutableList.add(4);
        System.out.println("mutableList = " + mutableList);
        System.out.println("mutableList class = " + mutableList.getClass());

        // 불변 리스트 변경
        List<Integer> immutableList = Collections.unmodifiableList(mutableList);
        System.out.println("immutableList = " + immutableList);
        System.out.println("immutableList class = " + immutableList.getClass());
    }
}

빈 리스트 생성

• 빈 리스트는 원하는 컬렉션의 구현체를 직접 생성하면 된다. 빈 불변 리스트는 2가지 생성 방법이 있다.

  • Collections.emptyList() : 자바5부터 제공되는 기능이다.

  • List.of() : 자바9부터 제공되는 최신 기능이다.

  • List.of() 가 더 간결하고, List.of(1,2,3) 도 불변이기 때문에 사용법에 일관성이 있다. 자바 9 이상을 사용한다면 이 기능을 권장한다.

package collection.utils;

import java.util.*;

public class EmptyListMain {

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

        List<Integer> list3 = Collections.emptyList();  // 자바5
        List<Integer> list4 = List.of();                // 자바9

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

멀티스레드 동기화

• Collections.synchronizedList 를 사용하면 일반 리스트를 멀티스레드 상황에서 동기화 문제가 발생하 지 않는 안전한 리스트로 만들 수 있다.

• 동기화 작업으로 인해 일반 리스트보다 성능은 더 느리다.

package collection.utils;

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

public class SyncMain {

    public static void main(String[] args) {

        List<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());
    }
}