자바 3

• 컬렉션 프레임워크(collection framework) -> 다수의 데이터를 다루기 위한 것
  🔸 컬렉션 collection : 여러 객체(데이터)를 모아 놓은 것을 의미
  🔸 프레임워크 framework : 표준화, 정형화 된 체계적인 프로그래밍 방식
  🔸 컬렉션 프레임워크 collection framework
  - 컬렉션(다수의 객체)을 다루기 위한 표준화 된 프로그래밍 방식
  - 컬렉션을 쉽고 편리하게 다룰 수 있는 다양한 클래스를 제공
  - java.util패키지에 포함. JDK1.2부터 제공
  🔸 컬렉션 클래스 collection class : 다수의 데이터를 저장할 수 있는 클래스 (예: Vector, ArrayList, HashSet)

• 컬렉션 프레임워크의 핵심 인터페이스

1. List
   - 순서가 있는 데이터의 집합. 데이터의 중복 허용
   - (ex)대기자 명단 (구현클래스) ArrayList, LinkedList, Stack, Vector
2. Set(집합)
   - 순서 유지x. 중복 허용x
   - (ex) 양의 정수집합, 소수의 집합 (구현클래스) HashSet, TreeSet
3. Map
   - 키key와 값value의 쌍pair으로 이루어진 데이터의 집합
   - 순서x key값 중복x value값 중복o
   - (ex) 우편번호, 지역번호 (구현클래스) HashMap, TreeMap, HashTable, Properties
4. List와 Map의 공통부분을 뽑아서 Collection 인터페이스를 만듦

• ArrayList
  - ArrayList는 기존의 Vector를 개선한 것으로 구현원리와 기능적으로 동일. ArrayList와 달리 Vector는 자체적으로 동기화처리가 되어 있다.
  - List 인터페이스를 구현하므로, 저장순서가 유지되고 중복을 허용한다.
  - 데이터의 저장공간으로 배열을 사용한다.(배열기반)

• LinkedList - 배열의 장단점
  🔹 장점 : 배열은 구조가 간단하고 데이터를 읽는 데 걸리는 시간이 짧다.
  🔸 단점 1. 크기를 변경할 수 없다.
  - 크기를 변경해야 하는 경우 새로운 배열을 생성 후 데이터를 복사해야 함.
  - 크기 변경을 피하기 위해 충분히 큰 배열을 생성하면, 메모리가 낭비됨.
  단점 2. 비순차적인 데이터의 추가, 삭제에 시간이 많이 걸린다.
  - 데이터를 추가하거나 삭제하기 위해, 다른 데이터를 옮겨야 함.
  - 그러나 순차적인 데이터 추가(끝에 추가)와 삭제(끝부터 삭제)는 빠르다.

  • LinkedList - 배열의 단점을 보완
    - 배열과 달리 링크드 리스트는 불연속적으로 존재하는 데이터를 연결
    - 데이터의 삭제 -> 단 한 번의 참조변경만으로 가능
    - 데이터의 추가 -> 한 번의 Node 객체생성과 두 번의 참조변경만으로 가능
  • LinkedList - 이중 연결 리스트
    - 링크드 리스트 linked list : 연결리스트. 데이터 접근성이 나쁨
    - 더블리 링크드 리스트 doubly linked list : 이중 연결리스트, 접근성 향상
    - 더블리 써큘러 링크드 리스트 doubly circular linked list : 이중 원형 연결리스트
  • ArrayList vs LinkedList - 성능 비교
  1. 순차적으로 데이터를 추가/삭제 - ArrayList가 빠름
  2. 비순차적으로 데이터를 추가/삭제 - LinkedList가 빠름
  3. 접근시간 - ArrayList가 빠름
  • 스택Stack과 큐Queue
    - 스택Stack : LIFO구조. 마지막에 저장된 것을 제일 먼저 꺼내게 된다.
    - 큐Queue : FIFO구조. 제일 먼저 저장한 것을 제일 먼저 꺼내게 된다.

    스택의 활용 예 : 수식계산, 수식괄호검사, 워드프로세서의 undo/redo, 웹브라우저의 뒤로/앞으로
    큐의 활용 예 : 최근사용문서, 인쇄작업 대기목록, 버퍼(buffer)

• Iterator, ListIterator, Enumeration
  - 컬렉션에 저장된 데이터를 접근하는데 사용되는 인터페이스
  - Enumeration은 Iterator의 구버전
  - ListIterator는 Iterator의 접근성을 향상시킨 것(단방향 -> 양방향)
  - 컬렉션에 저장된 요소들을 읽어오는 방법을 표준화 한 것
  - 컬렉션에 Iterator()를 호출해서 Iterator를 구현한 객체를 얻어서 사용

• Map과 Iterator
  - Map에는 iterator()가 없다. keySet(), entrySet(), Values()를 호출해야 한다.

Map map = new HashMap();
		...
Iterator it = map.entrySet().iterator();

• Arrays : 배열을 다루기 편리한 메서드(static) 제공

1. 배열의 출력 - toString()
2. 배열의 복사 - copyOf(), copyOfRange()
3. 배열 채우기 - fill(), setAll()
4. 배열의 정렬과 검색 - sort(), binarySearch()
5. 다차원 배열의 출력 - deepToString()
6. 다차원 배열의 비교 - deepEquals()
7. 배열을 List로 변환 - asList(Object...a)

• 향상된 for문 : 배열에서 요소를 순서대로 꺼내 i에다 넣는다

for(int i : 배열이름) 

