순회, 정렬

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

 

각각의 자료 구조마다 순회 방법이 모두 다르다.

↓

모든 자료 구조를 동일한 방법으로 순회할 수 있다면 편리할 것이다. 

↓

자바는 이를 위해 Iterable과 Iterator 인터페이스를 제공한다.

 

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

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

 

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

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

 

정리해보면,

자료 구조에 다음 요소가 있는지 묻는다

->있으면 다음 요소를 꺼내는 과정을 반복

->없으면 종료

 

코드 구현

Iterator 구현체

import java.util.Iterator;
public class MyArrayIterator implements Iterator<Integer> {
    private int currentIndex = -1;
    private int[] targetArr;
    public MyArrayIterator(int[] targetArr) {
        this.targetArr = targetArr;
    }
    @Override
    public boolean hasNext() {
        return currentIndex < targetArr.length - 1;
    }
    @Override
    public Integer next() {
        return targetArr[++currentIndex];
    }
}

 

Iterator을 통해 순회의 대상이 되는 자료구조

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

 

클래스 구조도

런타임 메모리 구조도

 

2. 순회2 - Iterable과 향상된 for문  

 

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

for (int value : myArray) {
        System.out.println("value = " + value);
}

 

이렇게 하면 자바는 컴파일 시점에 코드를 아래와 같이 변경한다.

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

MyArray는 Iterable을 구현했다. -> MyArray는 반복 가능하다.

-> MyArray는 iterator를 반환하고, for-each문도 작동한다.

 

정리하자면, 

• Iterable: 반복할 수 있는 객체. for-each문 사용 가능
• Iterator: 실제로 하나씩 꺼내는 역할을 하는 객체. hasNext()와 next() 메서드를 가짐.

즉, Iterable은 반복 가능한 "자료구조", Iterator는 반복을 수행하는 "기능" 이다.

특정 자료 구조가 Iterable, Iterator를 구현한다면, 단순히 hasNext(), next(), for-each 문을 사용해서 순회할 수 있다.

(인터페이스가 주는 큰 장점)

 

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

• 자바가 제공하는 컬렉션 프레임워크의 모든 자료 구조는 Iterable과 Iterator를 사용해서 편리하고 일관된 방법으로 순회할 수 있다.
• Map은 key, value가 있기 때문에 바로 순회 불가능
  -> keySet() , values(), entrySet() 순회 가능

예시 코드

import java.util.*;
public class JavaIterableMain {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        Set<Integer> set = new HashSet<>();
        set.add(1);
        set.add(2);
        set.add(3);
        printAll(list.iterator());
        printAll(set.iterator());
        foreach(list);
        foreach(set);
    }
    private static void printAll(Iterator<Integer> iterator) {
        System.out.println("iterator = " + iterator.getClass());
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }
    }
    private static void foreach(Iterable<Integer> iterable) {
        System.out.println("iterable = " + iterable.getClass());
        for (Integer i : iterable) {
            System.out.println(i);
        }
    }
}

 

4. 정렬 - Comparable, Comparator

 

4.1 Comparator

Arrays.sort()를 사용하면 배열에 들어있는 데이터를 순서대로 정렬할 수 있다.

 

Comparator(비교자)

Comparator를 사용하면 정렬의 기준을 자유롭게 변경할 수 있다.

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

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

• 첫 번째 인수가 더 작으면 음수, 예(-1)
• 두 값이 같으면 0
• 첫 번째 인수가 더 크면 양수, 예(1)

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()); //DescComparator와
        같다.
                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;
        }
    }
}

• new AscComparator().reversed() -> 정렬을 반대로 해준다.

 

4.2 Comparable

자바가 기본으로 제공하는 Integer, String 같은 객체를 제외하고 MyUser와 같이 직접 만든 객체를 정렬하려면 어떻게 해야 할까?

-> 내가 만든 객체이기 때문에 어떤 객체가 더 큰지 알려줄 방법이 있어야 한다.

