[JAVA] 순회와 정렬

순회란?

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

ArrayList, LinkedList, HashSet, Set, Tree 등 다양한 자료구조가 있는데 각 자료구조마다 순회하는 방법이 모두 다르기 때문에 자바는 자료구조의 구현과 상관없이 모든 자료 구조를 동일한 방법으로 순회할 수 있는 Iterable, Iterator 인터페이스를 제공한다.

Iterable, Iterator

Iterable = 반복 가능한

Iterator = 반복자

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

• Iterator 반복자를 반환

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

    E next();
}

• hasNext() = 다음 요소가 있는지 확인 후 없으면 false
• next() = 다음 요소 확인 후 내부 위치를 다음으로 이동

구현체 만들기

Iterator

public class MyArrayIterator implements Iterator<Integer> {

    private int currentIndex = -1; //호출 증가용
    private int[] targetArr; // 2. {1,2,3,4} 넘긴걸 targetArr로 가지고 있다.

    public MyArrayIterator(int[] targetArr) {
		    //3. 생성자를 통해 반복자가 사용할 배열 참조
		    //여기서 참조한 배열을 순회
        this.targetArr = targetArr;
    }

    @Override
    public boolean hasNext() {
		    //다음 항목 있는지? 배열 끝에서 false 반환
        return currentIndex < targetArr.length - 1;
    }

    @Override
    public Integer next() {
		    //다음 항목 반환
        return targetArr[++currentIndex];
    }
}

• Iterator 는 단독 사용 불가. 순회의 대상 MyArray를 만들어보자

public class MyArray implements Iterable<Integer>{

    private int[] number;

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

    //구현은 해야함
    @Override
    public Iterator<Integer> iterator() {
        return new MyArrayIterator(number); //1. 이거를 생성자를 넘겨서
    }
}

• Iterator 인터페이스를 구현
• MyArrayIterator 인스턴스는 내부에서 MyArray 배열을 참조
• MyArrayIterator 를 통해 MyArray 가 가진 내부 데이터 순회 가능

public class MyArrayMain {
    public static void main(String[] args) {
        MyArray array = new MyArray(new int[]{1,2,3,4});

        Iterator<Integer> iterator = array.iterator(); //반복자를 반환
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }

        System.out.println("for-each 사용");
        for(int value : array) {
	         System.out.println("value = " + value);
	      }
    }
}
//실행결과
1
2
3
4
for-each 사용
value = 1
value = 2
value = 3
value = 4

• MyArray는 Iterable(반복할 수 있는) 인터페이스를 구현 따라서 반복할 수 있다.
• Iterable 인터페이스를 구현하면 iterator() 메서드 구현해야 한다. Iterator 인터페이스를 구현한 반복자 반환 즉 MyArrayIterator를 생성해 반환

자바가 제공하는 Iterable, Iterator

• 자바는 컬렉션 프레임 워크를 사용하는 개발자가 편리하고 일관된 방법으로 자료 구조를 순회할 수 있도록 Iterable 인터페이스를 제공하고, 이미 각각의 구현체에 맞는 Iterator 도 구현해두었다.
• 컬렉션 인터페이스 상위에 Iterable 이 있다는 건, 모든 컬렉션에서 Iterable 과 Iterator 를 사용해 순회할 수 있다는 뜻이다.
• 하지만 Map의 경우는 Key 뿐만 아니라 Value 까지 있기 때문에 바로 순회할 수 없다. Key나 Value를 정해서 순회할 수 있다.

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

        printList(list.iterator());

        System.out.println();

        HashSet<Integer> set = new HashSet<>();
        set.add(1);
        set.add(2);
        set.add(3);

        printList(set.iterator());

        foreach(list);
        foreach(set);
    }

    private static void foreach(Iterable<Integer> iterable) {
        for (Integer i : iterable) {
            System.out.print(i + " ");
        }
    }

    private static void printList(Iterator<Integer> list) {
        System.out.println("iterator = " + list.getClass());
        while (list.hasNext()) {
            System.out.print(list.next() + " ");
        }
    }

}
//출력결과
iterator = class java.util.ArrayList$Itr
1 2 3 
iterator = class java.util.HashMap$KeyIterator
1 2 3 1 2 3 1 2 3 

