Java Collection
알고리즘 공부를 할 수록, Java Collection에 대한 공부가 부족함을 느꼈다.
실제 얼마전 면접에서도 비슷한 지적을 받았기에 반드시 숙지해야 할 내용을 정리하였다.
Collection의 특징
위 내용을 기반으로 각각 어떤 특징을 가지고 있는지, 장단점은 무엇인지. 나중에는 더 나아가 스스로 각 코드들을 구현해보도록 할것이다.
List
위를 표를 보면 알 수 있듯, List는 값을 검색함에 있어 불리함을 가진다.
ArrayList
가장 기본적인 컬렉션으로, 데이터를 추가 삭제시 안에서 배열 길이를 조절해준다.
내부적으로 Capacity가 할당되며, 크기가 가변시 저장공간을 새롭게 할당한다.
삭제의 불리함
위 그림처럼, 삭제시에 n번을 shift 해야하므로 O(n)의 복잡도를 가진다
- 추가시 n번째에 값을 추가시 O(1) ~ O(n)의 복잡도를 가진다(0에 추가시 최소 복잡도)
LinkedList
ArrayList는 배열과 같은 형태를 띄고있다면, LinkedList는 각각의 객체가 서로 사슬처럼 연결된 형태를 띄고있다.
(null) - (value)head - (value) - ... - (value) - (value)tail - (null)
접근의 불리함
접근시
LinkedList는 head부터 순차적으로 탐색을 시작한다.
n번째 값에 바로 접근 가능한ArrayList에 비해서 불리함을 가진다
추가/삭제의 용이함
반대로 배열 중간에 값을 추가하거나 삭제할때에, 단순 앞의 객체와 뒤의 객체 사이에서 연결만 해주면 되기에 매우 빠른 속도로 추가/삭제를 할 수 있다.
SET
Set의 가장 큰 특징은 중복된 값이 들어가지 않는다. 따라서 중복을 검사할때 쉽게 판단이 가능하다.
집합과 비슷한 개념으로 이해하면 쉽다.
HashSet
equals() 과 hashCode() 메소드를 기반으로 중복여부를 검사한다.
별도의 오버라이딩을 통해 이를 제어 가능하다
LinkedHashSet
HashSet과 크게 다르지 않으나, 이를 순서대로 관리한다.
TreeSet
Tree구조로 구성, 검색시 다양한 메소드를 지원한다.
E first()
E last()
E lower(E e)
E higher(E e)
E floor(E e)
E ceiling(E e)
E pollFirst()
E pollLast
Queue
FIFO 방식의 자료구조. 순서를 정하는데에 최적화 되어있음
PriorityQueue
실제로 queue가 아닌 tree 구조. 각 요소들이 우선순위를 가지고 있다. (정렬됨)
LinkedList
ArrayDequeue
DeQueueu
Double Enabled Queue
양방향으로 삽입 삭제 가능
Stack으로 사용시, Stack보다 빠르며, 대기열로 사용시 LinkedList보다 빠르다.
Stack을 사용시, Syncronized 코드때문에 단일 스레드에서 성능이 떨어지며, 초기 용량 설정이 불가능한 단점들이 존재한다.
또한 Stack은 Vector를 상속받아 기대와는 다르게 중간에서 삽입삭제가 이루어질 수 있다.
DelayQueue
public class DelayQueue<E extends Delayed> ...DelayQueue의 코드이다. 위처럼 DealyQueue는 제네릭으로 Delayed를 상속한 객체만 설정 가능하다.
이러한 객체를 만들기 위해서는 compareTo() 메소드와 getDelay() 메소드를 구현하여야 한다.
getDelay() 메소드를 통해 중간 지연이 필요한 시점, 지연이 가능해진다.
Map
Key와 Value로 이루어져있다.
HashMap
hash를 통해 데이터를 저장하므로 검색이 빠르다.
Key값은 중복 불가능하며, 순서가 존재하지 않는다
LinkedHashMap
HashMap의 특징을 그대로 가지고 있으며, 이에 추가로 순서를 가지고 있다.
WeakHashMap
Key값이 사라지면, 해당 요소는 바로 GC 대상이 되어 OOME를 줄일 수 있다.
EnumMap
Enum을 통해 메모리를 관리. Enum을 사용시 효율적인 메모리 관리를 도와주며, 시간복잡도또한 매우 훌륭하므로, Enum 사용시 고려해야 할 클래스이다.
TreeMap
Tree구조로, 이진탐색트리를 기반으로 key,value 저장
key를 기준으로 정렬되므로 빠른 검색이 가능하다.
저장시 재정렬을 하므로 성능에 부하가 생긴다.
출처