이때는 Comparable 인터페이스를 구현하면 된다. 

 

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

자기 자신과 인수로 넘어온 객체를 비교해서 반환하면 된다.

• 현재 객체가 인수로 주어진 객체보다 더 작으면 음수, 예(-1)
• 두 객체의 크기가 같으면 0
• 현재 객체가 인수로 주어진 객체보다 더 크면 양수, 예(1)

 

코드 구현

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) {
        return this.age < o.age ? -1 : (this.age == o.age ? 0 : 1);
    }
    @Override
    public String toString() {
        return "MyUser{" +
                "id='" + id + '\'' +
                ", age=" + age +
                '}';
    }
}

• Comparable을 통해 구현한 순서를 자연 순서라 한다.

 

Arrays.sort(array)

기본 정렬을 시도한다.

이때는 객체가 스스로 가지고 있는 Comparable 인터페이스를 사용해서 비교한다.

 

Arrays.sort(array, Comparator)

기본 정렬이 아니라 정렬 방식을 지정하고 싶다면 Arrays.sort의 인수로 비교자 Comparator를 만들어서 넘겨주면 된다.

이렇게 비교자를 따로 전달하면 객체가 기본으로 가지고 있는 Comparable을 무시하고,

별도로 전달한 비교자를 사용해서 정렬한다.

 

주의! 만약 Comparable, Comparator을 제공하지 않으면 런타임 오류가 발생한다.

 

Comparable, Comparator 정리

객체의 기본 정렬 방법 -> Comparable를 구현

기본 정렬 외에 다른 정렬 방법 -> Comparator를 별도로 구현, 이 경우 Comparator가 항상 우선권을 가짐

 

4.3 List에 정렬 사용하기

List와 정렬 

import java.util.*;
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);
    }
}

• Collections.sort(list) -> list.sort() 사용 권장
• list.sort(null) -> Comparable로 정렬, 자연적인 순서로 비교
• Collections.sort(list, new IdComparator()) -> list.sort() 사용 권장
• list.sort(new IdComparator()) -> 전달한 비교자로 비교

 

Tree 구조와 정렬

이진 탐색 트리 구조는 데이터를 정렬하면서 보관하므로, Comparable 또는 Comparator 가 필수이다.

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);
        TreeSet<MyUser> treeSet1 = new TreeSet<>();
        treeSet1.add(myUser1);
        treeSet1.add(myUser2);
        treeSet1.add(myUser3);
        System.out.println("Comparable 기본 정렬");
        System.out.println(treeSet1);
        TreeSet<MyUser> treeSet2 = new TreeSet<>(new IdComparator());
        treeSet2.add(myUser1);
        treeSet2.add(myUser2);
        treeSet2.add(myUser3);
        System.out.println("IdComparator 정렬");
        System.out.println(treeSet2);
    }
}

정리하면,

객체의 정렬이 필요 -> Comparable(기본 자연 순서를 제공)

자연 순서 외에 다른 정렬 기준이 추가로 필요 -> Comparator

 

5. 컬렉션 유틸  

Collections 정렬 관련 메서드

• max : 최대 값을 찾아서 반환
• min : 최소 값을 찾아서 반환
• shuffle : 컬렉션을 랜덤하게 섞는다.
• sort : 정렬 기준으로 컬렉션을 정렬
• reverse : 정렬 기준의 반대로 컬렉션을 정렬(컬렉션에 들어있는 결과를 반대로 정렬)

 

List.of(...)

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

 

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

• 불변 리스트 -> 가변 리스트
  new ArrayList<>()
• 가변 리스트 -> 불변 리스트
  Collections.unmodifiableList()

 

빈 리스트 생성

빈 가변 리스트는 원하는 컬렉션의 구현체를 직접 생성하면 된다.

List.of() -> 권장

Arrays.asList() -> 고정된 크기를 가지지만, set()을 통해 요소들은 변경할 수 있다.

 

멀티 스레드 동기화

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