[Java] Java Collection Framework, JCF

JAVA의 컬렉션 프레임 워크란 ? 

다수의 데이터를 쉽고 효과적으로 처리 가능한 표준화된 방법을 제공하는 클래스의 집합.

데이터를 저장하는 자료 구조와 데이터를 처리하는 알고리즘을 구조화하여 클래스로 구현해 놓은 것을 말한다.

이러한 Collection Framework는 자바의 인터페이스를 사용해 구현된다. 

JDK 1.2 부터 도입되었고 다양한 자료구조와 알고리즘을 효율적으로 사용할 수 있도록 설계되었다. 

Collection Framework의 주요 인터페이스 

자료구조에 따라 List, Set, Map 인터페이스가 있다. 

Map은 Collection과 데이터 저장 방식이 다르므로 다르게 구분된다. Collection은 단순히 값을 저장하지만 Map은 Key와 Value 값을 같이 저장한다는 것으로 구분된다. 

Collection Framework

컬렉션 클래스 

Collection Framework에 속하는 인터페이스를 구현한 클래스.

 

컬렉션 인터페이스 

List, Set 인터페이스의 많은 공통된 부분을 Collection 인터페이스에서 정의하고 두 인터페이스는 그것을 상속 받는다. 

컬렉션 인터페이스는 컬렉션을 다루는데 가장 기본적인 동작을 정의하고 메서드로 제공한다. 

 

Stack 자료구조에서 사용
LIFO (Last In First Out) & FILO (First In Last Out)
후입 선출 방식
마지막에 들어간 데이터가 가장 먼저 나오는 구조

이진 검색 트리
각 노드가 최대 2개의 자식 노드 가짐
왼쪽 자식(L) < 부모 노드(P) < 오른쪽 자식(R) 규칙을 따름
중위 순회(Inorder Traversal)하면 항상 오름차순 정렬된 데이터 출력 가능

Iterable 

최상위 인터페이스.

Iterable<T> 컬렉션을 반복할 수 있는 최상위 인터페이스.

Collection, List, Set, Queue 등 모든 컬렉션이 Iterable을 구현한다. 

Collection

데이터의 집합.

Collection<T> 인터페이스는 List, Set, Queue의 부모 인터페이스이다.

컬렉션에 대한 메소드(add, remove, contain...등) 제공

List 

순서를 유지하고 중복이 가능한 자료구조.

배열과 비슷한 형태로 데이터를 저장한다.

List 구현체 : ArrayList, LinkedList, Vector, Stack 등 

ArrayList

내부적으로 동적 배열

검색 속도 : O(1) → 검색 속도가 빠르다. :: 인덱스를 이용해 빠르게 배열 요소에 접근 

삽입/삭제 : O(n) → 삽입 / 삭제가 느리다. 

LinkedList

내부적으로 이중 연결 리스트 사용.

검색 속도 : O(n) → 검색이 느리다.

삽입/삭제 : O(1) → 삽입 / 삭제가 빠르다. 

 

단일 연결 리스트

요소의 저장과 삭제 작업이 다음 요소를 가리키는 참조만 변경

장점 : 아주 빠르게 처리 가능

당점 : 현재 요소에서 이전 요소로 접근이 어렵

단일 연결 리스트 (출처 : TCPSchool)

 

이중 연결 리스트 

단일 연결 리스트가 이전 요소로 접근하기 어려운 점과 달리, 이전 요소의 참조도 가진다.

이중 연결 리스트 (출처 : TCPSchool)

 

Vector

ArrayList와 유사하지만, 동기화를 지원한다. (성능 저하)

List의 인터페이스 상속 

Stack

후입선출(LIFO) 구조.

List 컬렉션 클래스의 Vector 클래스를 상속 받아, Stack 메모리 구조 클래스 제공

선형 메모리 공간에 데이터를 저장하면서 후입선출의 시멘틱을 따르는 자료 구조.

메소드	설명
boolean empty()	해당 스택이 비어 있으면 true를, 비어 있지 않으면 false를 반환함.
E peek()	해당 스택의 제일 상단에 있는(제일 마지막으로 저장된) 요소를 반환함.
E pop()	해당 스택의 제일 상단에 있는(제일 마지막으로 저장된) 요소를 반환하고, 해당 요소를 스택에서 제거함.
E push(E item)	해당 스택의 제일 상단에 전달된 요소를 삽입함.
int search(Object o)	해당 스택에서 전달된 객체가 존재하는 위치의 인덱스를 반환함. 이때 인덱스는 제일 상단에 있는(제일 마지막으로 저장된) 요소의 위치부터 0이 아닌 1부터 시작함.

Queue

큐 메모리 구조는 별도 인터페이스 제공

