ch11-1 컬렉션 프레임웍(collections framework)

여러번 반복, 빠르게, 전체적으로, 실습중요 어떻게, 언제 쓰는지

컬렉션(collection)

• 여러 객체(데이터)를 모아 놓은 것을 의미

프레임웍(framework, 작업틀)

• 표준화, 정형화된 체계적인 프로그래밍 방식
• 생산성 증가, 유지보수 쉬움

컬렉션 프레임웍(collections framework)

• 컬렉션(다수의 객체)을 다루기 위한 표준화된 프로그래밍 방식
• 컬렉션을 쉽고 편리하게 다룰 수 있는 다양한 클래스를 제공
  (저장, 삭제, 검색, 정렬)
  -java.util패키지에 포함. JDK1.2부터 제공

컬렉션 클래스(collection class)

• 다수의 데이터를 저장할 수 있는 클래스
  (예, Vector, ArrayList, HashSet)

ch11-2 컬렉션 프레임웍의 핵심 인터페이스

(컬렉션 프레임웍: 다수의 data)

List

순서O, 중복O
예)대기자 명단
ArrayList, LinkedList, Stack, Vector 등

Set

순서X, 중복X
예)(집합)양의 정수집합, 소수의 집합
HashSet, TreeSet 등

Map

키(key), 값(value)의 쌍으로 이루어진 데이터의 집합
순서X, 키(아이디)-중복X, 값(패스워드)-중복O
HashMap, TreeMap 등

Collection

List, Set의 공통부분을 모음.

ch11-3 Collection인터페이스의 메서드

메서드

(추가)
add(Object o)
addAll(Collection c)
//객체들을 Collection에 추가

(전체 삭제)
void clear()
//Collection의 모든 객체를 삭제

(검색)
contains(Object o)
containsAll(Collection c)
//객체들이 Collection에 포함되어있는지 확인

equals(Object o)
//동일한지 비교

hashCode()
//hash code를 반환

isEmpty()
//비어있는지 확인

iterator()
//iterator를 얻어서 반환

(삭제)
remove(Object o)
removeAll(Collection c)
//객체를 삭제

retainAll(Collection c)
//지정된 객체만을 남기고 다른 객체들은 Collection에서 삭제
//이 작업으로 Collection에 변화가 있으면 true, 아니면 false반환

size()
//저장된 객체의 개수를 반환

toArray()
//객체를 객체배열로 반환
toArray(Object[] a)
//객체를 저장해서 반환

ch11-4 List인터페이스 - 순서O, 중복O

ArrayList
LinkedList

ch11-5 Set인터페이스 - 순서X, 중복X

HashSet, TreeSet

Set인터페이스의 메서드=Collection인터페이스와 동일

• 집합과 관련된 메서드 존재(Collection에 변화 있으면 true, 아니면 false)
  (boolean을 반환)

addAll(Collection c) : 추가, 합집합
containsAll(Collection c) : 확인, 부분집합
removeAll(Collection c) : 삭제, 차집합
retainAll(Collection c) : 나머지만 삭제, 교집합

ch11-6 Map인터페이스 - 순서X, 중복(키X,값O)

HashMap, TreeMap
LinkedHashMap(순서O)

ch11-7 ArrayList

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

ch11-8 ArrayList의 메서드

생성자

ArrayList()
ArrayList(Collection c)
ArrayList(배열의 길이)

메서드

(추가)
add(int index, Object element)
addAll(int index, Collection c)

(검색)
indexOf(Object o)
//위치를 반환
lastIndexOf(Object o)
//역방향부터 찾음
contains(Object o)

(읽기)
get(int index)

(변경)
set(int index, Object element)
//지정된 위치에 객체를 저장

(삭제)
remove(Object o)
remove(int index)
//삭제하고, 삭제된 객체를 반환
removeAll(Collection c)
clear()
//모듣 객체 삭제

(그 외)
sort(Comparator c)
//정렬
subList(from, to)
//새로운 리스트 만듬, 읽기전용
toArray()
//객체배열을 반환
isEmpty()
//비어있는지
trimToSize()
//빈공간제거
size()
//저장된 객체의 개수

ch 11-10 ArrayList에 저장된 객체의 삭제과정

1. ArrayList에 저장된 첫 번째 객체부터 삭제하는 경우
   --> 배열 복사 발생

