컬렉션 프레임워크의 핵심 인터페이스
- Collection : List, Set
- Map
List, Set은 비슷한 부분이 많아 Collection 인터페이스를 정의할 수 있었지만, Map은 전혀 달라서 따로 인터페이스를 제작.
- List : 순서가 있는 데이터 집합, 중복 허용
- Set : 순서 유지하지 않는 집합, 중복 허용 X
- Map : Key value의 쌍으로 이루어진 데이터 집합
Collection 인터페이스
List와 Set의 공통부분을 정의한 조상객체 Collection에서는 다음과 같은 메서드가 정의
List 인터페이스
중복을 허용하면서 저장순서가 유지되는 컬렉션
Set 인터페이스
중복을 허용하지 않고 저장 순서가 유지되는 컬렉션
Map 인터페이스
키(key)와 값(value)를 하나의 쌍으로 묶어 저장하는 컬렉션
키는 중복이 허용되지 않지만, 값은 중복을 허용한다.
다양한 컬렉션 리스트
ArrayList
- 컬렉션 프레임웍에서 가장 많이 사용되는 컬렉션 클래스.
- List 인터페이스를 구현하기에 데이터의 저장순서가 유지되고 중복을 허용한다.
- Vector를 개선한 클래스로 구현원리나 기능측면에서 유사점이 많다.
- Object 배열을 이용해 데이터를 순차적으로 저장한다.
- 배열을 저장할 공간이 부족해지면 더 큰 배열을 생성해 기존 내용을 복사한 뒤 그 다음 저장한다.
장단점
- 장점
- 배열은 구조가 간단하고 데이터를 읽는데 걸리는 시간이 짧다.
- 단점
- 크기를 변경할 수 없다.
⇒ 크기를 변경해야 하는경우 새로운 배열을 생성후 데이터를 복사해야 한다.
⇒ 변경을 막기위해 초기에 크기를 크게 잡으면 메모리가 낭비된다. - 비순차적인 데이터의 추가, 삭제에 시간이 많이 걸린다.
⇒ 데이터를 추가하거나 삭제하기위해, 다른 데이터를 옮겨야 한다.
⇒ 다만, 순차적인 데이터 추가(끝에 추가)와 삭제(끝부터 삭제)는 빠르다.
- 크기를 변경할 수 없다.
LinkedList
- 배열이 가진 장점과 단점중 단점이였던 크기변경의 제약과, 비순차적인 데이터의 추가및 삭제에 걸리는 시간을 개선하기위해 나온 자료구조가 LinkedList이다.
- 불연속적으로 존재하는 데이터를 서로 연결(link)한 형태로 구성되어 있다.
정리
List를 구현하는 두가지 자료구조인 ArrayList와 LinkedList는 서로 장단점이 있어 필요에 따라 사용하면 된다.
- ArrayList : 데이터 접근이 빠르지만 비순차적인 데이터 추가/삭제가 느리다.
- LinkedList: 데이터 접근이 느리지만 비순차적인 데이터 추가/삭제가 빠르다.
Stack과 Queue
- 스택(Stack): LIFO(Last In First Out)구조로 마지막에 저장된 것을 첫 번째로 꺼낸다.
- 큐(Queue): FIFO(First In First Out)구조로 첫 번째로 저장한 것을 첫 번째로 꺼낸다.
스택 메소드
큐 메소드
Queue의 변형 - Deque, PriorityQueue, BlockinigQueue
자바에서 Queue는 인터페이스로 이를 구현한 여러 구현체가 있는데, 몇가지 구조를 소개한다.
PriorityQueue - 우선순위 큐
⇒ 저장한 순서에 관계없이 우선순위가 높은것부터 꺼내는 특징이 있다.
⇒ Null은 저장할 수 없다.
⇒ 저장공간으로 배열을 사용하며 각 요소는 힙(heap)이라는 자료구조의 형태로저장한다.
(힙은 이진트리의 한 종류로 가장 큰 값이나 가장 작은 값을 빠르게 찾을 수 있는 특징이 있다.)
⇒ 예) 입력[5,3,1,4,2] → 출력[1,2,3,4,5]
⇒ 객체를 넣을때는 비교할 수 있는 방법을 제공해야 한다.
⇒ 기본타입은 래퍼클래스로 오토박싱(auto-boxing)되며 해당 래퍼 클래스에서 비교하는 로직을 정의하고있기에 사용이 가능한 것이다.
Deque(Double-Ended Queue)
⇒ Stack과 Queue의 결합으로 양 끝에서 저장(offer)과 삭제(poll)이 가능하다.
⇒ 구현클래스는 ArrayDeque, LinkedList가 있다.
⇒ 스택 혹은 큐로 사용할 수 있다.
BlockingQueue - 블로킹 큐
⇒ 비어있을 때 꺼내기와 가득 차 있을 때 넣기를 지정된 시간동안 지연시킨다(block)
⇒ 멀티쓰레드에서 사용할 수 있다.
Enumeration, Iterator, ListIterator
- 컬렉션에 저장된 데이터를 접근하는데 사용되는 인터페이스
- Enumeration은 Iterator의 구 버전
- ListIterator는 Iterator의 접근성을 향상시킨 것(단방향 → 양방향)
Iterator
- 컬렉션에 저장된 요소들을 읽어오는 방법을 표준화한 인터페이스
- 기존에는 각각의 데이터군집 클래스들이 데이터를 순회하는 방법들이 모두 달랐다.
지원 메서드
ListIterator
- Iterator의 접근성을 단방향에서 양방향으로 확장시킨 것
지원 메서드
Arrays
- 배열을 다르눈데 도움을 주는 메서드가 정의된 유틸 클래스
-
배열의 출력 - toString()
모든 타입 매개변수에 대해 대응된다. -
배열의 복사 - copyOf(), copyOfRange()
배열 전체를 복수할 때는 copyOf(), 배열의 일부 범위만 복사할때는 copyOfRange()를 사용한다.
-
배열 채우기 - fill(), setAll()
fill()은 배열의 모든 요소를 지정된 값으로 채운다.
setAll()은 배열을 채우는데 사용할 함수형 인터페이스를 매개변수로 받는다.
⇒ 함수형 인터페이스를 구현할 객체를 매개변수로 지정하던가 람다식을 사용한다. -
배열의 정렬과 검색 - sort(), binarySearch()
sort() 메서드는 배열을 정렬해준다.
binarySearch()메서드는 이진검색 알고리즘으로 요소를 검색하는데, 범위가 절반씩 줄어들기에 검색 속도가 빠르다. 하지만, 배열이 정렬되어있어야 한다는 단점이 있다. -
문자열의 비교와 출력 - equals(), deepEquals(), toString(), deepToString()
toString()은 위에 작성한것처럼 요소를 편하게 출력하게 해주는 메서드.
deepToString()은 다차원 배열에서 사용하는 메서드로 모든 요소를 재귀적으로 접근해 문자열을 구성한다.
equals()메서드는 배열의 모든 요소를 비교해 같으면 true를 반환하는 메서드이다.
deepEquals()메서드는 다차원 배열간 비교할 때 사용하는 메서드이다.
- 배열을 List로 변환 - asList(Object... obj)
배열을 List에 담아 반환하는 메서드
가변인자 타입이라 저장할 요소들만 나열하는 식으로 사용이 가능하다.
- parallelXXX(), spliterator(), stream()
parallel : 여러 쓰레드가 작업을 나누어 처리
spliterator() : 여러 쓰레드가 처리할 수 있게 하나의 작업을 여러 작업으로 나누는 Spliterator 반환
stream() : 컬렉션을 스트림으로 변환
HashSet
순서가 없고, 중복도 없는 Set 컬렉션 구현체.
- HashSet은 내부적으로는 HashMap을 이용해 만들어졌으며 해싱(hashing)을 이용해 구현했기에 붙혀진 이름.
- 지원 메서드 자체는 List와 같은 Collection 인터페이스
- HashSet은 객체를 저장하기전 중복이 존재하는지 확인한 뒤 중복이 아닐 경우에만 저장한다.
⇒ 중복일 경우 false를 반환한다. - HashSet은 저장 순서를 유지하지 않기에 저장 순서를 유지하고자 한다면 LinkedHashSet을 사용해야 한다.
- 요소를 추가(add , addAll)하기 전 요소의 중복 검사를 하는데, 이 검사를 위해 equals() and hashCode()를 사용해 비교하기 때문에, 오버라이딩 되어 있어야 한다.
TreeSet
순서가 없고, 중복도 없는 Set 컬렉션 구현체.
이진 검색 트리(binary search tree) 자료구조 형태의 컬렉션 클래스
- 정렬, 검색, 범위검색에 높은 성능을 보인다.
- 레드-블랙 트리(Red-Black tree)로 구현되어 있다.
- LinkedList처럼 여러 노드(Node)가 서로 연결된 구조이다.
- 각 노드는 최대 2개의 노드를 연결할 수 있다.
- 최초의 루트(Root)노드부터 시작해 계속 확장해 나갈 수 있다.
이진 검색 트리(binary search tree)의 특징
→ 모든 노드는 최대 2개의 자식노드를 가질 수 있다.
→ 왼쪽 자식노드의 값은 부모노드의 값보다 작고 우측자식노드의 값은 부모노드의 값보다 커야 한다.
→ 노드의 추가 삭제가 오래걸린다(순차적으로 지정하지 않음)
→ 검색(범위검색)에 유리하다.
→ 중복된 값을 저장하지 못한다.
범위 검색 - subSet(), headSet(), tailSet()
headSet(Object toElement)를 이용해 toElement보다 작은 객체들을 반환
tailSet(Object fromElement)를 이용해 toElement보다 큰 객체들을 반환
HashMap
순서가 없고, 키의 중복은 허용하지 않으나 값의 중복은 허용하는 데이터 군집 관리 컬렉션
- Hashtable의 신 버전이 HashMap이다. 그렇기에 Hashtable보다는 HashMap을 사용하도록 하자.
→ Hashtable은 동기화가 되기때문에 동기화가 되지 않는 HashMap이 나왔다. - 순서를 유지하고싶다면 LinkedHashMap 클래스를 사용하면 된다.
- 해싱(hashing)기법으로 데이터를 저장하며 데이터가 많아도 검색이 빠르다.
- Map 인터페이스를 구현했으며 데이터를 키와 값의 쌍(pair)으로 저장한다.
- 내부에 키(key)와 값(value)을 갖는 Entry라는 내부 클래스를 정의해 해당 클래스의 객체 배열로써 관리한다.
출처: 자바의 정석, https://catsbi.oopy.io/8f0f5192-3a06-405e-8076-dbc5ff9f2dfb