Deque 인터페이스를 구현한 LinkedList 클래스가 큐 메모리 구조를 구현하는데 가장 많이 사용된다. 

선형 메모리 공간에 데이터를 저장하면서 선입선출(FIFO) 시멘틱을 따르는 자료구조이다.  

Deque

양방향 큐로 양쪽에서 삽입/삭제 가능 

메소드	설명
boolean add(E e)	해당 큐의 맨 뒤에 전달된 요소를 삽입함. 만약 삽입에 성공하면 true를 반환하고,  큐에 여유 공간이 없어 삽입에 실패하면 IllegalStateException을 발생시킴.
E element()	해당 큐의 맨 앞에 있는(제일 먼저 저장된) 요소를 반환함.
boolean offer(E e)	해당 큐의 맨 뒤에 전달된 요소를 삽입함.
E peek()	해당 큐의 맨 앞에 있는(제일 먼저 저장된) 요소를 반환함. 만약 큐가 비어있으면 null을 반환함.
E poll()	해당 큐의 맨 앞에 있는(제일 먼저 저장된) 요소를 반환하고, 해당 요소를 큐에서 제거함. 만약 큐가 비어있으면 null을 반환함.
E remove()	해당 큐의 맨 앞에 있는(제일 먼저 저장된) 요소를 제거함.

Set 

Set은 ① 요소의 저장 순서를 유지하지 않고 ② 같은 요소의 중복 저장을 허용하지 않는다. 

해시 알고리즘(hash algorithm)
해시 함수를 사용해 데이터를 해시 테이블에 저장하고 그것을 검색하는 알고리즘.
배열과 연결 리스트로 구현된다.
저장할 데이터 키 값을 해시 함수에 넣어 반환되는 값으로 배열의 인덱스를 구해 인덱스에 저장된 연결 리스트에 데이터를 저장하게 된다. 

HashSet

Set 컬렉션 클래스에서 가장 많이 사용되는 클래스 중 하나.

해시 알고리즘을 사용하여 검색 속도가 매우 빠르다. 

내부적으로 HashMap 인스턴스를 이용하여 요소를 저장.

요소를 순서에 상관없이 저장하고 중복된 값은 저장하지 않는다. 

TreeSet

데이터가 정렬된 상태로 저장되는 이진 검색 트리(binary search tree)의 형태로 요소를 저장.

이진 검색 트리는 데이터를 추가하거나 제거하는 등의 기본 동작 시간이 매우 빠름.

NavigableSet 인터페이스를 기존의 이진 검색 트리의 성능을 향상시킨 레드-블랙 트리(Red-Black tree)로 구현.

요소를 순서에 상관없이 저장하고 중복된 값은 저장하지 않는다. 

 

Map 

키(Key)-값(Value) 쌍으로 데이터 저장, 키는 중복 불가.

Collection 인터페이스와는 다른 저장 방식. 

요소의 저장 순서를 유지하지 않는다. 

Key 중복 X, Value 중복 허용

HashMap

Map 컬렉션 클래스에서 가장 많이 사용되는 클래스 중 하나.

중복된 키로는 값 저장 불가

같은 값을 다른 키로 저장하는 것은 가능

 Hashtable

Hashtable 클래스는 HashMap 클래스와 마찬가지로 Map 인터페이스를 상속

HashMap 클래스에서 사용할 수 있는 메소드와 거의 같다.

기존 코드의 호환성만을 위해 남아있어, Hashtable 클래스보다는 HashMap 클래스를 사용하는 것을 권장.

TreeMap

키와 값을 한 쌍으로 하는 데이터를 이진 검색 트리(binary search tree)의 형태로 저장

NavigableMap 인터페이스를 기존의 이진 검색 트리의 성능을 향상시킨 레드-블랙 트리(Red-Black tree)로 구현

Collection의 주요 메서드 

메서드	설명
boolean add(E e)	해당 컬렉션(collection)에 전달된 요소를 추가함. (선택적 기능)
void clear()	해당 컬렉션의 모든 요소를 제거함. (선택적 기능)
boolean contains(Object o)	해당 컬렉션이 전달된 객체를 포함하고 있는지를 확인함.
boolean equals(Object o)	해당 컬렉션과 전달된 객체가 같은지를 확인함.
boolean isEmpty()	해당 컬렉션이 비어있는지를 확인함.
Iterator<E> iterator()	해당 컬렉션의 반복자(iterator)를 반환함.
boolean remove(Object o)	해당 컬렉션에서 전달된 객체를 제거함. (선택적 기능)
int size()	해당 컬렉션의 요소의 총 개수를 반환함.
Object[] toArray()	해당 컬렉션의 모든 요소를 Object 타입의 배열로 반환함.