• Comparator와 Comparable
  - 객체 정렬에 필요한 메서드(정렬기준 제공)를 정의한 인터페이스

  Comparable 기본 정렬기준을 구현하는데 사용
  Comparator 기본 정렬기준 외에 다른 기준으로 정렬하고자 할 때 사용

  public interface Camparator {
  	int compare(Object o1, Object o2); //o1, o2 두 객체를 비교
      Boolean equals(Object obj); //equals를 오버라이딩하라는 뜻
  }
  public interface Comparable {
  	int compareTo(Object o); //주어진 객체(o)를 자신과 비교
  }

  - compara()와 compareTo()는 두 객체의 비교결과를 반환하도록 작성.
  같으면 0, 오른쪽이 크면 음수, 작으면 양수

  public final class Integer extends Number implements Comparable {
  	...
    public int comparaTo(Integer anotierInteger) {
    	int v1 = this.value;
     int v2 = anotherInteger.value;
     // 같으면 0, 오른쪽 값이 크면 -1, 작으면 1을 반환
     return (v1 < v2 ? -1 : (v1 == v2 ? 0: 1));
    }
    ...
  }

• ⛔ Integer와 Comparable ⛔

• HashSet - 순서X, 중복X
  - HashSet은 객체를 저장하기 전에 기존에 같은 객체가 있는지 확인. 같은 객체가 없으면 저장하고, 있으면 저장하지 않는다.
  - boolean add(Object o)는 저장할 객체의 equals()와 hastCode()를 호출 -> equals()와 hashCode()가 오버라이딩 되어 있어야 함

  🔸 HashSet
  - Set 인터페이스를 구현한 대표적인 컬렉션 클래스
  - 순서를 유지하려면 LinkedHashSet클래스를 사용하면 된다.

  🔸 TreeSet
  - 범위 검색과 정렬에 유리한 컬렉션 클래스
  - HashSet보다 데이터 추가, 삭제에 시간이 더 걸림

• TreeSet - 범위 탐색, 정렬
  - 이진 탐색 트리binary search tree로 구현. 범위 탐색과 정렬에 유리
  - 이진 트리는 모든 노드가 최대 2개의 하위 노드를 가짐
  - 각 요소node가 나무tree 형태로 연결(LinkedList의 변형)

  class TreeNode {
  	TreeNode left;    //왼쪽 자식노드
     Object   element; //저장할 객체
     TreeNode right;   //오른쪽 자식노드
  }

• 이진 탐색 트리 binary search tree
  - 부모보다 작은 값은 왼쪽, 큰 값은 오른쪽에 저장
  - 데이터가 많아질 수록 추가, 삭제에 시간이 더 걸림(비교 횟수 증가)

• TreeSet - 데이터 저장과정 boolean add(Object o)
  - TreeSet에 7,4,9,1,5의 순서로 데이터를 저장하면, 루트부터 트리를 따라 내려가며 값을 비교. 작으면 왼쪽, 크면 오른쪽에 저장
  - 범위검색에 유용한 메서드 제공 : subSet(), headSet(), tailSet()

• 트리 순회 tree traversal
  - 이진 트리의 모든 노드를 한번씩 읽는 것을 트리 순회라고 한다.
  - 전위, 중위, 후위 순회법이 있으며, 중위 순회하면 오름차순으로 정렬된다.

• HashMap과 Hashtable - 순서 X, 중복(키X, 값O)
  - Map인터페이스를 구현. 데이터를 키와 값의 쌍으로 저장
  - HashMap(동기화X)은 Hashtable(동기화 O)의 신버전

  🔸 HashMap
  - Map인터페이스를 구현한 대표적인 컬렉션 클래스
  - 순서를 유지하려면, LinkedHashMap클래스를 사용하면 된다.

  🔸 TreeMap
  - 범위 검색과 정렬에 유리한 컬렉션 클래스
  - HashMap보다 데이터 추가, 삭제에 시간이 더 걸림

• HashMap의 키(key)와 값(value)
  - 해싱hashing기법으로 데이터를 저장. 데이터가 많아도 검색이 빠르다.
  - Map인터페이스를 구현. 데이터를 키와 값의 쌍으로 저장

  키(key) : 컬렉션 내의 키(key)중에서 유일해야 한다.
  값(value) : 키(key)와 달리 데이터의 중복을 허용한다.

• 해싱(hashing)
  - 해시함수hash function로 해시테이블hash table에 데이터를 저장하고 읽어오는 것
  - 해시테이블은 배열과 링크드 리스트가 조합된 형태
  - 예시) 병원에서 환자정보를 저장하는 캐비닛

🔸 해시테이블에 저장된 데이터를 가져오는 과정
1. 키로 해시함수를 호출해서 해시코드를 얻는다.
2. 해시코드(해시함수의 반환값)에 대응하는 링크드리스트를 배열에서 찾는다.
3. 링크드리스트에서 키와 일치하는 데이터를 찾는다.
(+) 해시함수는 같은 키에 대해 항상 같은 해시코드를 반환해야 한다. 서로 다른 키일지라도 같은 값의 해시코드를 반환할 수도 있다.

• Collections - 컬렉션을 위한 메서드(static)를 제공

1. 컬렉션 채우기, 복사, 정렬, 검색 - fill(), copy(), sort(), binarySearch() 등
2. 컬렉션의 동기화 - synchronizedXXX()
3. 변경불가 컬렉션 만들기 - unmodifiableXXX()
4. 싱글톤 컬렉션 만들기 - singletonXXX() <- 객체 한개만 저장?
5. 한 종류의 객체만 저장하는 컬렉션 만들기 - checkedXXX()

• 컬렉션 클래스 정리&요약