자바의 정석 - 자바 기본기 정리하기 (10)컬렉션

들어가며

---

문제 구현에 있어서 자바에 대한 기본기의 부족함을 느껴서 오랜만에 자바의 기본 저서인 자바의 정석을 다시 피게 됐다. 그러면서 정말 신기한 경험을 하게 되었는데 바로 예전에 잘 이해가 안가서 읽고 넘어갔던 내용들이 이제는 내 머릿속에서 자연스럽게 그려지는 경험을 하게 되었다. 그동안에 시간들이 헛되지는 않았나보다.

 

어느 곳에서나 기본기는 중요하듯이 이번 기회를 통해 자바 기본기를 더 단단히 다지고자 챕터별로 글로 정리하면서 다시 한번 암기를 하고 좀 더 디테일하게 알아야 되는 곳은 챕터를 나눠서 자바의정석에 나온 내용 + 보강된 내용을 더해서 정리를 하고자 한다. 

 

정리

---

컬렉션 프레임워크
데이터 군을 저장하는 클래스들을 표준화한 설계이다. 
java API문서에는 컬렉션 프레임웍을 데이터 군을 다루고 표현하기 위한 단일화된 구조라고 정의하고 있다.
jdk1.2 때 나왔고 jdk1.8때 람다와 스트림이 나오면서 컬렉션 프레임웍이 이루지 못한 다양한 종류의 데이터를 동일한 방식으로 다루는 것이 가능하게 됨

컬렉션 프레임웍의 핵심 인터페이스
컬렉션 데이터그룹을 다루는데 크게 3가지 타입이 존재한다고 인식하고 각 컬렉션을 다루는 3개의 인터페이스를 정의했다.
그리고 인터페이스 List와 Set의 공통된 부분은 다시 뽑아 Collection 인터페이스를 추가로 정의했다.
하지만 Map인터페이스는 이들과 전혀 다른 형태로 컬렉션을 다루기 때문에 같은 상속 계층도에 포함되지 못했다.
List - 순서가 있는 데이터의 집합, 데이터의 중복 허용 (구현클래스 - ArrayList/LinkedList/Stack/Vector)
Set - 순서를 유지하지 않는 데이터의 집합, 중복 허용하지 않음 (HashSet/TreeSet)
Map - 키와 값의 쌍으로 이루어진 데이터의 집합, 순서는 유지되지 않으며 키는 중복을 허용하지 않고 값을 중복을 허용함 (HashMap/TreeMap/Hashtable/Properties)

HashSet
Set인터페이스를 구현한 가장 대표적인 컬렉션이며 Set 특징대로 중복요소를 저장하지 않는다.
HashSet을 이용하면 컬렉션 내의 중복 요소들을 쉽게 제거할 수 있다. HashSet도 마찬가지로 저장순서를 유지하지 않으므로 저장순서를 유지하고자 한다면 LinkedHashSet을 사용해야 한다.

TreeSet
TreeSet은 이진 검색트리라는 자료구조의 형태로 데이터를 저장하는 컬렉션 클래스이다. 이진 검색 트리의 성능을 향상시킨 '레드블랙트리'로 구현되어 있다. 그리고 Set인터페이스를 구현했으므로 중복 저장 안되며 저장 순서를 유지하지도 않는다.
class TreeNode {
TreeNode left;
Object element; // 객체를 저장하기 위한 참조변수
TreeNode right; // 오른쪽 자식
}

 

LinkedList
배열은 가장 기본적인 형태의 자료구조로 구조가 간단하며 사용하기 쉽고 데이터를 읽어 오는데 걸리는 시간이 가장 빠르다는 장점을 가지고 있지만 크기를 변경할 수 없다는 점과 비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸린다는 단점으 가지고 있다. 이러한 점을 보완하기 위해 나온것이 LinkedList이다. 배열은 모든 데이터가 연속적으로 존재하지만 링크드 리스트는 불연속적으로 존재하는 데이터를 서로 연결한 형태로 구성되어 있다.
링크드 리스트의 각 요소들은 자신과 연결된 다음 요소에 대한 참조와 데이터로 구성되어 있다.

LinkedList 추가와 삭제
삭제는 삭제하고자 하는 요소의 이전 요소가 삭제하고자하는 요소의 다음 요소를 참조하도록 변경만 하면된다. 배열처럼 데이터를 이동하기 위해 복사하는 과정이 없기 때문에 처리 속도가 매우 빠르다.
추가도 마찬가지로 새로 추가하려는 위치의 이전 요소의 참조를 새로운 요소로 변경하고 새로운 요소가 그 다음 요소를 참조하도록 변경한다.

ArrayList와 LinkedList 비교
LinkedList는 불연속적으로 위치한 각 요소들이 서로 연결된 것이라 처음부터 n번째 데이터까지 차례대로 따라가야 원하는 값을 가져올 수 있다. 대신 추가 삭제는 빠르다. ArrayList는 읽기가 빠르고 LinkedList에 비해 추가 삭제가 느리다. 즉, 다루고자 하는 데이터의 개수가 변하지 않는 경우라면 ArrayList가 최상의 선택이 되겠지만 데이터 개수의 변경이 잦다면 LinkedList를 사용하는 것이 더 나은 선택이 될 것이다.

Stack과 Queue
Stack은 마지막에 저장한 데이터를 가장 먼저 꺼내게 되는 LIFO 구조, 큐는 처음 저장한 데이터를 가장 먼저 꺼내난 FIFO구조 이다.
Stack은 동전통, Queue는 파이프 구조로 생각.
Stack 구현시 ArrayList / Queue구현시 LinkedList로 구현하는 것이 적합
Stack st = new Stack();
Queue q = new LinkedList(); // Queue인터페이스의 구현체인 LinkedList 사용

