컬렉션 프레임워크란?
: List, Set, Map으로 구성된 컬렉션들을 사용하기 위해 표준화된 설계
- java.util 패키지에 포함되어있다.
- jdk 1.2부터 제공되었다. 이전 버전의 도구들이 하위호환성을 위해 여전히 남아있다. 따라서, 지금부터 작성하는 곳에는 이 프레임워크를 사용하는 것이 좋다.
- 이전 버전과는 주로 동기화, 설계 측면에서 차이가 있다.
- 동시성: concurrency를 얻기 위해 많은 콜렉션 프레임워크는 동기화가 안되어있어서 성능이 더 좋을 수 있다. 그러나, 개발자는 임계영역에 대한 동기화를 고려하며 로직을 작성해야한다.
- stream과 같은 함수형 패러다임을 위주로 작성하게 되면 side effect를 줄일 수 있어 동시성에 대한 연계가 좋아보인다.
java collection의 핵심 인터페이스
- List(리스트)
- 중복 허용O, 저장순서 유지O
- ArrayList, LinkedList, Stack, Vector, Queue
- Set(집합)
- 중복 허용X, 저장순서 유지X
- HashSet, TreeSet
- Map(K-V)
- Key 중복 허용X, Value 중복 허용O, 저장순서 유지X
- HashMap, TreeMap, Hashtable, Properties
- List, Set과 저장방식이 다르다. List, Set은 Collection 공통조상을 갖는다.
ArrayList
: Vector 클래스의 신버전인 배열. 기능적인 측면에서는 유사하고 vector와 다르게 동기화가 안되어있다.
- 배열 크기는 변경 불가능하다. 크기를 변경하려면 새로 만들어서 할당하는 방식을 사용해서 필연적으로 용량 변경에는 오버헤드가 있다.
- 메모리상 연속적으로 데이터가 저장되어있다. 단순하게
인덱스가 n인 데이터의 주소 = 배열의 주소 + 데이터의 크기 * n로 인덱스 n의 원소값을 읽을 수 있다.
배열의 크기 변경
trimToSize()를 호출하면 size 만큼의 capacity로 새로운 배열을 생성해, 주소값을 변수에 할당한다. 기존 배열은 나중에 gc에 의해 제거된다.- 벡터의 경우
setSize를 호출했을 때 capacity보다 작다면 size를 늘리고 null로 채워주지만, capacity보다 크다면 위의 방법과 같이 새로운 배열을 만든다.
일반적으로 ArrayList를 List타입으로 선언하는 이유
ArrayList() 를 LinkedList()로 변경하게 되어도, 참조변수의 타입이 List이므로 List에 정의되지 않은 멤버는 사용하지 않았을 것이 보장된다. 만약 ArrayList를 참조변수로 선언했다면 ArrayList에만 정의되어있는 멤버를 호출했을 수 있기 때문에 선언문 이후의 모든 문장들을 검토해야한다.
LinkedList
: ArrayList는 크기 변경이 불가능하고, 데이터 추가 삭제에 많은 시간이 걸린다. LinkedList는 배열의 단점을 보완하기 위한 것이다.
- 양방향 linked list도 있다. 코틀린에서는 default가 양방향이다.
- 메모리상 불연속적으로 데이터가 저장되어있다. 따라서, 조회 시 n번째 데이터까지 차례대로 따라가야 원하는 값을 얻을 수 있다. 기본적으로 조회, 삭제, 생성 모두
O(N)의 비용이 발생한다고 보면 된다. - 바로 위의 특징 때문에 새로운 배열을 생성하지 않는다는 전제하에, 맨 앞, 맨 뒤 원소를 추가 / 삭제하면 그냥 인덱스로 접근하는 ArrayList가 더 빠를 수 있다. 중간값의 경우는 LinkedList가 훨씬 빠르다.
Stack, Queue
Stack: 리스트의 맨 뒤 원소를 제거하는 스택은 ArrayList가 더 빠르기도 하고 적합하다. Class로 구현되어있어, 생성자가 있다.
- 컬렉션 프레임워크 이전부터 존재하던 것이기 때문에 ArrayList가 아닌 Vector를 상속받아 구현되어있다.
Queue: 첫번째 원소를 삭제해야하는 큐는 LinkedList가 적합하다. Interface로 구현되어있고 따로 생성자가 없으며
LinkedList()를 통해 생성해야한다.- https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Queue.html 의 All Known Implementing Classes에서 여러가지 구현체를 볼 수 있다.
- 다형성: 실제 수행되는 메소드는 자식 클래스
LinkedList의 메소드들이 수행된다.
1 2
Stack<Integer> myStack = new Stack<>(); Queue<Integer> myQueue = new LinkedList<>();
PriorityQueue: 힙 구조로 이루어진 우선순위 큐
Deque(Double-Ended Queue): 양쪽으로 추가 삭제가 가능하다. Queue를 상속받으며, Interface이다. 구현체로 ArrayDeque, LinkedList가 올 수 있다.
Reference)
자바의 정석 3판
https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Queue.html
https://facingissuesonit.com/2019/10/15/java-collection-framework-hierarchy/