[Java] Collection Framework (컬렉션 프레임워크)란?

🌈 Collection Framework란

컬렉션은 여러 요소를 하나의 그룹으로 묶어 효율적으로 저장하고, 관리할 수 있는 기능을 제공하는 클래스의 집합이다. 예를 들면 배열은 크기가 고정되어 있지만, 컬렉션 프레임워크는 가변적인 크기를 갖는 특징이 있다. 또한 데이터 삽입, 탐색, 정렬 등의 API 를 제공한다. 이러한 컬렉션 프레임워크는 자바의 인터페이스(interface)를 사용하여 구현된다.

 

🌈 Collection Framework의 종류

 

🌈 Collection 인터페이스

✔ 리스트 (List)

인덱스 순서로 요소를 저장한다. 중복된 데이터를 저장할 수 있다. 아래는 List를 상속 받아 구현한 대표 클래스 및 시간 복잡도 (Time complexity)이다.

	add()	remove()	get()	contains()
ArrayList	O(1)	O(n)	O(1)	O(n)
LinkedList	O(1)	O(1)	O(n)	O(n)
Vector	O(1)	O(n)	O(1)	O(n)
Stack	O(1)	O(1)	O(n)	O(n)

 

✔ 큐 (Queue)

데이터가 저장된 순서대로 출력되는 선입선출 (FIFO: First In First Out) 의 구조를 갖는 선형 자료구조이다. 아래는 Queue를 상속 받아 구현한 대표 클래스 및 시간 복잡도 (Time complexity)이다.

	offer()	peak()	poll()	size()	Data Structure
PriorityQueue	O(log n)	O(1)	O(log n)	O(1)	Priority Heap
ArrayDequeue	O(1)	O(1)	O(1)	O(1)	Linked List

 

✔ 집합 (Set) 

순서 가 없으며, 데이터를 중복하여 저장할 수 없다. 아래는 Set를 상속 받아 구현한 대표 클래스 및 시간 복잡도 (Time complexity)이다.

	add()	contains()	next()	Data Structure
HashSet	O(1)	O(1)	O(h / n)	Hash Table
LinkedHashSet	O(1)	O(1)	O(1)	Hash Table + Linked List
TreeSet	O(log n)	O(log n)	O(log n)	Red-black tree

 

✔ Map 인터페이스

Key, value 쌍으로 데이터를 저장한다. 순서가 존재하지 않으며, Key 가 중복될 수 없다. 아래는 Map을 상속 받아 구현한 대표 클래스 및 시간 복잡도 (Time complexity)이다.

	get()	containsKey()	next()	Data Structure
HashMap	O(1)	O(1)	O(h / n)	Hash Table
TreeMap	O(log n)	O(log n)	O(log n)	Red-black tree

h : 해쉬 버킷 사이즈, n : 데이터 사이즈

 

Reference

• https://docs.oracle.com/javase/8/docs/technotes/guides/collections/index.html
• https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Collection.html