2. ArrayList에 저장된 마지막 객체부터 삭제하는 경우
   --> 배열 복사 발생 X

open Declaration

--> 실제 소스 확인 가능

ch11-12 LinkedList - 배열의 장단점

장점 : 배열은 구조가 간단하고 데이터를 읽는데 걸리는 시간이 짧다

(접근시간, access time)이 짧다.

단점 1 : 실행 중에 크기를 변경할 수 없다.

• 크기를 변경해야 하는 경우

1. 더 큰 배열 생성
2. 복사
3. 참조 변경

• 크기 변경을 피하기 위해 충분히 큰 배열을 생성하면, 메모리가 낭비됨.

단점 2 : 비순차적인 데이터의 추가, 삭제에 시간이 많이 걸림.

• 데이터를 추가하거나 삭제하기 위해, 다른 데이터를 옮겨야 함.
• 그러나 순차적인 데이터 추가(끝에 추가)와 삭제(끝부터 삭제)는 빠르다.

LinkedList - 배열의 단점을 보완

• 배열과 달리 불연속적으로 존재하는 데이터를 연결(link)

• 데이터의 삭제 : 단 한번의 참조변경만으로 가능
  (기차 연결)

• 데이터의 추가 : 한번의 Node객체생성과 두 번의 참조변경만으로 가능

LinkedList - 이중 연결 리스트

• 링크드 리스트 - 연결리스트. 데이터 접근성이 나쁨
  (순차적으로 이동해야함, 뒤로 이동 불가, 자기 다음밖에 모름, 한번에 접근 불가)
• 더블리 링크드 리스트 - 이중 연결리스트, 접근성 향상
  (앞뒤로 이동 가능)
• 더블리 써큘러 링크드 리스트 - 이중 원형 연결리스트
  (첫번째요소 앞으로 가면 맨끝으로 이동, 맨끝의 다음으로 가면 맨앞으로 이동)

ch11-15 스택과 큐(Stack & Queue)

스택(Stack) : LIFO구조. 마지막에 저장된 것을 제일 먼저 거내게 된다.

(밑이 막힌 상자)
저장(push) <->(순서가 반대) 추출(pop)
LIFO(Last In First Out) : 마지막 저장한게 제일 먼저 꺼냄

큐(Queue) : FIFO구조. 제일 먼저 저장한 것을 제일 먼저 꺼냄.

(밑에 뚫린 상자, 줄서기와 비슷)
저장(offer), 추출(poll)
FIFO(First In First Out) : 먼저 들어온게 먼저 나감.

• 스택 - 배열로 구현하는게 효율적
• 큐 - 링크드리스트로 구현하는게 효율적

메서드

스택(Stack) - 클래스

empty() //Stack이 비어있는지 알려줌
peek() //Stack의 맨 위에 저장된 객체를 읽기.
pop() //Stack의 맨 위에 저장된 객체를 꺼낸다.
push(Object item) //Stack에 객체를 저장
search(Object o) //찾기. 배열과 달리 위치는 1부터 시작

큐(Queue) - 인터페이스

ex) Queue q = new LinkedList();

offer(Object o) //Queue에 객체를 저장
poll() //Queeu에서 객체 삭제
peek() //읽기

ch11-19 스택과 큐의 활용

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

ch11-22 Iterator, ListIterator, Enumeration

• 컬렉션에 저장된 데이터를 접근하는데 사용되는 인터페이스
  Iterator 메서드

hasNext() //읽을게 있는지 확인
next() //읽기

• Enumeration은 Iterator의 구버전
• ListIterator은 Iterator의 접근성을 향상(단방향->양방향)
  (previous(), next())
• 컬렉션에 저장된 요소들을 읽어오는 방법을 표준화한 것

ch11-24 Map과 Iterator

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

ch11-25 Arrays - 배열을 다루기 편리한 메서드(static) 제공

1. 배열의 출력 - toString()
2. 배열의 복사 - copyOf(), copyOfRange()
   //새로운 배열을 생성 후 반환
3. 배열 채우기 - fill(), setAll()
4. 배열의 정렬과 검색 - sort(), binarySearch()
   //이진탐색은 정렬된 배열에만 가능
5. 다차원 배열의 출력 - deepToString()
6. 다차원 배열의 비교 - deepEquals()
7. 배열을 List로 변환 - asList(Object... a)
   //List는 읽기전용.
