📓 컬렉션 프레임워크 (Collections Framework)
- 컬렉션(Collection) : 여러 객체(데이터)를 모아 놓은 것
- 프레임워크(Framework) : 표준화(정형화)된 체계적인 프로그래밍 방식
- 컬렉션 프레임워크 : 컬렉션(다수의 객체)을 다루기 위한 표준화된 프로그래밍 방식
- 컬렉션을 쉽고 편리하게 다룰 수 있는 다양한 클래스를 제공
📒 Collection인터페이스의 메소드
📕 컬렉션 프레임워크의 핵심 인터페이스
| 인터페이스 | 특 징 |
|---|---|
| List | 순서가 있는 데이터의 집합. 데이터의 중복을 허용 -구현클래스 : ArrayList, LinkedList, Stack, Vector 등 |
| Set | 순서를 유지하지 않는 데이터의 집합. 데이터의 중복을 허용하지 않는다. -구현클래스 : HashSet, TreeSet 등 |
| Map | 키(Key)와 값(Value)의 쌍을 이루어진 데이터의 집합. 순서는 유지되지 않으며, 키는 중복을 허용하지 않고, 값은 중복을 허용. -구현클래스 : HashMap, TreeMap, Hashtable, Properties 등 |
📒 List인터페이스
순서가 있고 중복을 허용함
🔹 List인터페이스의 메소드
📃 ArrayList
기존의 Vector를 개선한 것. 구현원리가 기능적으로 동일
- Vector는 동기화, ArrayList는 비동기화
- 배열의 타입이 Object이므로 모든 종류의 객체를 저장할 수 있다.
◼ ArrayList의 메소드
◼ ArrayList의 삭제(remove)과정
- 삭제할 데이터 아래의 데이터를 한 칸씩 위로 복사해서 삭제할 데이터를 덮어쓴다.
- 마지막 객체를 삭제할 때는 덮어씌우기를 하지 않음- 데이터가 모두 한 칸씩 이동했으므로 마지막 데이터는 null로 변경
- 데이터가 삭제되어 데이터의 개수가 줄었으므로 size 값 감소
🔸 배열의 장단점
◼ 장점
- 구조가 간단하다
- 접근시간(데이터를 읽는데 걸리는 시간)이 짧다
◼ 단점
- 크기를 변경할 수 없다.
- 변경하는 경우 배열을 새로 생성 후 복사
- 충분히 큰 배열 생성시 남는 부분만큼 메모리가 낭비
- 비순차적인 데이터의 추가/삭제에 시간이 오래 걸림
- 데이터 추가/삭제를 위해 다른 데이터를 옮겨야 한다
- 순차적인 데이터 추가/삭제(끝에서 하는 추가 삭제)는 빠름
📃 LinkedList
불연속적으로 존재하는 데이터를 연결(link)
◼ 배열의 단점을 보완하여 나온 클래스
▶ 데이터의 추가, 삭제
추가 : 모든 위치에서 한번의 Node생성과 두 번의 참조변경만으로 가능
삭제 : 모든 위치에서 단 한 번의 참조변경만으로 가능
◼ 단점
단일 링크드 리스트의 경우 데이터 접근성이 나쁨
◼ LinkedList의 종류
- 링크드 리스트(Linked List)
- 연결리스트. 데이터 접근성 나쁨- 더블리 링크드 리스트(Doublely Linked List)
- 이중 연결리스트. 접근성 향상- 더블리 써큘러 링크드 리스트(Doublely Circular Linked List)
- 이중 원형 연결리스트. 시작노드와 끝노드가 연결
🔸 ArrayList vs LinkedList 성능 비교
- 순차적인 데이터 추가/삭제 - ArrayList > LinkedList
- 비순차적인 데이터 추가/삭제 - LinkedList > ArrayList
- 접근시간 - ArrayList > LinkedList
| 컬렉션 | 접근시간 | 추가/삭제 | 비 고 |
|---|---|---|---|
| ArrayList | 빠르다 | 느리다 | 순차적인 추가/삭제는 더 빠르다. 비효율적인 메모리 사용 |
| LinkedList | 느리다 | 빠르다 | 데이터가 많을수록 접근성이 떨어짐 |
📃 스택(Stack)
마지막에 저장된 것을 가장 먼저 꺼냄(Last In First Out, LIFO)
◼ Stack의 메소드
◼ Stack의 활용 예
수식계산, 수식괄호검사, 워드프로세서의 undo/redo, 웹브라우저의 뒤로/앞으로
📃 큐(Queue)
가장 먼저 저장된 것을 가장 먼저 꺼냄(First In First Out, FIFO)
◼ Queue의 메소드
Queue는 인터페이스다!
- 생성자가 없음. Queue를 구현한 클래스인 LinkedList를 주로 사용
◼ Queue의 활용 예
최근사용문서, 인쇄작업 대기목록, 버퍼(buffer)
📒 Set인터페이스
순서가 없고, 중복을 허용하지 않음
🔹 Set인터페이스의 메소드
Collection 인터페이스와 동일
◼ 집합 연산과 관련된 메소드
📃 HashSet
Set인터페이스를 구현한 대표적인 컬렉션 클래스
⁕ 순서를 유지하려면 LinkedHashSet클래스 사용
◼ HashSet의 메소드
◼ HashSet의 add()
- HashSet은 객체를 저장하기전에 기존에 같은 객체가 있는지 확인
- 같으면 저장하지 않음- boolean add(Object o)는 저장할 객체의 equals()와 hashCode() 호출
- equals()와 hashCode()가 오버라이딩 되어있어야 한다.
//오버라이딩을 하지 않을시
class Person {
String name;
int age;
Person(String name, int age){
this.name = name;
this.age = age;
}
}
HashSet set = new HashSet();
set.add(new Person("David" , 10));
set.add(new Person("David" , 10));
// set에는 David가 두번 저장됨. - equals()의 기본형은 주소비교이기때문📃 TreeSet
이진 탐색 트리로 구현. 범위 검색과 정렬에 유리한 컬렉션 클래스
- HashSet보다 데이터 추가/삭제에 시간이 더 걸림
🔸 이진 탐색 트리 (Binary Search Tree)
◼ 이진 트리
- 모든 노드가 최대 2개의 하위 노드를 가짐
- 각 요소(node)가 나무(tree)형태로 연결(LinkedList의 변형)
class TreeNode {
TreeNode left; //왼쪽 자식노드
Object element; //저장할 객체
TreeNode right; //오른쪽 자식노드
}
◼ 이진 탐색 트리
이진 트리 형태로, 부모보다 작은 값은 왼쪽, 큰 값은 오른쪽 자식에 저장
- 데이터가 많아질수록 추가/삭제에 시간이 더 걸림(비교 횟수 증가)
◼ TreeSet의 add()
루트(root)부터 트리를 따라 내려가며 값을 비교.
작으면 왼쪽, 크면 오른쪽 자식으로 저장
◼ TreeSet의 메소드
🔸 트리 순회 (Tree Traversal)
이진 트리의 모든 노드를 한 번씩 읽는 것
- 전위순회(preorder), 중위순회(inorder), 후위순회(postorder)가 존재
- 이진탐색트리를 중위순회 하면 오름차순으로 정렬된다
📒 Map인터페이스
순서가 없고, 키(key)는 중복을 허용하지 않지만 값(value)는 허용
🔹 Map인터페이스의 메소드
📃 HashMap과 HashTable
데이터를 키와 값의 쌍으로 저장
- HashTable(동기화 X)은 HashMap(동기화 O)의 신버전
📃 HashMap
Map인터페이스를 구현한 대표적인 컬렉션 클래스
⁕ 순서를 유지하려면, LinkedHashMap 사용
🔸 해싱(hashing)
해시 함수(hash function)로 해시테이블(hash table)에 데이터 저장, 탐색
- 해시테이블은 배열(Array)과 링크드 리스트(Linked List)가 조합된 형태
◼ 해시테이블에 저장된 데이터를 가져오는 과정
① 키로 해시함수를 호출해서 해시코드를 얻는다.
② 해시코드(해시함수의 반환값)에 대응하는 링크드 리스트를 배열에서 찾음
③ 링크드 리스트에서 키와 일치하는 데이터를 찾는다.
⁕ 해시함수는 같은 키에 대해 항상 같은 해시코드 반환
서로 다른 키일지라도 같은 값의 해시코드를 반환할 수도 있다.
◼ HashMap의 키(key)와 값(value)
해싱(hashing)기법으로 데이터를 저장. 데이터가 많아도 검색 빠름
- 키(key) : 컬렉션 내의 키(key) 중에서 유일해야한다
- 값(value) : 키(key)와 달리 데이터의 중복을 허용
◼ HashMap의 메소드
📃 TreeMap
범위 검색과 정렬에 유리한 컬렉션 클래스
- HashMap보다 데이터 추가/삭제에 시간이 더 걸림
📘 Iterator, ListIterator, Enumeration
컬렉션에 저장된 데이터를 접근하는데 사용되는 인터페이스
- Enumeration은 Iterator의 구버전
- ListIterator는 Iterator의 접근성을 향상시킨 것 (단방향 → 양방향)
🔷 Iterator
컬렉션에 저장된 요소들을 읽어오는 방법을 표준화한 것
- List와 Set에서 사용
◼ 사용법
컬렉션에 iterator()를 호출해서 Iterator를 구현한 객체를 얻어서 사용
public interface Collection {
...
public Iterator iterator(); //Collection인터페이스에 iterator()가 존재
...
}
List list = new ArrayList();
Iterator it = list.iterator(); // iterator() 호출
while(it.hasNext()){
System.out.println(it.next());
}◼ Iterator의 메소드
🔷 Map과 Iterator
Map에는 iterator()가 없다.
- 대신 keySet(), entrySet(), values()를 호출
Map map = new HashMap();
...
Iterator it = map.entrySet().iterator(); //entrySet()을 호출해서 간접접근📘 Comparator와 Comparable
객체 정렬에 필요한 메소드(정렬기준 제공)를 정의한 인터페이스
- Comparable : 기본 정렬기준을 구현하는데 사용
- Comparator : 기본 정렬기준 외에 다른 기준으로 정렬하고자할때 사용
public interface Comparator {
int compare(Object o1, Object o2); // o1, o2 두 객체 비교
boolean equals(Object obj); //equals를 오버라이딩하라는 뜻
}
public interface Comparable {
int compareTo(Object 0); //주어진 객체(o)를 자신과 비교
}
//compare(), compareTo()는 두 객체의 비교 결과를 반환
//(같으면 0, 오른쪽이 크면 음수(-), 왼쪽이 크면 양수(+) 🔷 예제
class Ex11 {
public static void main(String[] args){
String[] strArr = {"cat", "Dog", "lion", "tiger"};
Arrays.sort(strArr);
System.out.println("strArr=" + Arrays.toString(strArr));
Arrays.sort(strArr, String.CASE_INSENSITIVE_ORDER);//대소문자구분X
System.out.println("strArr=" + Arrays.toString(strArr));
Arrays.sort(strArr, new Descending());
System.out.println("strArr=" + Arrays.toString(strArr));
}
}
class Descending implements Comparator {
public int compare(Object o1, Object o2) {
if(o1 instanceof Comparable && o2 instanceof Comparable) {
Comparable c1 = (Comparable) o1;
Comparable c2 = (Comparable) o2;
return c1.compareTo(c2) * -1; // -1을 곱해서 역으로 변경
}
}
}
/* 출력
strArr=[Dog, cat, lion, tiger] //D가 c보다 코드상 빠르기 때문
strArr=[cat, Dog, lion, tiger]
strArr=[tiger, lion, cat, Dog] //D가 c보다 코드상 빠르기 때문
*/🔷 Integer와 Comparable
Integer는 Comparable을 구현한 클래스
public final class Integer extends Number implements Comparable{
...
public int compareTo(Object o) {
return compareTo((Integer)o);
}
//Array.sort()같은 메소드가 정렬을 수행하는 과정에서 사용됨
public int compareTo(Integer anotherInteger){
int thisVal = this.value;
int anotherVal = anotherInteger.value;
//같으면 0, 크면 -1, 작으면 1 반환
return (thisVal < anotherVal ? -1 : (thisVal == anotherVal ? 0 : 1));
}
}
📘 Collections
컬렉션을 위한 메소드(static) 제공
◼ 1. 컬렉션 채우기, 복사, 정렬, 검색
fill(), copy(), sort(), binarySearch() 등
◼ 2. 컬렉션의 동기화
synchronizedXXX() (XXX에 컬렉션객체타입)
static Collection synchronizedCollection(Collection c)
static List synchronizedList(List list)
static Set synchronizedSet(Set set)
static Map synchronizedMap(Map map)
static SortedSet synchronizedSortedSet(SortedSet s)◼ 3. 변경불가(readOnly) 컬렉션 만들기
unmodifiableXXX() (XXX에 컬렉션객체타입)
static Collection unmodifiableCollection(Collection c)
static List unmodifiableList(List list)
static Set unmodifiableSet(Set set)
static Map unmodifiableMap(Map map)
static NavigableSet unmodifiableNavigableSet(NavigableSet s)
static SortedSet unmodifiableSortedSet(SortedSet s)
static NavigableMap unmodifiableNavigableMap(NavigableMap m)
static SortedMap unmodifiableSortedMap(SortedMap m)◼ 4. 싱글톤 컬렉션 만들기
singletonXXX() (XXX에 컬렉션객체타입)
static List singletonList(List list)
static Set singleton(Object o) //주의하기!! Set은 singletonSet() X
static Map singleton(Object key, Object value)◼ 5. 한 종류의 객체만 저장하는 컬렉션 만들기
checkedXXX() (XXX는 컬렉션객체타입)
static Collection checkedCollection(Collection c, Class type)
static List checkedList(List list, Class type)
static Set checkedSet(Set set, Class type)
static Map checkedMap(Map map, Class keyType, Class valueType)
static Queue checkedQueue(Queue queue, Class type)
static NavigableSet checkedNavigableSet(NavigableSet s, Class type)
static SortedSet checkedSortedSet(SortedSet s, Class type)
static NavigableMap checkedNavigableMap(NavigableMap m, Class keyType, Class valueType)
static SortedMap checkedSortedMap(SortedMap m, Class keyType, Class valueType)📝 요약
