[자바의 정석] 컬레션 프레임웍(collections framework)

※ Collections는 유틸 클래스(Math클래스처럼 메서드 제공하는 클래스)

 

[컬렉션 collection]

- 컬렉션(collection) : 여러 객체(데이터)를 모아 놓은 것 (인터페이스)

- 프레임웍(framework) : 표준화, 정형화된 체계적인 프로그래밍방식, 생산성을 올려 줌

등장 배경을 이해하면 프레임웍을 사용하는 이유를 저절로 알게 됨

ex) collection framework, django framework, spring framework

- 라이브러리 : 정보, 책, 오디오 라이브러리 등 → 기능만 제공

- 컬렉션 프레임웍 : 컬렉션(다수의 객체)을 다루기 위한 표준화된 프로그래밍 방식,

                           java.util패키지에 포함,  jdk1.2부터 제공

 

[collection 인터페이스]

- List : 순서 O, 중복 O ex) 대기자 명단

 * 구현 클래스 : ArrayList, LinkedList, Stack, Vector

 

 - Set : 순서x, 중복x ex) 양의 정수 집합, 소수의집합

 * 구현클래스 : HashSet, TreeSet

 

 - Map : key, value한 쌍 구조, 순서x, 중복(키x, 값o) ex) 우편번호, 지역번호(전화번호)

* 구현클래스 : HashMap, TreeMap, HashTable(legacy), Properties(legacy)

 

[ArrayList]-순서O,중복O

배열기반(연속적)

-ArrayList는 기존의 Vector를 개선한 것으로 구현원리와 기능적으로 동일

 ArrayList와 달리 Vector는 자체적으로 동기화처리가 되어 있다.

-List인터페이스를 구현하므로, 저장순서가 유지되고 중복을 허용한다.

-데이터의 저장공간으로 배열을 사용한다.(배열기반)

 

[ArrayList의 생성자]

[배열의 장단점]

*장점

배열은 구조가 간단하고 데이터를 읽는데 걸리는 시간(접근시간, access time)이 짧다.

*단점1 : 크기를 변경할 수 없다.

-변경을 원하면 더 큰 배열 생성-> 기존 내용 복사 → 참조변경을 해야함.

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

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

-데이터를 추가하거나 삭제하기 위해, 다른 데이터를 옮겨야 함.

-그러나 순차적인 데이터의 추가(끝에 추가),삭제(끝부터 삭제)는 속도 빠름

 

[LinkedList] -순서O,중복O 노드(Node)

-연결기반(불연속적)

-LinkedList는 배열의 단점을 보완했다. LinkedList-기차, 배열-상자

-배열과 달리 링크드 리스트는 불연속적으로 존재하는 데이터를 연결(link)

-데이터의 삭제 : 단 한번의 참조변경만으로 가능

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

→ 링크드 리스트(연결리스트)는 데이터 접근성이 나쁨

class Node {

      Node next;

      Object obj;

}

→ 더블리 링크드 리스트(이중 연결리스트) : 접근성 향상(Java)

class Node {

      Node next;

      Node previous;

      Object obj;

}

→ 더블리 써큘러 링크드 리스트(이중 원형 연결리스트)

 

[Stack]

LIFO(Last In First Out)

저장/추가 : push( ), 추출/삭제 : pop( ), 스택의 맨 위에 저장된 객체 반환 : peek( )

순차적 추가/삭제가 가능한 배열을 사용해서 구현

 

[Queue]

FIFO(First In First Out)

저장/추가 : offer( ), 추출/삭제 : poll( ), 삭제 없이 요소를 읽어 옴 : peek( )

배열보다 LinkedList가 더 적합

→ LinkedList는 저장/추출 시에 자리이동을 하지 않아도 되니까

Queue는 interface -> 객체 생성 불가, Queue를 구현한 클래스 사용하기(자바API검색)

 

[Stack & Queue의 활용]

스택의 활용 예 – 수식계산, 수식 괄호검사, 워드프로세서의 undo/redo

                        웹 브라우저의 뒤로/앞으로

큐의 활용 예 – 최근 사용문서, 인쇄작업 대기목록, 버퍼(buffer)

 

[Iteraator, ListIterator,  Enumeration]

-컬렉션에 저장된 데이터를 접근하는데 사용되는 인터페이스