8. 람다와 스트림 관련 - parallelXXX(), spliterator(), stream()

ch11-30 Comparator와 Comparable

• 객체 정렬에 필요한 메서드(정렬기준 제공)를 정의한 인터페이스
  Comparable : 기본 정렬기준을 구현하는데 사용
  Comparator : 기본 정렬기준 외에 다른 기준으로 정렬하고자할 때 사용

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

ch11-32 Integer와 Comparable

ch11-34 HashSet - 순서X, 중복X

HashSet

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

TreeSet

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

HashSet - 주요 메서드

(생성자)
HashSet()
HashSet(Collection c)
HashSet(초기용량)
HashSet(초기용량, float loadFactor)

(추가, 삭제)
add(Object o)
addAll(Collection c) //합집합
remove(Object o) //삭제
removeAll(Collection c) //교집합
retainAll(Collection c) //차집합
clear() //모두삭제

isEmpty()
size()
toArray()
toArray(Object[] a)

contains(Object o)
containsAll(Collection c)
iterator()

ch11-37 HashSet

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

ch11-39 TreeSet - 범위 탐색, 정렬

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

ch11-40 이진 탐색 트리(binary search tree)

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

ch11-41 TreeSet - 데이터 저장과정 boolean add(Object o)

• HashSet은 equals(), hashCode()로 비교
  TreeSet은 compare()를 호출해서 비교

ch11-42 TreeSet - 생성자, 메서드

(생성자)
TreeSet() //comparable <-- 기본 비교
TreeSet(Collection c)
TreeSet(Comparator comp) //비교 기준 제공

(메서드)
first() //제일 작은 것
last() //제일 큰 것
ceiling(Object o) //올림
floor(Object o) //버림
highter(Object o) //지정된 객체보다 큰 값
lower(Object o) ///지정된 객체보다 작은 값
subSet(from, to) 
headSet(Object toElement) //더 작은 값들을 모두 반환
tailSet(Object fromElement) //더 큰 값들을 모두 반환

트리 순회(tree traversal)

• 이진 트리의 모든 노드를 한번식 읽는 것

1. 전위순회
2. 후위순회
3. 중위순회 //오름차순으로 정렬
4. 레벨순회

ch11-46 HashMap, Hashtable - 순서X,중복(키X,값O)

• Map인터페이스를 구현. 데이터를 키와 값의 쌍우로 저장
• HashMap(동기화X)은 Hashtable(동기화O)의 신버전

HashMap

• Map인터페이스를 구현한 대표적인 컬렉션 클래스
• 순서를 유지하려면, LinkedHashMap클래스를 사용하면 됨

TreeMap

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

ch11-47 HashMap의 키(key)와 값(value)

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

  키(key) 중복허용X
  값(value) 중복허용O

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

해싱(hashing)

ex) 환자정보관리 - 출생연도별로 정리

• 해시함수를 이용해서 해시테이블에 데이터를 저장 & 검색

• 해시테이블은 배열과 링크드 리스트가 조합된 형태

해시테이블에 저장된 데이터를 가져오는 과정

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

ch11-48 HashMap - 주요 메서드

메서드

(생성자)
HashMap()
HashMap(배열 용량)
HashMap(배열 용량, float loadFactor)
HashMap(Map m)

(읽기)
entrySet()
//(키,값)쌍(set)으로 반환
keySet()
//키 반환
values()
//값 반환

(검색)
containsKey(Object key)
containsValue(Object value)
//각각 키와 값이 있는지 확인
get(Object key)
//지정한 키에 대응하는 value를 찾아서 반환
getOrDefault(Object key, ObjectdefaultValue)
//value를 못찾으면 defaultValue를 반환

(추가)
put(Object key, Object value)
putAll(Map m)

(삭제)
remove(Object key)

(변경)
replace(Object key, Object value)

(그 외)
size()
isEmpty()
claer()
clone()

ch11-52~54 Collections

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

1. 컬렉션 채우기, 복사, 정렬, 검색
   : fill(), copy(), sort(), binarySearch()

2. 컬렉션의 동기화 - synchronizedXXX()

3. 변경불가(readOnly) 컬렉션 만들기 - unmodifiableXXX()

4. 싱글톤 컬렉션 만들기 - singletonXXX()
   : 객체 1개만 저장

5. 한 종류의 객체만 저장하는 컬렉션 만들기 - checkedXXX()