Stack과 Queue의 활용
Stack ex - 수식계산, 수식괄호검사, 워드프로세서의 undo/redo, 웹브라우저의 뒤로 앞으로
Queue ex - 최근사용문서, 인쇄작업 대기목록, 버퍼

Iterator, ListIterator, Enumeration
3가지 모두 컬렉션에 저장된 요소를 접근하는데 사용되는 인터페이스이다.
Enumeration은 Iterator의 구버전이며, ListIterator는 Iterator의 기능을 향상 시킨 것이다.
Iterator - 컬렉션에 저장된 요소를 접근하는데 사용되는 인터페이스
ListIterator - Iterator에 양방향 조회 기능 추가 (List를 구현한 경우만 사용가능)
public interface Iterator {  // Iterator 인터페이스 정의
boolean hasNext();
Object next();
void remove();
}

public interface Collection { // Iterator를 구현한 클래스의 인스턴스를 반환하는 iterator()가 정의되어 있음
...
public Iterator iterator();
...
}
--> Collection인터페이스에 정의되어 있으므로 자손이 List와 Set에도 포함되어 있어서 List나 Set으로 구현하는 컬렉션은 iterator()를 사용 가능

Map과 Iterator
Map은 직접 Iterator()를 호출할 수 없고, 그 대신 keySet()이나 entrySet()과 같은 메서드를 통해서 키와 값을 각각 따로 Set의 형태로 얻어 온 후에 다시 iterator()를 호출해야 얻을 수 있다. 

Arrays 클래스
배열을 다루는데 유용한 메서드가 정의되어 있다.
copyOf() - 배열전체를 복사해서 새로운 배열을 만들어 반환
copyOfRange() - 배열의 일부를 복사해서 새로운 배열을 만들어 반환 (지정된 범위의 끝은 포함하지 않음)
fill() - 배열의 모든 요소를 지정된 값으로 채움
setAll() - 배열을 채우는데 사용할 함수형 인터페이스를 매개변수로 받음
sort() - 배열을 정렬
binarySearch() - 저장된 요소를 검색할때 사용, 검색한 값과 일치하는 요소들이 여러개 있다면 어떤 것의 위치가 반환될지는 알 수 없다.
-> 이유는 이진검색은 배열의 검색할 범위를 반복적으로 절반씩 줄여가면서 검색하기 때문에 검색속도가 상당히 빠르다. 단, 배열이 정렬이 되어 있는 경우에만 사용할 수 있다는 단점이 있다. 
equals() - 두 배열에 저장된 모든 요소를 비교해서 같으면 true, 다르면 false를 반환, 다차원 비교는 deepEquals() 사용
toString() - 일차원 배열에만 사용할 수 있다. 다차원배열에서는 deepToString()을 사용해야 한다. 3차원 이상에도 가능
asList() - 배열을 리스트로 변환
parallelXXX() - parallel로 시작하는 이름의 메서드들은 보다 빠른 결과를 얻기 위해 여러 쓰레드가 작업을 나누어 처리하도록한다
spliterator() - 여러 쓰레드가 처리할 수 있게 하나의 작업을 여러 작업으로 나누는 Spliterator를 반환
stream() - 컬렉션을 스트림으로 변환한다. 

이진 탐색 트리
- 모든 노드는 최대 두개의 자식노드를 가질 수 있다.
- 왼쪽 자식노드의 값은 부모노드의 값보다 작고 오른쪽 자식노드의 값은 부모노드의 값보다 커야한다.
- 노드의 추가 삭제에 시간이 걸린다 (순차적으로 저장하지 않으므로)
- 검색과 정렬에 유리하다.
- 중복된 값을 저장하지 못한다.

HashMap과 Hashtable
두 관게는 vector와 ArrayList의 관계와 같아서 새로운 버전이 HashMap을 사용하는 것을 권장한다.
해싱(hashing)을 사용하기 때문에 많은 양의 데이터를 검색하는데 있어서 뛰어난 성능을 보인다.

HashMap의 키와 값
키와 값을 각각 Object타입으로 저장하기 때문에 어떠한 객체도 저장할 수 있지만 키는 주로 String을 대문자 또는 소문자로 통일해서 사용하곤 한다.
키는 유일해야하며 값은 중복 가능

컬렉션의 동기화 - Collections의 메서드
멀티쓰레드 프로그래밍에서는 하나의 객체를 여러 쓰레드가 동시에 접근할 수 있기 때문에 데이터의 무결성을 유지하기 위해서는 공유되는 객체에 동기화가 필요하다. Vector와 Hashtable과 같은 구버전 1.2 이전 의 클래스들은 자체적으로 동기화 처리가 되어 있는데 멀티쓰레드 환경이 아닌 경우는 성능을 떨어뜨리는 요인이 되어 새로 추가된 ArrayList와 HashMap과 같은 컬렉션은 동기화를 자체적으로 처리하지 않고 필요한 경우에만 java.util.Collections클래스의 동기화 메서드를 이용해서 동기화 처리가 가능하도록 변경하였다.

변경불가 컬렉션 만들기 - Collections의 메서드
컬렉션에 저장된 데이터를 보호하기 위해서 컬렉션을 변경할 수 없게, 즉 읽기 전용으로 만들어야 할때가 있
unmodifiableCollection(Collection c)
unmodifiableList(List list)
unmodifiableSet(Set s)
unmodifiableMapCMap m)
unmodifiableNavigableSet(NavigableSet s)
unmodifiableSortedSet(SortedSet s)
unmodifiableNavigableMapCNavigableMap m)
unmodifiableSortedMap(SortedMap m)

싱글톤 컬렉션 만들기
단 하나의 객체만을 저장하는 컬렉션을 만들어야 하는 경우에 사용