List

데이터의 저장 순서가 유지되고 중복을 허용한다.

ArrayList

기존의 Vector을 구현한 것이다.
내부적으로 Object 배열을 이용해서 데이터를 순차적으로 저장한다.
생성자를 통해 배열의 크기를 설정할 수 있다.

장점

• 배열의 크기가 충분할때, 순차적으로 저장하거나 맨 뒤에서부터 순차적으로 삭제할때 빠르다.

• 임의의 요소에 접근할때 가장 빠르다.

단점

• 크기를 변경할 수 없기 때문에 메모리 낭비가 발생 할 수 있다.

• 비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸린다.
  만약 배열의 중간에 데이터를 추가하려면, 빈자리를 만들기 위해 다른 데이터들을 복사해서 이동해야한다.

LinkedList

Java 의 LinkedList 는 더블 링크드 리스트형태로 구현돼있다.
불연속적으로 존재하는 데이터를 서로 연결한 형태로 구성돼있다.
각 node들은 자신과 연결된 이전 요소와 다음 요소에 대한 참조와 데이터로 구성돼있다.

class Node{
	Node next;
    	Node previous;
    	Object obj;
}

장점

• 중간 데이터를 추가/삭제하는 경우에 속도가 매우 빠르다. 각 요소간의 연결만 변경해주면 되기 때문이다.

단점

• 순차적으로 추가/삭제하는 경우에는 상대적으로 느리다.

• 요소에 접근하는 속도는 느리다. 왜냐하면 각 요소들이 불연속적으로 위치하기 때문에, 요소의 처음부터 n까지 차례대로 따라가야 한다.

---

Stack & Queue

Stack

스택은 후입선출이다. LIFO (Last In First Out) 구조다.
자바의 Stack 클래스는 컬렉션 프레임웍 이전부터 존재했다.
그래서 ArrayList 가 아닌 Vector로부터 상속받아 구현했다.

Queue

큐는 선입선출이다. FIFO (First In First Out) 구조다.

구현체

• PriorityQueue
  저장한 순서에 관계없이 우선순위가 높은 것부터 꺼내게 된다.
  null은 저장할 수 없다.
  
• Deque(Double-Ended Queue)
  양쪽 끝에 추가/삭제가 가능하다.
  구현체로는 ArrayDeque 와 LinkedList 등이 있다.
  스택과 큐를 하나로 합쳐놓은 것과 같다.

---

Iterator

Iterator, ListIterator, Enumeration 은 모두 컬렉션에 저장된 요소를 접근하는데 사용되는 인터페이스이다.
Enumeration은 Iterator 의 구버전이고,
ListIterator 는 Iterator 의 기능을 향상시킨 것이다.

Iterator

Collection 인터페이스에 정의된 메서드이므로 Collection 인터페이스의 자손인 List와 Set에도 포함되어 있다.
단방향으로만 이동할 수 있다. ( iterator.next() )
next() 를 호출하고 remove()를 호출해야 한다.

ListIterator

Iterator는 단방향으로만 이동할 수 있는 데 반해 ListIterator는 양방향으로의 이동이 가능하다.
다만 List를 구현한 컬렉션에서만 사용할 수 있다.
next() 를 호출하고 remove()를 호출해야 한다.

---

Arrays

배열을 다루는데 유용한 메서드가 정의되어 있다.

Arrays 클래스의 메서드

• copyOf(), copyOfRange()
  copyOf()는 배열 전체를,
  copyOfRange()는 배열의 일부를 복사해 새로운 배열을 만들어 반환한다.

• fill(), setAll()
  fill()은 배열의 모든 요소를 지정된 값으로 채운다.
  setAll()은 배열을 채우는데 사용할 함수형 인터페이스를 매개변수로 받는다.

• sort(), binarySearch()
  sort() 는 배열을 정렬할때,
  binarySearch() 는 정렬된 배열의 요소를 검색하는데 사용한다.

• equals(), toString()
  equals() 는 요소를 비교한다.
  toString()은 배열을 문자열로 바꿔준다.

• asList(Objet.. a)
  배열을 List에 담아서 반환한다.
  asList()가 반환한 List의 크기를 변경할 수 없다.
  (UnsupportedOperationException 발생함)

• parallelXXX(), spliterator(), stream()
  parallel로 시작하는 메서드들은 보다 빠른 결과를 얻기 위해 여러 쓰레드가 작업을 나누어 처리한다.
  spliterator()는 여러 쓰레드가 처리할 수 있게 하나의 작업을 여러 작업으로 나누는 Spliterator를 반환한다.
  stream()은 컬렉션을 스트림으로 변환한다.

