순회란?
자료구조에서의 순회는 자료구조에 들어있는 데이터를 차례대로 접근해 처리하는 것을 순회라 한다.
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()= 다음 요소가 있는지 확인 후 없으면 falsenext()= 다음 요소 확인 후 내부 위치를 다음으로 이동
구현체 만들기
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→ArrayListSet→HashSetMap→HashMapQueue→ArrayDeque
만드는 사람이 수고로우면 쓰는 사람이 편하고, 만드는 사람이 편하면 쓰는 사람이 수고롭다.
···