Ch11. 컬렉션 프레임워크 (1)

< 컬렉션 프레임워크란? >

* 컬렉션 프레임 워크

- 프로그램 구현에 필요한 자료구조와 알고리즘을 구현해놓은 라이브러리

- java.util 패키지에 구현되어 있음

- 이를 사용하여 개발에 소요되는 시간을 절약하고 최적화된 라이브러리 사용 가능

- Collection인터페이스와 Map인터페이스로 구성됨

 

* Collection 인터페이스

- 하나의 객체에 대한 자료구조 cf. map : key-value pair(쌍)로 이루어져 있는 객체를 관리

- 하위에 List, Set 인터페이스가있다

 

 

* Map 인터페이스

- 쌍(pair)으로 이루어진 객체를 관리하는 데 필요한 여러 메서드가 선언되어 있음

- key-value 쌍으로 이루어져 있으며, key는 중복될 수 없음

---

* 배열(Array) vs. Linked List

- 배열

: 연속된 선형 자료구조

: 논리적 구조 = 물리적 구조

: 물리적으로 따닥따닥 붙어있기 때문에, i번째에 있는 값을 찾을 때 빠르다

: 중간에 값을 지우면 뒤에서 값을 한칸씩 앞으로 땡겨야하기 때문에 시간이 걸린다

: Fixed Length를 가지므로 정해진 길이를 초과해 값을 추가하려면 Length를 뻥튀기한 배열을 만든 후 Copy해야 함

: JDK에는 ArrayList나 Vector가 있다

 

- Linked List

: 논리적으로는 선형이지만, 물리적으로는 메모리가 동떨어져 있다

: 동적메모리가 허용하는 한 계속 이어서 쓸 수 있다

: 중간에 값을 지우게 되면 메모리는 지우고 링크만 조정해주면 되기 때문에 시간이 오래 걸리지 않는다

--> 자료변동이 자주 일어날 때 쓰면 좋다

: JDK에는 LinkedList가 있다

 

* Stack vs. Queue

- Stack

: LIFO(Last In First Out)

: 아래에서 점차 차곡차곡 쌓아가는 구조로 제일 위를 top이라고 함

: 자료를 넣는 것을 push(), 빼는 것을 pop()

 

- Queue

: FIFO(First In First Out)

: 자료를 빼는 쪽이 Front, 자료를 넣는 쪽이 Rear

: 자료를 넣는 것을 enqueue(), 자료를 빼는 것을 dequeue()

 

* Hash

- 검색을 위한 자료구조로 검색속도가 빠르다

- index(위치) = hash(key), 이 때 key는 중복 X

- 꽉차게 쓰지 않고 75%정도 차면 뻥튀기를 한다

- hashtable, hashmap 등이 있다

 

* Binary Tree

- Child가 2개 이하

- ex) Binary Search Tree

--> 데이터 중복은 X

--> 분기점에서 비교를 해서 자기자신보다 작은 값은 왼쪽에, 큰 값은 오른쪽에....