👉🏻 이 글은 자바의 정석(3판) Chapter.11을 공부하고 적은 내용입니다.
📌 컬렉션 프레임워크
- 컬렉션 : 다수의 데이터(데이터 그룹)
- 프레임워크 : 표준화된 프로그래밍 방식
➡️ 컬렉션 프레임워크 :
데이터 군을 다루고 표현하기 위한 단일화된 구조,
컬렉션과 다수의 데이터를 다루는 데 필요한 다양하고 풍부한 클래스들을 제공
JDK1.2 이전까지의 컬렉션 클래스 - Vector, Hashtable, Properties, Stack
JDK1.2 이후부터 컬렉션 프레임워크 등장 - ArrayList, LinkedList, HashSet, ......
cf) JDK1.5부터 Iterable 인터페이스 추가
📖 핵심 인터페이스
컬렉션 데이터 그룹을 크게 3타입이 존재한다고 인식하고 인터페이스 정의
| 인터페이스 | 구현 클래스 | 특징 |
|---|---|---|
| List | ArrayList, LinkedList, Stack, Vector 등 | 순서가 있는 데이터의 집합. 데이터 중복을 허용. |
| Set | HashSet, TreeSet 등 | 순서를 유지하지 않는 데이터의 집합. 데이터 중복을 허용하지 않는다. |
| Map | HashMap, TreeMap, Hashtable, Properties 등 | 키(key)와 값(value)의 쌍(pair)으로 이루어진 데이터의 집합. 순서유지X, 키는 중복을 허용하지 않는다. (Map : 어떤 두 값을 연결한다.) |
⚠️ Vector나 Hashtable과 같은 기존 컬렉션들은 호환을 위해 남겨두었지만 가능하면 사용하지 않는 것이 좋다. (-> ArrayList, HashMap 사용 권장)
⭐ Collection 인터페이스
List와 Set의 부모클래스로, 두 클래스의 공통된 부분을 뽑아 정의한 것이다.
Collection 인터페이스는 컬렉션 클래스에 저장된 데이터를 읽고, 추가, 삭제하는 등 컬렉션을 다루는데 가장 기본적인 메소드들을 저장하고 있다.
| 메서드 | 설명 |
|---|---|
boolean add(Object o) | 지정된 객체(o) 또는 Collection(c)의 객체들을 Collection에 추가한다. |
boolean addAll(Collection c) | |
void clear() | Collection의 모든 객체를 삭제한다. |
boolean contains(Object o) | 지정된 객체(o) 또는 Collection의 객체들(c)이 Collection에 포함되어 있는지 확인한다. |
boolean containsAll(Collection c) | |
boolean equals(Object o) | 동일한 Collection인지 비교한다. |
int hashCode() | Collection의 hash code를 반환한다. |
boolean isEmpty() | Collection이 비어있는지 확인 |
Iterator iterator() | Collection의 Iterator를 얻어서 반환한다. |
boolean remove(Object o) | 지정된 객체를 삭제한다. |
boolean removeAll(Colection c) | 지정된 Collection에 포함된 객체들을 삭제한다. |
boolean retainAll(Collection c) | 지정된 Collection에 포함된 객체만을 남기고 다른 객체들은 Collection에서 삭제한다. 이 작업으로 인해 Collection에 변화가 생기면 true, 없으면 false를 반환한다. |
int size() | Collection에 저장된 객체의 개수를 반환한다. |
Object[] toArray() | Collection에 저장된 객체를 객체배열(Object[])로 반환한다. |
Object[] toArray(Object[] a) | 지정된 배열에 Collection의 객체를 저장해서 반환한다. |
⚠️ Collection은 인터페이스이고, Collections는 클래스이다.
📌 List
📖 List 인터페이스
중복을 허용하면서 저장순서가 유지되는 컬렉션을 구현하는데 사용한다.
⭐ ArrayList
ArrayList는 List인터페이스를 구현하기 때문에 데이터의 저장순서 유지, 중복 허용
- 기존의 Vector를 개선한것으로 Vector와 구현원리와 기능적인 측면에서 동일하다고 할 수 있다. Vector는 기존에 작성된 코드와의 호환성을 위해서 계속 남겨 두고 있을 뿐이기 때문에 가능하면 Vector보다는 ArrayList를 사용하자.
⬇️ArrayList 소스코드 일부
public class ArrayList extends AbstractList
implements List, RandomAccess, Cloneable, java.io.Serializable{
...
transient Object[] elementData; // Object배열
...
}Object 배열을 이용해서 데이터를 순차적으로 저장한다.
선언된 배열의 타입이 Object이므로 모든 종류의 객체를 담을 수 있다.
⬇️ ArrayList의 생성자와 매서드
| 메서드 | 설명 |
|---|---|
| ArrayList() | 크기가 10인 ArrayList 생성 |
| ArrayList(Collection c) | 주어진 컬렉션이 저장된 ArrayList를 생성 |
| ArrayList(int initialCapacity) | 지정된 초기용량을 갖는 ArrayList 생성 |
| Object clone() | ArrayList를 복제한다. |
| void ensureCapacity(int minCapacity) | ArrayList의 용량이 최소한 minCapacity가 되도록 한다. |
| List subList(int fromIndex, int toIndex) | fromIndex부터 toIndex 사이에 저장된 객체를 반환한다. |
| Object[] toArray() | ArrayList에 저장된 모든 객체들을 객체배열로 반환한다. |
| Object[] toArray(Object[] a) | ArrayList에 저장된 모든 객체들을 객체배열 a에 담아 반환한다. |
| void trimToSize() | 용량을 크기에 맞게 줄인다.(빈 공간을 없앤다.) |
| ... |
⬇️ 아래는 list2에서 list1과 공통되는 요소들을 찾아 삭제하는 부분이다.
for(int i=list2.size()-1; i>=0; i--) {
if(list1.contains(list2.get(i));
list2.remove(i);
}⚠️ 만일 변수 i를 증가시켜가면서 삭제하면, 한 요소가 삭제될 때마다 빈 공간을 채우기 위해 나머지 요소들이 자리이동을 하기 때문에 올바른 결과를 얻을 수 없다.
그래서 제어변수를 감소시켜가며 삭제를 해야 자리이동이 발생해도 영향을 받지 않고 작업이 가능하다.
⚠️ ArrayList를 생성할 때, 저장할 요소의 개수를 고려해서 실제 저장할 개수보다 약간 여유있는 크기로 하는 것이 좋다.
List list = new ArrayList(length/LIMIT +10);생성할 때 지정한 크기보다 더 많은 객체를 저장하면 자동적으로 크기가 늘어나기는 하지만 이 과정에서 처리시간이 많이 소요되기 때문이다.
Vector의 용량과 크기에 관한 코드
class VectorEx1{
public static void main(String[] args) {
Vector v = new Vector(5);
v.add("1");
v.add("2");
v.add("3");
print(v);
v.trimToSize(); // 빈 공간을 없앤다. (용량과 크기가 같아진다.)
System.out.println("=== After trimToSize() ===");
print(v);
v.ensureCapacity(6);
System.out.println("=== After ensureCapacity(6) ===");
print(v);
v.setSize(7);
System.out.println("=== After setSize(7) ===");
print(v);
v.clear();
System.out.println("=== After clear() ===");
print(v);
}
public static void print(Vector v) {
System.out.println(v);
System.out.println("size :"+v.size());
System.out.println("capacity :"+v.capacity());
System.out.println();
}
}
--> 배열은 크기를 변경할 수 없기 때문에 새로운 배열을 생성해서 그 주소값을 변수 v에 할당한다. 기존의 Vector 인스턴스는 더 이상 사용할 수 없으며, 후에 가비지 컬렉터에 의해 메모리에서 제거된다.
---> 따라서 ArrayList나 Vector과 같이 배열을 이용한 자료구조는 데이터를 읽어오고 저장하는 데는 효율이 좋지만 (접근 시간, access time), 용량을 변경해야 할 때는 데이터 복사 과정을 거치기 때문에 상당히 효율이 떨어진다.
----> 처음에 인스턴스를 생성할 때 저장할 데이터의 개수를 잘 고려해서 충분한 용량의 인스턴스를 생성하는 것이 좋다. (이 방법을 이용할 시, 메모리 낭비 가능성이 있는 것이 배열의 단점임.)
⭐ LinkedList
위의 배열의 단점을 보완하기 위해 LinkedList라는 자료구조가 고안됨.
배열은 모든 데이터가 연속적으로 존재하지만 링크드 리스트는 불연속적으로 존재하는 데이터를 서로 연결한 형태로 구성되어 있다.
링크드 리스트의 각 요소(node)들은 자신과 연결된 다음 요소에 대한 참조(주소값)와 데이터로 구성되어 있다.
class Node {
Node next; // 다음 요소의 주소를 저장
Object obj; // 현 노드의 데이터 저장
}- 요소 삭제 & 추가
- 삭제 : 삭제하고자 하는 요소의 이전 요소가 삭제하고자 하는 요소의 다음 요소를 참조하도록 변경하기만 하면 된다.
- 추가 : 새로운 요소를 생성한 다음 추가하고자 하는 위치의 이전 요소의 참조를 새로운 요소에 대한 참조로 변경, 새로운 요소가 그 다음 요소를 참조하도록 변경.
이동방향이 단방향 -> 이전요소에 대한 접근은 어려움 --> 더블 링크드 리스트
- 더블 링크드 리스트 (이중 연결리스트)
: 양방향 가능하도록 앞뒤 연결
class Node {
Node next; // 다음 요소의 주소를 저장
Node previous; // 이전 요소의 주소를 저장
Object obj; // 현 노드의 데이터 저장
}⬇️ 접근성을 더욱 향상시킨 것
- 더블 써큘러 링크드 리스트(이중 원형 연결리스트)
: 첫 번째 요소와 마지막 요소를 서로 연결시킨 것.
LinkedList 역시 List인터페이스를 구현했기 때문에 ArrayList와 내부구현방법만 다를뿐 제공하는 메서드의 종류와 기능은 거의 같다.
⭐ Stack과 Queue
Stack : 마지막에 저장한 데이터를 가장 먼저 꺼내는 LIFO구조 (동전통 구조)
Ex) 수식계산, 수식 괄호 검사, 웹 브라우저 뒤로/앞으로....
- Stack의 메서드
| 메서드 | 설명 |
|---|---|
| boolean empty() | Stack이 비어있는지 알려준다. |
| Object peek() | 맨 위에 있는 객체를 반환. pop과 달리 객체를 꺼내지는 않음. (비었을 경우 EmptyStackException 발생함) |
| Object pop() | 맨 위에 저장된 객체를 꺼낸다. (비었을 경우 EmptyStackException 발생함) |
| Object push(Object item) | Stack에 객체를 저장한다. |
| int search(Object o) | 주어진 객체를 찾아서 그 위치를 반환. 못 찾으면 -1 반환. (배열과 달리 위치는 1부터 시작) |
Queue : 처음에 저장한 데이터를 가장 먼저 꺼내는 FIFO구조 (파이프 구조)
Ex) 최근 사용 문서, 인쇄작업 대기 목록, 버퍼(buffer)....
- Queue의 메서드
| 메서드 | 설명 |
|---|---|
| boolean add(Object o) | 지정된 객체를 Queue에 추가한다. 성공하면 true, 저장공간이 부족하면 IllegalStateException발생 |
| Object remove() | 객체를 꺼내 반환. 비어있으면 NoSuchElementException 발생 |
| Object element() | 삭제 없이 요소를 읽어온다. peek와 달리 Queue가 비어있을 때 NoSuchElementException 발생 |
| Object offer(Object o) | Queue에 객체를 저장. 성공하면 true, 실패하면 false |
| Object poll() | Queue에서 객체를 꺼내 반환. 비어있으면 null 반환. |
| Object peek() | 삭제 없이 요소를 읽어 온다. Queue가 비어있으며 null을 반환 |
👉🏻 Queue의 인터페이스 기능 사용할 때 아래의 Java API문서 참고
https://docs.oracle.com/javase/8/docs/api/java/util/Queue.html
-
PriorityQueue
: Queue의 구현체 중 하나, 저장한 순서와 관계없이 우선순위가 높은 것부터 꺼내는 특징이 있다. (null은 저장할 수 없다. )
저장공간으로 배열을 사용, 각 요소를 힙이라는 자료구조 형태로 저장. -
Deque 덱, 다큐 (Double-Ended Queue)
: Queue의 변형. 양쪽 끝에 추가/삭제가 가능하다.
Deque의 조상은 Queue, 구현체는 ArrayDeque, LinkedList
스택과 큐를 하나로 합쳐 놓은 것과 같다.
| Deque | Queue | Stack |
|---|---|---|
| offerLast() | offer() | push() |
| pollLast() | - | pop() |
| pollFist() | poll() | - |
| peekFirst() | peek() | - |
| peekLast() | - | peek() |
📖 Enumeration, Iterator, ListIterator
모두 컬렉션에 저장된 요소를 접근하는데 사용되는 인터페이스이다. Enumeration은 Iterator의 구버전이며, ListIterator는 Iterator의 기능을 향상시킨 것이다.
⭐ Iterator
public interface Iterator{
boolean hashNext(); // 읽어 올 요소가 남아있는지 확인한다.
Object next(); // 다음 요소를 읽어 온다.
void remove(); // next()로 읽어 온 요소를 삭제. (선택적 기능)
}
public interface Collention {
...
public Iterator iterator(); // List와 Set에서도 포함되어 있음.
...
}
// 리스트에 저장된 요소들을 출력하기 위한 코드
List list = new ArrayList(); // 다른 컬렉션으로 변경할 때는 이 부분만 고치면 된다.
Iterator it = list.iterator();
while(it.hashNext()) {
System.out.println(it.next());
}
// Map인터페이스에서 Iterator 사용.
Map map = new HashMap();
...
// 키와 값을 Set형태로 받아온 다음 iterator() 호출
Iterator it = map.keySet().iterator(); // 키를 Set형태로 받아옴
Iterator list = map.entrySet().iterator(); // 값를 Set형태로 받아옴⭐ Enumeration
컬렉션 프레임워크가 만들어지기 전 기능으로, Iterator의 구버전임.
메서드 이름만 다를 뿐 기능은 같다.
- boolean hashMoreElements() : 읽어 올 요소가 남아있는지 확인
( = hasNext() ) - Object nextElement() : 다음 요소를 읽어온다.
( = next() )
⭐ ListIterator
Iterator를 상속받아서 기능을 추가한 것으로, ListIterator는 양방향으로의 이동이 가능하다. 다만, ArrayList나 LinkedList와 같이 List인터페이스를 구현한 컬렉션에서만 사용할 수 있다.
add(Object o), hasNext(),hasPrevious(), next(), previous(), nextIndex(), remove(), set(Object o) 가 메서드로 있음.
- 이동하기 전에 반드시 hasNext()나 hasPrevious()를 호출해서 이동할 수 있는지 확인해야 한다.
ListIterator it = list.listIterator();
while(it.hasNext()) { // 순방향으로 진행하면서 읽어옴
System.out.println(it.next());
}
while(it.hasPrevious()) { // 역방향으로 진행하면서 읽어옴
System.out.println(it.previous());
}remove()는 단독으로 쓰일 수 없고,next()를 호출하여 읽어온 것을 삭제하는 역할을 한다. (읽어온 값이 있어야 호출될 수 있다.)
📖 Arrays
Arrays 클래스에는 배열을 다루는데 유용한 메서드(모두 static메서드)가 정의되어 있다.
1. 배열의 복사 - copyOf(), copyOfRange()
copyOf()는 배열 전체 복사, copyOfRange()는 일부를 복사하여 새로운 배열을 만든 다음 반환한다.
int[] arr = {0, 1, 2, 3, 4};
int[] arr1 = Arrays.copyOf(arr, arr.length);
int[] arr2 = Arrays.copyOf(arr, 3); // [0,1,2]
int[] arr3 = Arrays.copyOf(arr, 7); // [0,1,2,3,4,0,0]
int[] arr4 = Arrays.copyOfRange(arr, 2, 4); // [2,3]2. 배열 채우기 - fill(), setAll()
Arrays.fill(arr, 9);: 배열의 모든 요소를 9로 채움.Arrays.setAll(arr, ()->(int)(Math.random()*5)+1);
: 배열을 채우는데 사용할 함수형 인터페이스를 매개변수로 받는다.
// arr = [1,5,2,1,1]
3. 배열 정렬과 검색 - sort(), binarySearch()
sort(): 배열을 정렬binarySearch(): 배열에서 지정된 값이 저장된 위치를 찾아서 반환
'순차검색(linear search)'보다 큰 배열의 검색에서 유리하다. 단, 배열이 정렬되어 있는 경우에만 사용할 수 있다는 단점이 있다.
4. 문자열 비교와 출력 - equals(), toString()
일차원 배열에서의 문자열로 출력은 toString()이용하고,
다차원 배열에서의 문자열로 출력은 deepToString()을 이용한다.
일차원 배열에서 배열 비교는 equals(),
다차원 배열에서 배열 비교는 deepEquals()
📌 Set
📖 Comparator와 Comparable
모두 인터페이스로 컬렉션을 정렬하는데 필요한 메서드를 정의하고 있음.
Comparable : 기본 정렬기준을 구현하는데 사용. (기본 오름차순)
Comparator : 기본 정렬기준 외에 다른 기준으로 정렬하고자할 때 사용
// java.util
public interface Comparator {
int compare(Object o1, Object o2);
boolean equals(Object obj);
}
// java.lang
public interface Comparable {
public int compareTo(Object o);
}📖 HashSet
HashSet은 Set인터페이스를 구현한 가장 대표적인 컬렉션이며, 중복요소를 저장하지 않는다.
새로운 요소를 추가할 때는 add메서드나 addAll메서드를 이용하는데, 만일 이미 저장되어 있는 요소이면, false를 반환한다.
저장순서를 유지하지 않으므로 저장순서를 유지하고자 한다면 LinkedHashSet을 사용해야한다.
-
객체의 타입이 다르면 중복으로 간주하지 않는다.
("1") != Integer(1) -
랜덤으로 중복되지 않는 숫자 배열을 만드는 방법
for(int i=0; set.size() < 25; i++){
set.add((int)Math.random()*50)+1+"");
}- 여러번 생성된 동일한 값의 객체를 같은 것으로 인식하게 하는 방법
class Person{
String name;
int age;
Person(String name, int age){
this.name = name;
this.age = age;
}
//
public boolean equals(Object obj) {
if(obj instanceof Person){
Person tmp = (Person)obj;
return name.equals(tmp.name) && age==tmp.age;
}
return false;
}
public int hashCode() {
return (name+age).hashCode();
}
public String toString(){
return name + ":" + age;
}
}👉🏻 HashSet의 add메서드는 새로운 요소를 추가하기 전에 기존에 저장된 요소와 같은 것인지 판단하기 위해 추가하려는 요소의 equals()와 hashCode()를 호출하므로 목적에 알맞게 오버라이딩 해야한다.
- String은 문자열의 내용으로 해시코드를 만들어 내고, Object클래스는 객체 주소로 해시코드를 만들어 낸다.
📖 TreeSet
이진 검색 트리라는 자료구조의 형태로 데이터를 저장한다.
정렬, 검색, 범위 검색에 높은 성능을 보인다.
중복된 데이터의 저장을 허용하지 않으며, 정렬된 위치에 저장하므로 저장순서를 유지하지도 않는다.
- 이진 검색 트리 (binary tree)
- 모든 노드는 두 개의 자식 노드를 가질 수 있다.
- 왼쪽 노드는 부모노드의 값보다 작고, 오른쪽 노드는 크다.
- 노드의 추가, 삭제에 시간이 걸린다.
- (범위)검색과 정렬에 유리하다.
- 중복된 값은 저장하지 못한다.
- TreeSet에서의 랜덤으로 숫자 배열하기
for(int i=0; set.size() < 6; i++) {
int num = (int)(Math.random()*45) + 1;
set.add(num);
}-> TreeSet은 HashSet과 달리 따로 정렬할 필요가 없다.
headSet() : 지정된 기준 값보다 큰 값의 객체들
tailSet() : 지정된 기준 값보다 작은 값의 객체들
📌 Map
📖 HashMap
Hashtable은 HashMap의 구버전. 새로운 버전인 HashMap 사용할 것을 권장한다.
Map은 키(key)와 값(value)을 묶어서 하나의 데이터(entry)로 저장한다.
public class HashMap extends AbstractMap implements Map,
Cloneable, Seialization {
transient Entry[] table;
...
static class Entry implements Map.Entry {
final Object key;
Object value;
...
}
}key : 컬렉션의 내의 키 중에서 유일해야 한다.
value : 키와 달리 데이터의 중복을 허용. ( null 허용 )
entry = (Object, Object)
📖 TreeMap
이진 검색 트리 형태로 키와 값의 쌍을 저장한다.
검색과 정렬에 적합한 컬렉션 클래스이다.
검색에 관한한 대부분의 경우에서 TreeMap보다 HashMap이 더 뛰어나므로 HashMap을 사용하는 것이 적합하다.
다만, 범위검색이나 정렬이 필요한 경우 TreeMap을 사용하자.
📖 Properties
Hashtable을 상속받음.
entry = (String, String)
주로 환경설정 관련한 속성을 저장할 때 사용한다.
📌 컬렉션 클래스 정리 & 요약
총정리 필기본
