[Java] 컬렉션 프레임워크 - 컬렉션 기반 알고리즘

정렬

List 인터페이스를 구현한 클래스들은 정렬된 상태로 유지하지 않는다. 

public static <T extends Comparable<? super T>> void sort(List<T> list)

위 메서드는 Collections 클래스에 정의되어 있는 제네릭 메서드로, 정렬을 해야할 때 사용한다. 인자로 List<T>의 인스턴스를 모두 받지만, T는 Comparable<T> 인터페이스를 구현한 상태여야 한다. 내부적으로 Comparable<T> 의 compareTo를 사용하여 정렬이 시행된다.

이때, Comparable<T> 가 아닌 Comparable<? super T> 인 이유는 상속과 관련이 있다. 

class Car implements Comparable<Car> { ... }
class ECar extends Car { ... }

List<ECar> elist = new ArrayList<>();
Collections.sort(elist); //가능

Car 클래스를 상속하는 ECar 클래스가 있다고 하자. 만약 Comparable<T> 였다면 ECar 는 Comparable<ECar>를 구현해야 하므로 sort 메서드 호출이 불가능하다. Comparable<? super T> 인 경우 ECar은 Comparable<? super ECar> 를 구현해야하는데,  Comparable<Car>를 간접 구현하기 때문에 sort 메서드 호출이 가능하다. 

 

public static <T> void sort(List<T> list, Comparator<? super T> c)

Collections 클래스에는 Comparator<T>를 사용해 정렬의 기준을 결정할 수 있는 메서드도 존재한다. 

class CarComp implements Comparator<Car> { ... }

List<ECar> elist = new ArrayList<>();
Collections.sort(elist, new CarComp()); // 가능

위와 같은 이유로 Comparator<T> 가 아닌 Comparator<? super T> 이므로, Car를 상속한 ECar 또한 sort 메서드 호출이 가능하다. 

 

찾기

List 자료구조 기반으로 특정 인스턴스를 찾을 때 사용할 수 있는 메서드가 있다. 

public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key);

binarySearch 메서드는 list에서 key를 찾아 그 인덱스 값을 반환하고, 못 찾으면 음의 정수를 반환한다. 이진 탐색 알고리즘을 기반으로 탐색을 진행하는데, 이 알고리즘은 정렬된 상태에서 사용 가능하다. 따라서 binarySearch 호출 이전에 리스트를 반드시 정렬해야 한다. 만약 정렬하지 않은 채 호출한다면 비정상적인 결과를 반환할 수 있다.

List 의 타입 인자는 Comparable<T>를 직/간접 구현한 클래스여야 한다.

 

public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c);

Collections 클래스에는 Comparator<T>를 사용해 정렬의 기준을 결정할 수 있는 메서드도 존재한다.

List<? extends T> 이기 때문에 T형 인스턴스를 get만 가능하고, Comparator<? super T> 이기 때문에 T의 상위 클래스 중 하나가 Comparator를 구현해야 한다.

 

복사하기

List 자료구조의 인스턴스에 저장된 내용을 복사하는 기능의 메서드이다. 

public static <T> void copy(List<? super T> dest, List<? extends T> src);

copy 메서드는 src의 내용을 dest로 복사한다. List<? super T> dest 인 이유는 set 만을 허용하기 때문이고, List<? extends T> src 인 이유는 get 만을 허용하기 때문이다. 

List<String> src = Arrays.asList(...);

List<String> dest = new ArrayList<>(src);	// 얕은 복사
Collections.copy(dest, src);			// 깊은 복사

추가로 위의 방법은 얕은 복사(shallow copy)지만 아래 방법은 깊은 복사(deep copy)이다. 

 

이외에도 많은 기능들이 Collections 클래스에 구현되어있다.

 

 

 

참조
윤성우의 열혈 JAVA  프로그래밍