10. <컬렉션 프레임웍 - List, Set, Map> ~자바의 정석 summary ~

1. 컬렉션 프레임웍

: 데이터 군(group)을 저장하는 클래스들을 표준화한 설계

  1) 컬렉션 - 다수의 데이터, 즉 데이터 그룹

  2)프레임웍 - 표준화된 프로그래밍 방식

 

*컬렉션 프레임웍의 핵심 인터페이스

Collection (List와 Set의 공통점 집합 인터페이스)	List	순서 o, 중복 o ex)대기자 명단
		ArrayList, LinkedList, Stack, Vector 등
	Set	순서 x, 중복 x ex)소수의 집합, 양의 정수집합
		HashSet, TreeSet 등
독립적	Map	- 키(key)와 값(value)의 쌍(pair)으로 이루어진 데이터 집합 - 순서x, 키 중복 x, 값 중복 o ex)우편번호, 지역번호, 아이디-비밀번호
		HashMap, TreeMap, Hashtable, Properties 등

- 컬렉션 프레임웍의 모든 컬렉션 클래스들은 List, Set, Map 중의 하나를 구현하고 있으며, 구현한 인터페이스의 이름이 클래스 이름에 포함되어 있어서 이름만으로도 클래스의 특징을 쉽게 알 수 있다.

 

2. ArrayList

- 컬렉션 프레임웍에서 가장 많이 사용되는 컬렉션 클래스

- Object배열을 이용해서 데이터를 순차적으로 저장한다.

  (선언된 배열의 타입이 Object이므로 모든 종류의 객체가 가능)

 

3. LinkedList

- 배열 : 모든 데이터가 연속적으로 존재

           (인덱스가 n인 데이터의 주소 = 배열의 주소+n*데이터 타입 크기)

- 링크드 리스트 : 데이터가 불연속적으로 존재하며 데이터를 서로 연결한 형태로 구성되어 있다.

- 각 요소(node)들은 자신과 연결된 다음 요소에 대한 참조(주소값)와 데이터로 구성되어 있다.

- 데이터 삭제 / 추가시 각 node가 참조하고 있는 주소값만 변경하면 된다.

  (처리속도가 빨라진다.)

 

           [ ArrayList와 LinkedList의 비교 ]

컬렉션	읽기 (접근시간)	추가/삭제	비고
ArrayList	빠르다	느리다	- 순차적인 추가삭제는 빠르다. - 비효율적인 메모리사용
LinkedList	느리다	빠르다	- 데이터가 많을 수록 접근 시간이 길어진다.

=> 다루고자 하는 데이터의 개수가 불변하다면 ArrayList를,

      변경이 잦다면 LinkedList를 선택하는 것이 좋다.

 

4. Stack(스택)/Queue(큐)

[1] Stack클래스 : 마지막에 저장한 데이터를 가장 먼저 꺼내게 되는 LIFO(Last In First Out) 구조 (한 방향 출입)

           - ArrayList에 적합, 저장(Push), 추출(Pop)

           - 활용 : 수식계산, 수식괄호검사, undo/redo, 뒤로/앞으로 등

 

[2]Queue인터페이스 : 처음에 저장한 데이터를 가장 먼저 꺼내게 되는 FIFO(First In First Out) 구조 (양방향 출입)

           - LinkedList에 적합, 저장(Offer), 추출(Poll)

           - 인터페이스이므로 이를 구현한 클래스를 선택해 객체 생성한다.

           ex. Queue q = new LinkedList();

          - 활용 : 최근사용문서, 버퍼(buffer), 인쇄작업 대기목록 등

 

5. Set인터페이스

Set	HashSet
	SortedSet	TreeSet

- Set인터페이스의 메서드들은 Collection인터페이스의 메서드와 같다.(생략)

 

           5-1. HashSet

- HashSet은 저장순서를 유지하지 않으므로 저장순서를 유지하고자 한다면 LinkedHashSet을 이용한다.

- add()메서드 사용 시 equals()와 hashCode()를 오버라이딩해야 한다.

 

          5-2.TreeSet

- 이진 검색 트리(binary search tree)라는 자료구조의 형태로 데이터를 저장하는 컬렉션 클래스

- 정렬, 검색, 범위검색(range search)에 높은 성능을 가지고 있다.

- root라고 불리는 하나의 노드에서부터 시작해서 계속 확장해 나아가는데 각 노드에 최대 2개의 노드를 연결할 수 있다.

- 위의 노드 : 부모노드, 아래 노드 : 자식노드라고 하며 부모-자식 관계라고 표현함

- 부모노드의 왼쪽 밑에는 부모노드의 값보다 작은 값의 자식노드를, 오른쪽에는 큰 값의 자식노드를 저장한다.

- 노드의 추가, 삭제에 시간이 걸린다.

- TreeSet에 저장되는 객체가 Comparable을 구현하던가, Comparator를 제공해서 두 객체를 비교할 방법을 알려줘야 한다. 그렇지 않으면 예외 발생함

- TreeSet은 저장할 때 이미 정렬하므로 따로 정렬하지 않아도 된다.

 

6. Map인터페이스

- 기존에 저장된 데이터와 중복된 키와 값의 쌍을 입력하면 기존의 값은 없어지고 마지막에 저장된 값이 남게 된다. 

   (키가 중복될 수 없으므로)

- 키(key)와 값(value)을 묶어서 하나의 데이터(entry)로 저장한다.

- 해싱을 사용해 많은 양의 데이터를 검색하는데 성능이 뛰어나다.

Map	Hashtable
	HashMap	LinkedHashMap
	SortedMap	TreeMap

6-1. HashMap

- 키와 값을 각각 Object타입으로 저장한다. (Object/Object)

- 위와 같은 이유로 어떤 타입의 객체든 저장할 수 있지만 주로 키(key)는 String을 대문자 또는 소문자로 통일해서 사용한다.