---

Comparator & Comparable

이 둘은 모두 인터페이스로 컬렉션을 정렬하는데 필요한 메서드를 정의하고 있다.

Comparator

Comparable을 구현하고 있는 클래스들은 같은 타입의 인스턴스끼리 서로 비교할 수 있는 클래스들, 주로 Integer 와 같은 wrapper클래스와 String, Date, File과 같은 것들이다.
기본적으로 오름차순으로 정렬되도록 구현되어있다.

Comparator

기본 정렬기준외에 다른 기준으로 정렬하고자 할때 사용한다.

---

Set

중복을 허용하지 않는다.

HashSet

저장 순서를 유지하지 않는다.
저장 순서를 유지하고자 한다면 LinkedHashSet을 사용해야 한다.

• 주의점
  특정 클래스가 equals() 메서드를 오버라이딩 하지 않았으면
  그 클래스의 두 객체가 내용이 같더라도 같은 객체로 판단하지 않는다.
  왜냐하면 equals() 메서드는 기본적으로 인스턴스의 주소값을 갖고
  같은지 판단하기 때문이다.

TreeSet

이진 검색 트리라는 자료구조의 형태로 데이터를 저장한다.
이진 검색 트리의 성능을 향상시킨 Red-Black tree로 구현되어있다.
저장 순서를 유지하지 않는다.
항상 오름차순으로 정렬된다.

이진 검색 트리

• 모든 노드는 최대 두개의 자식 노드만 갖는다.

• 왼쪽 자식노드의 값은 부모노드의 값보다 작고 오른쪽 자식 노드의 값은 부모노드의 값보다 커야한다.

• 노드의 추가와 삭제에 시간이 걸린다.

• 검색 ( 범위검색 ) 과 정렬에 유리하다.

• 중복된 값을 저장하지 못한다.

---

Map

키와 값을 쌍으로 갖는 자료구조다.

HashMap

해싱을 사용하기 때문에 많은 양의 데이터를 검색하는데 있어 뛰어난 성능을 보인다.
Entry라는 내부 클래스를 정의하고, 다시 Entry 타입의 배열을 선언한다.

Entry[] table;
class Entry{
	Object key;
	Object value;
}

키는 유일해야하지만 값을 중복을 허용한다.

장점

• 추가, 삭제, 검색, 접근성이 모두 뛰어나다. 검색에는 최고 성능을 보인다.

단점

• 성능이 해시코드를 만드는 해시함수에 달려있다.
  만약 중복되는 해시코드를 많이 만들어내는 해시함수를 사용한다면 성능이 저하된다.

Hashing

• 배열과 링크드리스트의 조합으로 된 자료구조를 사용한다.

• 저장할 데이터의 키를 해시함수에 넣으면 배열의 한 요소를 얻고, 다시 그곳에 연결되어있는 링크드 리스트에 저장하게 된다.

TreeMap

이진 검색 트리의 형태로 키와 값의 쌍으로 이루어진 데이터를 저장한다.
검색과 정렬에 적합한 컬렉션 클래스이다.
대부분의 경우 HashMap이 TreeMap보다 검색 성능이 뛰어나다.

장점

• 정렬과 검색(특히 범위검색)에 적합하다.

단점

• 검색 성능은 HashMap보다 떨어진다.

---

Collections

컬렉션과 관련된 메서드를 제공한다.
fill(), copy(), sort(), binarySearch()를 포함한다.

컬렉션의 동기화

Vector 와 Hashtable과 같은 구버전(JDK1.2 이전) 의 클래스들은 자체적으로 동기화 처리가 되어 있다.
하지만 불필요한 경우도 있어서 새로 추가된 ArrayList와 HashMap과 같은 컬렉션은 동기화를 자체적으로 처리하지 않고 필요한 경우에만 java.util.Collections 클래스의 동기화 메서드를 이용해서 동기화 처리가 가능하도록 변경하였다.

동기화 메서드들은 synchronized 가 메서드 이름 앞에 붙는다.

변경 불가 컬렉션

컬렉션을 읽기전용으로 만들 수 있는 메서드들을 제공한다.
메서드 이름 앞에 unmodifiable 이 붙는다.

싱글톤 컬렉션

단 하나의 객체만을 저장하는 싱글톤 컬렉션을 만들 수 있는 메서드들을 제공한다.
메서드 이름 앞에 singleton 이 붙는다.

---