• Iterator, Iterable 은 인터페이스라 다형성을 활용할 수 있다.
• HashSet 자료 구조는 내부에서 HashMap 자료 구조를 사용한다. HashMap 자료 구조에서 Value를 사용하지 않으면 HashSet과 같다.

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

정렬 - Comparable, Comparator

배열에 들어있는 데이터를 순서대로 정렬해보자.

public class SortMain1 {
    public static void main(String[] args) {
        Integer[] arr = {3,2,1,4,5,35,23,77,498,264};
        System.out.println(Arrays.toString(arr));

        System.out.println("기본 정렬 후");
        Arrays.sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
//출력결과
[3, 2, 1, 4, 5, 35, 23, 77, 498, 264]
기본 정렬 후
[1, 2, 3, 4, 5, 23, 35, 77, 264, 498]

비교자 - Comparator

반대로 정렬하고 싶다면? 두 값을 비교할 때 비교 기준을 직접 제공할 수 있다.

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

        System.out.println("Comparator 비교");
        Arrays.sort(arr, new AscCompartor());
        System.out.println("AscCompartor: " + Arrays.toString(arr));

        Arrays.sort(arr, new DescCompartor());
        System.out.println("DescComparator: " + Arrays.toString(arr));

        Arrays.sort(arr, new AscCompartor().reversed()); //Desc와 같다
        System.out.println("reversed: " + Arrays.toString(arr));

    }

    public static class DescCompartor 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;
        }
    }

    public static class AscCompartor 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
AscCompartor: [1, 2, 3]
o1 = 2, o2 = 1
o1 = 3, o2 = 2
DescComparator: [3, 2, 1]
o1 = 3, o2 = 2
o1 = 2, o2 = 1
reversed: [3, 2, 1]

• 첫 번째 인수가 더 작으면 음수 → -1
• 두 값이 같으면 → 0
• 첫 번쨰 인수가 더 크면 양수 → 1
• Arrays.sort() 를 사용할 때 Comparator(비교자)를 넘겨주면 알고리즘에서 어떤 값이 더 큰지 두 값을 비교할 때, 비교자를 사용한다.

Arrays.sort(arr, new AscCompartor()); // 오름차순 정렬
Arrays.sort(arr, new DescCompartor()); //내림차순 정렬 구현체의 마지막에 -1을 곱해주었기 때문에 반대로
Arrays.sort(arr, new AscCompartor().reversed()); //정렬을 반대로

객체 정렬

Comparable 인터페이스를 구현해 객체에 비교 기능을 추가해 준다.

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);
        //내 나이가 비교하는 나이보다 작으면 -1, 또는 같으면 0 아니면 1
    }

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

• 자기 자신과 인수로 넘어온 객체를 비교해 반환
  • 현재 객체가 인수로 주어진 객체보다 작으면 음수 = -1
  • 두 객체의 크기가 같으면 = 0
  • 현재 객체가 인수로 주어진 객체보다 크면 양수 = 1
• 정렬의 기준을 age(나이) 오름차순으로 기본정렬 방식을 정했다.

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("Comparable 기본정렬"); //나이 오름차순 10, 20, 30

        Arrays.sort(array); //기본 정렬 -> 객체가 스스로 가지고 있는 Comparable 인터페이스를 사용해 비교
        System.out.println(Arrays.toString(array));

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

        System.out.println("id Comparator reversed 정렬");
        Arrays.sort(array, new IdComparator().reversed());
        System.out.println(Arrays.toString(array));
    }
}
//출력결과
기본 데이터
[MyUser{id='a', age=30}, MyUser{id='b', age=20}, MyUser{id='c', age=10}]
Comparable 기본정렬
[MyUser{id='c', age=10}, MyUser{id='b', age=20}, MyUser{id='a', age=30}]
id Comparator 정렬
[MyUser{id='a', age=30}, MyUser{id='b', age=20}, MyUser{id='c', age=10}]
id Comparator reversed 정렬
[MyUser{id='c', age=10}, MyUser{id='b', age=20}, MyUser{id='a', age=30}]

