Java Collection FrameWork(JCF)
Java에서 데이터를 저장하는 자료구조들을 한 곳에 모아 편리하게 관리하고 사용하기 위해 제공하는 것. 크게 List, Set, Map으로 구분할 수 있다.
Collection은 기본 데이터형이 아닌, 참조 데이터형만 저장이 가능하다. 따라서 Collection에서의 데이터는 Object 타입의 객체로서 저장이 된다.
기본 데이터형은 Wrapper 클래스를 이용하여 Boxing 시켜주거나 (ex. Integer num = new Integer(10); 기본 데이터형인 10을 Wrapper 클래스의 Integer타입 객체로 변환) autoBoxing으로 저장 할 수 있다. 저장된 값을 얻을 때에도 객체화된 데이터를 기본 데이터형으로 바로 얻을 수 있는데, 이경우 unboxing이라 한다.
List : 인터페이스
- 동일한 데이터의 중복을 허용한다.
- 데이터 저장 순서가 유지된다.
- 힙(heap) 영역 내에서 List는 객체를 일렬로 늘어놓은 구조를 하고 있다.
- 객체를 인덱스로 관리하기 때문에 객체를 저장하면 자동으로 인덱스가 부여되고 인덱스로 객체를 검색, 삭제할 수 있다. 이 때 List Collection은 객체 자체를 저장하여 인덱스를 부여하는 것이 아닌, 해당하는 인덱스에 대한 객체의 주소값을 참조하여 저장한다.
Arraylist
Arraylist 는 List 인터페이스의 구현 클래스로, 여기서의 객체는 인덱스로 관리된다. ArrayList에 객체를 추가하면 객체가 인덱스로 관리된다.
List<T> list = new Arraylist<T>();
ArrayList<T> list= new ArrayList<T>
단점 :
- 저장소의 용량을 늘리는 과정에서 많은 시간이 소요된다.
- thread-safe 보장 안함
시간 복잡도
add : O(1)
remove: O(n)
get:O(1)
Contains:O(n)
Vector
vector는 Arraylist와 동일한 내부 구조를 가지고 있다. Vector를 생성하기 위해서는 지정할 객체 타입을 타입 파라미터로 표기하고 기본 생성자를 호출하면 된다.
List<E> list = new Vector<E>();
Vector V = new Vector()
특징 :
- ArrayList 와는 다르게, Vecotr는 thread-safe하게 구성되어 멀티 스레드가 동시에 이 메서드를 실행할 수 없고, 안전하게 객체를 추가,삭제 할 수 있다. 이에 따라 단일 쓰레드환경에서는 Arraylist가 더 빠른 속도를 보여준다.
LinkedList
LinkedList는 List 구현 클래스로 ArrayList와 사용하는 메서드는 같지만 내부 구조는 완전히 다른 모습을 보여준다. ArrayList는 내부 배열 객체를 저장하여 인덱스로 관리하지만, LinkedList는 양방향 포인터 구조로, 각각마다 인접하는 참조를 링크해서 체인처럼 관리한다.
따라서, 중간 삽입/삭제가 빈번할 수록 LinkedList를 쓰는 것이 효율적이다. 반대로 순차적인 삽입/삭제가 빈번하다면 ArrayList를 사용하는 것이 효율적이다.
LinkedList를 생성할 때, 처음에는 어떠한 링크도 만들어지지 않기 때문에 내부적으로 비어있다.
LinkedList<E> list = new LinkedList<E>();
자바에서는 주로 Queue를 구현할 때, 링크드 리스트를 자주 쓰는 모습을 보여준다.
시간복잡도
add : O(1)
remove : O(1)
get : O(n)
Contains : O(n)
thread-safe 보장 안함
Set : 인터페이스
- 데이터의 저장 순서를 유지하지 않는다
- 같은 데이터의 중복 저장을 허용하지 않는다. 따라서 null도 하나의 null만 저장할 수 있다.
- Set 컬렉션은 List 컬렉션처럼 인덱스로 객체를 검색해서 가져오는 메서드가 없다. 대신 전체 객체를 대상으로 한번씩 다 가져오는 반복자 Iterator를 제공한다.
시간복잡도
HashSet
add : O(1)
contains : O(1)
next : O(h/n) h는 테이블 용량
thread - safe 보장 안함
특징 : 객체들을 순서없이 저장하고 동일한 객체를 중복 저장 X
- 중복되지 않는 값을 등록할 때 용의
- 순서없이 저장되는 것 주의
- null 허용
LinkedHashSet
add : O(1)
contains : O(1)
next : O(1)
thread - safe 보장 안함
특징 : 속도는 hashSet에 비해 느리지만 좋은 성능을 보장한다.
- 등록한 순으로 정렬을 한다.
- null을 허용한다
TreeSet
add : O(log n)
contains : O(log n)
next : O(log n)
thread - safe 보장 안함
특징 : 객체기준으로 정렬을 한다. 느리다
- null 허용 X
Map : 인터페이스
Map Collection에는 키(key)와 값(value)으로 구성된 Entry 객체를 저장하는 구조를 가지고 있다. 여기서 키와 값은 모두 객체이다.
값은 중복 저장이 가능하지만, 키는 중복 저장이 불가능하다. Set과 마찬가지로, Map 컬렉션에는 키 값의 중복 저장이 허용되지 않는다.
HashMap
HashMap은 Map 인터페이스 구현을 위해 해시테이블을 사용한 클래스이다. 또한 중복을 허용하지 않고 순서를 보장하지 않는다.
HashTable과는 달리 HashMap은 키와 값으로 null값이 허용된다.
시간복잡도
HashMap
get : O(1)
containsKey : O(1)
next : O(h/n) h는 테이블 용량
thread - safe 보장 안함
특징 : 순서에 상관없이 저장, null 허용.
LinkedHashMap
get : O(1)
containsKey : O(1)
next : O(1)
thread - safe 보장 안함
특징 : 순서대로 저장, null 허용.