* Iteraator인터페이스를 주로 사용함, Enumeration은 Iteraator와 동일하며 옛날버전

 

[Iteraator인터페이스의 메서드]

-boolean hasNext( )는 읽어 올 요소가 남아있는지 확인함

-Object next( )는 다음 요소를 읽어 옴

 

[Iteraator]

-컬렉션에 저장된 요소들을 읽어오는 방법을 표준화한 것

-컬렉션에서 iterator( )를 호출해서 Iterator를 구현한 객체를 얻어서 사용

- iterator( )는 1회용이라 다 쓰고 나면 다시 얻어와야 한다.

Iterator it = set.iterator( );

while(it.hasNext( )) {

           System.out.println(it.next( ));

}

 

[Map과 Iteraator]

-Map에는 Iteraator( )가 없다.

=> keySey( ), entrySet( ), values( )를 호출해야 사용가능

 

[Arrays]

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

1. 배열의 출력 – toString( )

2. 배열의 복사 – copyOf( ), copyOfRange( )

3. 배열 채우기 – fill( ), setAll( )<-람다식

4. 배열의 정렬과 검색 – sort( ), binarySearch( )

5. 다차원 배열의 출력 – deepToString( )

6. 다차원 배열의 비교 - deepEquals( )

7. 배열을 List로 변환 – asList( )

8. 람다와 스트림(14장)관련 – parallelXXX( ), spliterator( ), stream( )

 

[Comparator와 Comparable] sort( )

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

Comparator : 기본 정렬기준을 구현하는데 사용

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

-compare( )와  compareTo( )는 두 객체의 비교결과를 반환하도록 작성

                 → 같으면0, 오른쪽이 크면 음수(-), 작으면 양수(+)

 

[HashSet]-순서X,중복X, 정렬필요

-set인터페이스를 구현한 대표적인 컬렉션 클래스

-순서를 유지하려면 LinkedHashSet클래스를 사용하면 된다.

*HashSet데이터 저장과정

-HashSet은 객체를 저장하기 전에 기존에 같은 객체가 있는지 확인 후,

 같은 객체가 없으면 저장하고, 있으면 저장하지 않는다. (set은 중복을 허용하지 않으니까)

-boolean add(Object o)메서드는 저장할 객체의 equals( )와 hashcode( )로 비교

→ add메서드 실행 시 equals( )와 hashCode( )가 오버라이딩 되어 있지 않으면 위의 작업이 제대로 작동하지 않는다.

 

[TreeSet]

장점 : 범위 탐색(검색)유리함, 정렬필요X -> 정렬에 유리함

단점 : 트리가 커질수록 추가, 삭제 시간이 늘어남.

-이진 탐색 트리(binary search tree)로 구현. 범위 탐색과 정렬에 유리

-이진 트리는 모든 노드가 최대2개의 하위 노드를 가짐.

-각 요소(node)가 나무(tree)형태로 연결(LinkedList의 변형)

class TreeNode {

           TreeNode left;   //왼쪽 자식노드

           Object element; //저장할 객체

           TreeNode right; //오른쪽 자식노드

}

*이진 탐색 트리(binary search tree)

-부모보다 작은 값은 왼쪽, 큰 값은 오른쪽에 저장

-데이터가 많아질수록 추가, 삭제에 시간이 더 걸림(비교 횟수 증가)

(HashSet보다 시간이 더 걸림)

 

*TreeSet데이터 저장과정

boolean add(Object o)메서드는 저장할 객체의 compare( )를 호출해서 비교

(루트부터 트리를 따라 내려가며 값을 비교. 작으면 왼쪽, 크면 오른쪽에 저장)

 

*Tree set 범위검색 메서드

subset(Object fromElement, Object toElement); 범위 검색 from~to사이의 결과를 반환. to값은 범위에 포함되지 않음

headset(Object toElement); 지정된 객체보다 작은 값을 객체들을 반환

tailSet(Object formElement); 지정된 객체보다 큰 값의 객체들을 반환

 

*트리 순회(tree travelsal)

-이진 트리의 모든 노드를 한번씩 읽는 것을 트리 순회라고 한다.

-전위, 중위, 후위 순회법이 있으며, 중위 순회하면 오름차순으로 정렬된다.

 

[HashMap]-키,값(한 쌍)구조, 키 중복X, 순서X