ID로 비교

public class IdComparator implements Comparator<MyUser> {

    @Override
    public int compare(MyUser o1, MyUser o2) {
        return o1.getId().compareTo(o2.getId()); //아이디를 기준으로 정렬
    }
}

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

• 결과는 같지만 객체 스스로 정렬 메서드를 가지고 있는 list.sort(); 사용을 권장

Tree 구조와 정렬

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

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> set1 = new TreeSet<>(); //들어가는 순간 저장
        set1.add(myUser1);
        set1.add(myUser2);
        set1.add(myUser3);
        System.out.println("Comparable 기본 정렬");
        System.out.println(set1);

        TreeSet<MyUser> set2 = new TreeSet<>(new IdComparator()/*.reversed()*/);
        set2.add(myUser1);
        set2.add(myUser2);
        set2.add(myUser3);
        System.out.println("idComparator 정렬");
        System.out.println(set2);
    }
}

컬렉션 유틸

정렬

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);
        Collections.sort(list); //정렬
        System.out.println("sort: " + list);
        Collections.reverse(list);
        System.out.println("reverse: " + list);
    }
}

//출력결과
max: 5
min: 1
list: [1, 2, 3, 4, 5]
shuffle: [2, 1, 5, 4, 3]
sort: [1, 2, 3, 4, 5]
reverse: [5, 4, 3, 2, 1]

생성

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

        /*list.add(1);*/ //불변이라 못넣음
        /*list.set(3,"asdasd");*/

        System.out.println("list: " + list);
        System.out.println("set: " + set);
        System.out.println("map: " + map);
        System.out.println("list class: " + list.getClass());
    }
}

//출력결과
list: [1, 2, 3]
set: [3, 2, 1]
map: {2=two, 1=one}
list class: class java.util.ImmutableCollections$ListN

• List.of(…) 를 사용해 불변 컬렉션을 생성할 수 있다. 불변 컬렉션은 변경할 수 없다.

불변과 가변

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

        //다시 불변리스트로
        Collection<Integer> unmodifiableList = Collections.unmodifiableCollection(list);
        System.out.println("unmodifiableList: " + unmodifiableList);
        /*unmodifiableList.add(4); //예외 터짐 */
    }
}

• 불변 → 가변 new ArrayList<>() 를 사용
• 가변 → 불변 Collections.unmodifiableCollection()를 사용

빈 리스트 생성

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 = " + list3.getClass());
        System.out.println("list4 = " + list4.getClass());
    }
}

멀티스레드 동기화

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

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

인터페이스

자바 컬렉션 프레임워크의 인터페이스들

• Collection: 단일 루트 인터페이스, 모든 컬렉션 클래스가 이 인테페이스를 상속받는다. (List, Set, Queue)
• List: 순서가 있고 중복을 허용한다. 인덱스를 통해 요소에 접근할 수 있다 ( ArrayList, LinkedList)
• Set: 중복을 허용하지 않고 특정 위치가 없어 인덱스를 통해 요소에 접글할 수 없다. (HashSet, LinkedHashSet, TreeSet)
• Queue: 요소가 처리되기 전에 보관되는 컬렉션 (ArrayDeque, LinkedList, PriorityQueue)
• Map: 키와 값 쌍으로 요소를 저장, Map은 Collection 인터페이스를 상속받지 않는다. (HashMap, LinkedHashMap, TreeMap)

구현

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

선택 가이드

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

실무 선택 가이드

• List → ArrayList
• Set → HashSet
• Map → HashMap
• Queue → ArrayDeque

만드는 사람이 수고로우면 쓰는 사람이 편하고, 만드는 사람이 편하면 쓰는 사람이 수고롭다.

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