프레임워크는 잘 정의된 구조 또는 골격을 뜻하며 자바에서 말하는 프레임워크는 잘 정의된 구조의 클래스들을 뜻함
즉 프로그래머들이 쓸 수 있도록 잘 정의된 클래스들의 모임
컬렉션 프레임워크는 데이터의 저장 방법, 그리고 이와 관련 있는 알고리즘에 대한 프레임워크를 뜻함
또는 자료구조와 알고리즘을 제네릭 기반의 클래스와 메소드로 미리 구현해 놓은 결과물이라고 할 수 있음
이로 인해 자료구조를 몰라도 트리 기반으로 데이터를 저장할 수 있고, 알고리즘을 몰라도 이진 탐색을 수행할 수 있음
예) 자료구조 : 리스트, 스택, 큐, 트리, 해쉬 / 알고리즘 : 버블 정렬, 퀵 정렬, 이진 탐색 등
컬렉션 프레임워크의 기본 골격
컬렉션 클래스들이 구현하는 인터페이스들의 상속 관계는 다음과 같으며, 모든 인터페이스는 제네릭으로 정의되어 있음
인스턴스를 저장하는 컬렉션 클래스들은 이 인터페이스 중 하나를 구현하게 되며, 구현한 인터페이스에 따라서 컬렉션 클래스의 데이터 저장 방식이 결정됨
컬렉션 프레임워크의 인터페이스 구조
✔ List<E> 인터페이스를 구현하는 컬렉션 클래스들
List<E> 인터페이스를 구현하는 대표적인 컬렉션 클래스
ArrayList<E>와 LinkedList<E>가 존재
이들은 인스턴스의 저장 순서를 유지하며, 동일한 인스턴스의 중복 저장을 허용함
둘은 기능적 측면에서 보면 동일하지만 인스턴스를 저장하는 방식에 차이가 있음
import문 구성시에는 클래스의 이름만 명시하도록 함
List<E>형 참조변수로 선언할 경우, 컬렉션 클래스의 교체가 용이해지는 코드 유연성을 제공할 수 있음
인스턴스 저장 : add() 메소드의 인자를 통해 저장할 인스턴스를 전달하면, 인스턴스의 참조 값이 전달됨
저장된 인스턴스 수 : size() 메소드 호출
인스턴스 참조 : get() 메소드에 인덱스 값을 전달하면 인스턴스의 참조 값이 반환됨
인스턴스 삭제 : remove() 메소드에 인덱스 값을 전달
ArrayList<E> 클래스는 배열 기반 자료구조로, 배열을 이용하여 인스턴스를 저장함
컬렉션 인스턴스를 사용하면 배열처럼 길이를 신경 쓰지 않아도, 필요하면 그 배열의 길이를 스스로 늘리게 됨 이는 더 긴 배열의 교체를 의미하므로 성능에 신경을 써야 한다면 적당한 길이의 배열을 미리 만들어두는 것이 좋음
인스턴스 저장 공간을 늘리거나 인스턴스를 삭제할 경우 많은 시간과 연산이 필요하다는 단점이 있지만, 인덱스 값을 통해 저장된 인스턴스의 참조가 빠름
List<String> list = new ArrayList<>();
// ArrayList<String> list = new ArrayList<>();
list.add("Toy");
list.add("Box");
list.get(0);
list.remove(0);
LinkedList<E> 클래스는 연결 리스트 기반 자료구조로, 연결 리스트를 구성하여 인스턴스를 저장함
연결 리스트를 쉽게 늘릴 수 있기 때문에 인스턴스의 저장 공간을 미리 마련해 둘 필요가 없음
인스턴스 저장 공간을 늘리거나 인스턴스를 삭제할 경우 적은 과정과 연산이 필요하다는 장점이 있지만, 중간에 위치한 인스턴스를 참조하려면 맨 앞, 또는 맨 뒤부터 하나씩 건너가야 하므로 인스턴스의 참조가 느림
List<String> list = new LinkedList<>();
// LinkedList<String> list = new LinkedList<>();
list.add("Toy");
list.add("Box");
list.get(0);
list.remove(0);
저장된 인스턴스의 순차적 접근 방법
저장된 모든 인스턴스들을 대상으로 연산을 할 때 for문을 이용할 수 있지만, 보다 나은 for-each(enhanced for)문을 사용
for-each문을 통한 순차적 접근의 대상이 되려면, Iterable 인터페이스를 구현해야 하는데 Collection<E>가 Iterable<T>를 상속하고 있으며, ArrayList<E>, LinkedList<E> 클래스는 Collection<E> 인터페이스를 구현하여 직간접적으로 구현하고 있음
List<String> list = new LinkedList<>();
for(String s : list) {
System.out.println(s + '\t');
}
또다른 접근 방법으로는 Iterable<T>의 추상 메소드인 iterator()를 사용
iterator 추상 메소드는 저장된 인스턴스들을 순차적으로 참조할 때 사용하는 인스턴스인 반복자를 반환
반복자를 통해 Iterator<E>의 메소드들을 호출하여 인스턴스에 접근
E next() : 다음 인스턴스의 참조 값을 반환
boolean hasNext() : next 메소드 호출 시 참조 값 반환 가능 여부 확인
void remove() : next 메소드 호출을 통해 반환했던 인스턴스를 삭제
만약 반복자가 다시 첫 번째 인스턴스를 가리키게 하려면 반복자를 다시 얻어야 함
List<String> list = new LinkedList<>();
Iterator<String> itr = list.iterator();
while(itr.hasNext()) {
str = itr.next();
if(str.equals("Box"))
itr.remove();
}
참고로 for-each문도 컴파일 과정에서 반복자를 이용하는 코드로 수정되어 반복자에 의한 순차적 접근으로 진행이 됨
컬렉션 인스턴스는 새로운 인스턴스의 추가나 삭제가 필요한 상황이라면 생상자를 기반으로 인스턴스를 생성함
이때 이 생성자는 Collection<E>를 구현한 컬렉션 인스턴스를 인자로 전달 받음
그리고 E는 인스턴스 생성 과정에서 결정되므로 무엇이든 될 수 있음
덧붙여서 매개변수 c로 전달된 컬렉션 인스턴스는 꺼내는 참조만 가능함
이렇게 대다수의 컬렉션 클래스들은 다른 컬렉션 인스턴스를 인자로 전달받을 수 있어 다른 컬렉션 인스턴스에 저장된 데이터를 복사해서 새로운 컬렉션 인스턴스를 생성할 수 있음
따라서 ArrayList<E> 인스턴스를 사용하다가 연결 리스트 자료구조의 특성이 필요하다면 이를 기반으로 LinkedList<E> 인스턴스를 생성하면 됨
class ArrayList<E> {
public ArrayList(Collection<? extends E> c) { ... }
}
class LinkedList<E> {
public LinkedList(Collection<? extends E> c) { ... }
}
List<String> list = Arrays.asList{"Toy", "Box", "Robot", "Box"};
list = new ArrayList<>(list);
list = new LinkedList<>(list); // ArrayList<E> 인스턴스 기반으로 LinkedList<E> 인스턴스 생성
기본 자료형 데이터의 저장과 참조
컬렉션 인스턴스도 기본 자료형의 값은 저장하지 못하므로 래퍼 클래스를 사용하여 저장 및 참조가 가능
이 과정에서 오토 박싱과 오토 언박싱이 이루어짐
LinkedList<Integer> list = new LinkedList<>();
연결 리스트만 갖는 양방향 반복자
Collecion<E>를 구현하는 클래스의 인스턴스는 iterator 메소드의 호출을 통해서 반복자를 얻을 수 있음
그런데 List<E>를 구현하는 클래스의 인스턴스들만 얻을 수 있는 양방향 반복자를 얻는 listIterator 메소드가 존재
배열이나 연결 리스트 같은 자료구조의 특성으로 인해 양쪽 방향으로 이동이 가능하므로 반복자에 다른 메소드들이 추가됨
E previous() : next 메소드와 기능은 같고 방향만 반대
boolean hasPrevious() : hasNext 소드와 기능은 같고 방향만 반대
void add(E e) : 인스턴스의 추가
void set(E e) : 인스턴스의 변경
public ListIterator<E> listIterator()
✔ Set<E> 인터페이스를 구현하는 컬렉션 클래스들
Set<E> 인터페이스를 구현하는 대표적인 컬렉션 클래스
HashSet<E>와 TreeSet<E>가 존재
이들은 인스턴스의 저장 순서가 유지되지 않으며, 동일한 인스턴스의 중복 저장을 허용하지 않음
집합의 특성을 가짐
HashSet<E> 클래스
Object 클래스에 정의되어 있는 hashCode 메소드로 인스턴스가 저장된 주솟값을 기반으로 반환 값을 만들어낸 후, 이를 토대로 부류를 결정하고 선택된 부류 내에서 equals 메소드를 호출하여 동등 비교해 동일한 컬렉션 인스턴스인지 판단
만약 인스턴스가 저장하고 있는 값을 기준으로 동등 여부를 따지도록 하려면 두 메소드를 오버라이딩해야 함
둘 이상의 값을 지니는 클래스의 경우 등과 같이 클래스를 정의할 때마다 hashCode 메소드를 정의하는 것은 번거로우므로 매개변수 선언으로 가변 인자 선언을 가진 hash 메소드를 제공하여 hashCode 메소드를 쉽게 오버라이딩 하도록 함
참고로 String 클래스는 문자열의 내용 비교가 이뤄지도록 두 메소드를 적절히 오버라이딩하고 있으므로 HashSet<E> 인스턴스에는 동일한 문자열을 지닌 String 인스턴스가 둘 이상 저장되지 않음
Set<String> set = new HashSet<>();
set.add("Toy");
set.add("Box");
Set<Num> set = new HashSet<>();
// 다른 인스턴스로 간주됨
set.add(new Num(7799));
set.add(new Num(7799));
// hash 사용 전, 내용 비교 오버라이딩
@Override
public int hashCode() {
return (mode.hashCode() + color.hashCode()) / 2;
}
// hash 사용 후, 내용 비교 오버라이딩
public static int hash(Obejct...values)
@Override
public int hashCode() {
return Objects.hash(mode, color);
}
TreeSet<E> 클래스는 트리 기반 자료구조로, 트리를 이용하여 인스턴스를 저장하므로 정렬된 상태가 유지됨
그러므로 반복자는 인스턴스들의 참조 순서를 오름차순을 기준으로 함
이때 기준을 어떻게 정하느냐에 따라 오름차순으로의 나열 결과가 달라지므로 Comparable 인터페이스의 compareTo 추상 메소드 구현을 통해 크고 작음에 대한 기준을 정해줄 수 있음
이 메소드의 인자로 전달된 o가 작다면 양의 정수를 반환, 크다면 음의 정수를 반환함, 같다면 0을 반환함
만약 일시적으로 기준을 변경해야한다면 메소드를 수정하는 것 대신, Comparator 인터페이스의 compare 메소드 호출을 통해 정렬을 진행할 수 있음
Set<Integer> set = new TreeSet<>();
set.add(3);
set.add(1);
public interface Comparable<T> {
int compareTo(T o);
}
class Person implements Comparable<Person> {
@Override
public int compareTo(Person p) { // 나이가 적으면 작은 것이고 나이가 많으면 큰 것 (나이 오름차순)
return this.age - p.age;
}
}
public interface Comparator<T> {
int compare(T o1, T o2);
}
class PersonComparator implements Comparator<Person> {
@Override
public int compare(Person p1, Person p2) { // 나이가 적으면 큰 것이고 나이가 많으면 작은 것 (나이 내림차순)
returm p2.age - p1.age;
}
}
중복된 인스턴스를 삭제하려면
List<E>를 구현하는 컬렉션 클래스는 인스턴스의 중복 삽입을 허용함
이때 중복 삽입된 인스턴스들을 하나만 남기고 모두 지워야 한다면 Set<E> 인터페이스 인스턴스를 사용
대다수 컬렉션 클래스들은 다른 컬렉션 인스턴스를 인자로 전달받는 생성자가 있어 가능한 것
List<String> lst = Arrays.asList("Box", "Toy", "Box", "Toy");
ArrayList<String> list = new ArrayList<>(lst);
HashSet<String> set = new HashSet<>(list);
list = new ArrayList<>(set);
✔ Queue<E> 인터페이스를 구현하는 컬렉션 클래스들
Queue<E> 인터페이스를 구현하는 대표적인 컬렉션 클래스
LinkedList<E>가 존재
큐는 들어간 순으로 빠져나오는 자료구조
LinkedList<E> 클래스는 List<E>를 구현하면서 동시에 Queue<E>를 구현하는 컬렉션 클래스
어떠한 타입의 참조변수로 참조하느냐에 따라서 리스트로도 동작하고 큐로도 동작함
넣기 : boolean add(E e) 메소드를 통해 넣을 수 있으며, boolean offer(E e)를 통해 넣을 경우 공간이 부족하면 false 반환
꺼내기 : E remove() 메소드를 통해 꺼낼 수 있으며, E poll()를 통해 꺼낼 경우 공간이 부족하면 null 반환
확인하기 : E element() 메소드를 통해 확인할 수 있으며, E peek()를 통해 꺼낼 경우 공간이 부족하면 null 반환
Queue<String> que = new LinkedList<>();
queue.offer("Box");
queue.offer("Toy");
queue.offer("Robot");
queue.peek();
queue.poll();
Stack<E> 인터페이스 대신 Deque<E>?
Stack<E>와 Deque<E>가 존재
스택은 가장 먼저 저장된 데이터가 가장 마지막에 나오는 자료구조
Vector<E>를 상속하는 Stack<E> 클래스는 동기화된 클래스로 멀티 쓰레드에 안전하지만, 그만큼 성능의 저하가 발생하므로 권하지 않음
덱 자료구조는 스택을 대신할 수 있으며, 큐처럼 사용하는 것도 가능함
Deque<E> 인터페이스를 구현하는 대표적인 컬렉션 클래스
ArrayDeque<E>와 LinkedList<E>가 존재
덱은 양쪽에서 넣고 빼는 것이 가능하므로 스택처럼 사용하는 것이 가능하며, 큐처럼 사용하는 것도 가능함
앞에서 넣고, 꺼내고, 확인하기 : void addFirst(E e), E removeFirst(), E getFirst()
뒤로 넣고, 꺼내고, 확인하기 : void addLast(E e), E removeLast(), E getLast()
공간 예외를 발생시키지 않고 앞에서 넣고, 꺼내고, 확인하기 : boolean offerFirst(E e), E pollFirst(), E peekFirst()
공간 예외를 발생시키지 않고 뒤에서 넣고, 꺼내고, 확인하기 : boolean offerLast(E e), E pollLast(), E peekLast()
스택이 필요하면 Deque<E>를 구현한 클래스의 인스턴스를 대상으로 offerFirst & pollFirst, offerLast & pollLast로 쌍을 이루어 메소드를 호출하면 됨
TreeMap<K, V> 클래스는 트리 기반 자료구조로, Key를 대상으로 정렬된 상태가 유지됨
Key에 해당하는 정보에 따라 오름차순으로 정렬됨
내림차순으로 정렬하고 싶다면 Comparator 인터페이스의 compare 메소드 호출을 통해 정렬을 진행할 수 있음
class AgeComparator implements Comparator<Integer> {
public int compare(Integer n1, Integer n2) {
return n2.intValue() - n1.intValue();
}
}
TreeMap<Integer, String> map = new TreeMap<>(AgeComparator());
map.put(45, "Brown");
map.put(37, "James");
Set<Integer> ks = map.keySet();
✔ 컬렉션 기반 알고리즘
정렬
List<E>를 구현한 컬렉션 클래스들을 정렬해야 한다면 sort 메소드를 사용
sort 메소드는 Collections 클래스에 정의되어 있는 제네릭 메소드
메소드 호출 시점에 T가 결정되므로 List<T>의 인스턴스는 모두 전달이 가능함
대신 T가 Comparable<T> 인터페이스를 구현한 상태이어야 함
만약 상속을 한 상위 클래스가 Comparable<T> 인터페이스를 구현하고 있다면, 상속 받은 하위 클래스도 사용 가능
String의 경우 Comparable<String>을 구현하므로 sort 메소드의 인자로 전달될 수 있으며 String 클래스의 compareTo 메소드는 사전 편찬 순으로 정렬되도록 구현되어 있음
public static <T extends Comparable<? super T>> void sort(List<T> list)
class Car implements Comparable<Car> {
@Override
public int compareTo(Car o) {
return disp - o.disp;
}
}
class ECar extends Car { ... }
List<Ecar> list = new ArrayList<>();
Collections.sort(list);
Comparator<T> 기반 정렬
Collections 클래스에는 호출 시 정렬의 기준을 결정할 수 있는 형태로 정의된 sort 메소드도 존재
위와 마찬가지로 만약 상속을 한 상위 클래스가 Comparator<T> 인터페이스를 구현하고 있다면, 상속 받은 하위 클래스도 사용 가능
public static <T> void sort(List<T> list, Comparator<? super T> c)
class Car { ... }
class CarComp implements Comprartor<Car> {
@Override
public int compare(Car o1, Car o2) {
return o1.disp - o2.disp;
}
}
class ECar extends Car { ... }
List<Ecar> list = new ArrayList<>();
CarComp comp = new CarComp();
Collections.sort(list, comp);
찾기
List<E>를 구현한 컬렉션 클래스들에서 특정 인스턴스를 찾아야 한다면 binarySearch 메소드를 사용
binarySearch 메소드는 Collections 클래스에 정의되어 있는 제네릭 메소드
리스트에서 key를 찾아 그 인덱스 값을 반환하고, 찾지 못할 경우 음의 정수를 반환함
메소드 호출 시점에 T가 결정되므로 List<T>의 인스턴스는 모두 전달이 가능함
대신 T가 Comparable<T> 인터페이스를 구현한 상태이어야 함
만약 상속을 한 상위 클래스가 Comparable<T> 인터페이스를 구현하고 있다면, 상속 받은 하위 클래스도 사용 가능
binarySearch 메소드는 이진 탐색 알고리즘을 기반으로 탐색을 진행하므로 정렬된 상태여야만 함
public static <T> int binaraySearch(List<? extends Comparable<? super T>> list, T key)
class Car implements Comparable<Car> {
@Override
public int compareTo(Car o) {
return disp - o.disp;
}
}
class ECar extends Car { ... }
List<Ecar> list = new ArrayList<>();
Collections.sort(list);
int idx = Collecionts.binarySearch(list, "Robot");
list.get(idx);
Comparator<T> 기반 찾기
Collections 클래스에는 호출 시 탐색의 기준을 결정할 수 있는 형태로 정의된 binarySearch 메소드도 존재
위와 마찬가지로 만약 상속을 한 상위 클래스가 Comparator<T> 인터페이스를 구현하고 있다면, 상속 받은 하위 클래스도 사용 가능
public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c)
class StrComp implements Comprartor<String> {
@Override
public int compare(String s1, String s2) {
return s1.compareToIgnoreCase(s2); // 대소문자 구분 없이 정렬 및 탐색
}
}
List<String> list = new ArrayList<>();
StrComp cmp = new StrComp();
Collections.sort(list, cmp);
int idx = Collecionts.binarySearch(list, "Robot", cmp);
list.get(idx);
복사
List<E>를 구현한 컬렉션 클래스들에서 컬렉션 인스턴스에 저장된 내용을 복사해야 한다면 copy 메소드를 사용
