Collection Framework
Framework : 표준화된 프로그래밍 방식
Collection : 다수의 데이터, 즉 데이터 그룹
=> 컬렉션 프레임워크는 데이터 군(群)을 다루고 표현하기 위한 단일화된 구조이다. (JAVA API Docs)
해당 게시글의 목차와 위 상속구조도의 상속관계는 같지 않을 수 있다.
위 그림을 보면 알 수 있듯 List, Queue, Set 인터페이스가 Collection 인터페이스를 상속받으며, Map은 Collection 인터페이스를 상속받지는 않으나 여러 원소를 다루는 인터페이스이므로 Collection 프레임워크에는 포함된다.
그렇다면 Collection 인터페이스가 상속받고 있는 Iterable 인터페이스는 무엇일까? 먼저 Iterable 인터페이스에는 iterator() 추상 메소드가 있다. 즉 Iterable 인터페이스를 상속받음으로써 하위 인터페이스(List, Set, Queue 등)는 iterator()메소드를 반드시 구현해야 한다. iterator() 메소드로 하여금 List, Set, Queue는 Iterator 객체를 받아올 수 있고 hasNext(), next(), remove() 등의 메소드를 사용할 수 있어 각 원소를 다루기 편리하다. 이 외에도 Iterable 인터페이스는 forEach()라는 deafult 메소드를 제공한다.
- Iterable, iterator에 대한 자세한 내용은 해당 블로그 추천
위 인터페이스와 클래스들 중에서도 많이 사용되는 List, Set, Map, Queue, Stack에 대해 알아보자.
1. List
- 순서 (O) - index 有
- 중복 (O)
List 인터페이스에서 지원하는 클래스는 ArrayList, LinkedList, Vector, Stack이 있다.
📍참고 1. array vs. List
List 인터페이스를 상속받는 각 클래스들을 살펴보기에 앞서, 다수의 데이터를 다루는 것은 List 뿐만 아니라 int[]나 char[]과 같이 선언하여 사용하는 배열로도 충분히 가능하다. 자바 컬렉션 프레임워크에서 지원하는 ArrayList나 LinkedList같은 List 클래스들은 단지 데이터들을 좀 더 다루기 쉽게 메소드들을 구현한 것이다.
배열과 리스트 사이에는 공통점과 차이점이 존재하며, 이에 따른 장단점도 존재한다.
✅ 배열과 리스트의 공통점
- 동일한 특성의 데이터들을 묶는다.
- 반복문(loop)내에 변수를 이용하여 하나의 묶음 데이터들을 모두 접근할 수 있다.
☑️ 배열과 리스트의 차이점
- 처음 선언한 배열의 크기(길이)는 변경할 수 없다. (정적 할당).
반면 리스트는 길이가 가변적이다. (동적 할당) - 배열은 메모리에 연속적으로 나열되어 할당된다.
반면 리스트는 메모리에 연속적으로 나열되지 않고 각 데이터들은 주소(reference)로 연결되어 있다. - 배열은 index에 위치한 하나의 데이터(element)를 삭제하더라도 해당 index에는 빈공간으로 계속 남는다.
리스트는 데이터 사이에 빈 공간을 허용하지 않는다.
배열의 장단점
✅ 장점
- 데이터 크기가 정해져있는 경우 메모리 관리가 편리하다
- 메모리에 연속적으로 나열되어 할당하므로 index를 통한 색인(접근)속도가 빠르다.
☑️ 단점
- 배열 크기를 변경할 수 없으므로 초기에 너무 크거나 작은 크기로 설정해줬을 경우 메모리 낭비가 심해지거나 데이터를 다 담지 못할 수 있다.
- 데이터 삽입(add), 삭제(remove) 시 빈 공간을 허용하지 않고자 한다면, 뒤의 데이터를 모두 밀어내거나 당겨줘야 하므로 속도가 느려 삽입, 삭제가 빈번한 경우에는 유용하지 않다.
리스트의 장단점
✅ 장점
- 데이터의 개수에 따라 해당 개수만큼 메모리를 동적 할당해주기 때문에 메모리 관리가 편리하다.
- 빈 공간을 허용하지 않으므로 데이터 관리도 편리하다.
- 포인터(주소)로 각 데이터들이 연결되어 있으므로 해당 데이터에 연결된 주소만 바꿔주면 되기 때문에, 삽입 삭제가 용이하다. (ArrayList 제외)
☑️ 단점
- 객체로만 데이터를 다루므로 적은 양의 데이터를 쓰는 경우 배열에 비해 차지하는 메모리가 커진다.
예를 들어 primitive type인 int는 4byte를 차지하나, Wrapper class인 Integer는 32bit JVM 기준 최소 16byte를 차지한다. 또한 주소를 연결해야하므로 16+@ byte를 차지한다.
- 기본적으로 주소를 기반으로 구성되어 있고, 메모리에 순차적으로 할당하는 것이 아니므로(물리적 주소가 순차적이지 않으므로) 색인(검색)능력은 떨어진다.
1-1. ArrayList
- Array + List의 이름에서 알 수 있듯, 내부적으로 배열(Array)을 이용해 요소를 저장한다. 따라서 index를 이용해 배열 요소에 빠르게 접근하고 조회할 수 있다.
- 크기가 고정되어 있는 배열과 달리 데이터 적재량에 따라 가변적으로 공간을 늘리거나 줄인다. 그러나 앞서 말했듯 ArrayList는 배열을 이용해 요소를 저장하고, 배열은 크기를 변경할 수 없는 인스턴스이다. 따라서 크기를 변경하기 위해서는 새로운 배열을 생성하고 기존의 배열에서 데이터를 복사하여 옮겨야 한다. 이러한 과정이 자동으로 수행되기는 하나, 요소의 삽입/삭제 작업 시 시간이 오래 걸린다.
=> 삽입/삭제보다 조회가 많이 일어나는 작업을 수행할 때 사용하기 좋다.
1-2. LinkedList
- LinkedList 클래스는 ArrayList 클래스가 배열을 이용하여 요소를 저장함으로써 발생하는 단점을 극복하기 위해 고안되었다.
=> 배열은 데이터가 연속적으로 저장되지만, LinkedList는 불연속적으로 저장된 데이터들을 서로 연결(link)하는 형태로 구성되어있다.
위 그림처럼 다음 요소를 가리키는 참조만을 갖는 연결 리스트를 단일 연결 리스트(singly linked list)라고 한다. 이러한 단일 연결리스트는 요소의 저장/삭제 작업 시 다음 요소를 가리키는 참조만 변경하면 되므로 빠르게 처리할 수 있으나, 현재 요소에서 이전 요소로 접근하기는 힘들다.
따라서 이전 요소를 가리키는 참조도 함께 가지는 이중 연결 리스트(doubly linked list)가 더 많이 사용된다.
LinkedList 클래스 또한 이 이중 연결 리스트를 내부적으로 구현한 것이다. 또한 ArrayList와 마찬가지로 List 인터페이스를 구현했기 때문에, ArrayList와 내부 구현 방법만 다를 뿐 제공하는 메소드의 종류와 기능은 거의 같다. 다만 ArrayList와 LinkedList의 성능에는 차이가 있으므로 장단점을 이해하고 필요한 상황에 적절히 선택해 사용하는 것이 좋다.
📍참고 2. ArrayList vs. LinkedList
순차적으로 추가/삭제가 일어날 때
=> ArrayList가 LinkedList보다 빠르다.중간 데이터의 추가/삭제가 일어날 때
=> LinkedList가 ArrayList보다 빠르다.
다루고자 하는 데이터의 개수가 변하지 않는 경우 : ArrayList
데이터 개수의 변경이 잦은 경우 : LinkedList
그러나 모든 상황에 위 내용이 적용되지는 않을 수도 있으므로 적절한 상황에 선택하여 사용해야 한다.
1-3. Vector
ArrayList와 같은 동작을 수행하며, 기존 코드와의 호환성을 위해 남아있다.
Vector를 쓸 일이 있다면 대신 ArrayList 클래스를 사용하는 것을 추천한다.
1-4. Stack
Vector를 상속받는 클래스이다. 후입선출 (LIFO; Last-In-First-Out) 구조로, 가장 나중에 저장(push)된 데이터가 가장 먼저 인출(pop)된다. 이러한 특성으로 인해 실생활에서는 페이지 뒤로가기, 실행 취소(undo), 수식 괄호 검사 등에서 사용된다.
다만, 경우에 따라 Stack이 필요한 상황에 대신 ArrayDeque를 사용하기도 한다. 자세한 내용은 뒤에서 Deque를 다루면서 다뤄보겠다.
2. Queue
보통 Queue와 Stack이 함께 비교되곤 하는데, Queue는 클래스인 Stack과 달리 인터페이스이다. 또한 선입선출 (FIFO; First-In-First-Out) 구조로 가장 먼저 저장된 데이터가 먼저 인출된다. (Stack 그림 참고) Queue 인터페이스를 상속받는 하위 인터페이스는 Deque, BlockingDeque, BlockingQueue, TransferQueue가 있다.
이 중에서도 Deque 인터페이스를 구현한 LinkedList 클래스가 큐를 구현할 때 많이 사용된다. Java SE 6부터 지원되는 ArrayDeque 클래스도 스택과 큐 메모리 구조를 모두 구현하는데 적합한 클래스이다.
2-1. Deque
Queue 인터페이스를 상속받는 Deque이라는 인터페이스가 있다.
Deque는 Double-Ended Queue의 줄임말로, 양 쪽에서 데이터의 삽입/삭제가 가능한 자료구조이다. 따라서 Deque는 어떤 쪽으로 입력하고 출력하냐에 따라 Stack으로 쓸 수도 있고, Queue로 쓸 수도 있다. 특히 한 쪽으로만 입력 가능하게끔 설정한 덱을 입력제한덱(scroll)이라고 하고, 한 쪽으로만 출력 가능하게끔 설정한 덱은 출력제한덱(shelf)라고 한다.
Deque 인터페이스를 구현한 클래스로는 ArrayDeque, LinkedBlockingDeque, ConcurrentLinkedDeque, LinkedList 등의 클래스가 있다. Deque은 List보다 속도가 빠르고, 쓰레드 환경에서 안전하다. pop(0)과 같은 메소드를 수행할 때 리스트는 O(N) 연산을 수행하지만 Deque는 O(1) 연산을 수행한다. 따라서 push와 pop이 빈번한 알고리즘의 경우 List보다는 Deque를 사용하는 것이 더 빠르고 효율적이다.
📍참고 3. Stack vs. ArrayDeque
Java 공식 문서에서는 Stack보다는 Deque 인터페이스와 그 구현체를 사용하라고 말한다.
A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class. For example:
Deque<Integer> stack = new ArrayDeque<Integer>(); stack.push(1);
일단 위에서 설명했듯 Deque는 Queue로 사용할 수도, Stack으로 사용할 수도 있다. 그럼 이제는 Stack을 쓰나 Deque를 쓰나 무방하지 않은가? 라는 의문이 든다.
Stack이 아닌 ArrayDeque를 써야하는 이유는 Stack이 Vector 클래스를 상속받아 구현됐기 때문이다. Vector는 List를 구현한 클래스로 자바의 레거시 코드 중 하나이며 하위 버전 호환을 위해서 남아있다. Vector는 동기화된 메소드로 구성되어 있어 멀티 쓰레드 환경에서 안전하나, 단일 쓰레드 환경에서도 동기화 처리에 대한 오버헤드가 발생하여 성능 저하가 발생할 수 있다. 따라서 단일 쓰레드 환경에서는 ArrayList를 사용하는 것이 성능 상 유리하며, Java 1.5 이후부터는 Collections.synchronizedList가 제공되므로 ArrayList를 사용하면서도 동기화 처리가 가능하다. 따라서 쓰레드 환경에 무관하게 ArrayList를 사용하는 것이 낫다.
Vector 대신 ArrayList를 사용해야 하는 이유와 Stack 대신 ArrayDeque를 사용해야 하는 이유는 거의 같다고 볼 수 있다. 단, ArrayDeque는 sunchronizedList같은 메소드를 제공하지는 않으므로 멀티 쓰레드 환경에서는 외부 동기화를 통해 안전하게 사용이 가능하다.
ArrayDeque vs. LinkedList
여담으로, ArrayDeque가 LinkedList보다도 속도와 메모리 측면에서 더 효율적이라고 한다. 그러니 큐를 구현할 때도 ArrayDeque를 사용하는 것이 더 나은 선택이 될 수 있다. 다만, ArrayDeque는 null을 요소로 추가할 수 없으나 LinkedList는 null을 추가할 수 있다.
This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue.
3. Set
- 순서 (X)
- 중복 (X)
대표적인 Set 컬렉션 클래스에 속하는 클래스는 HashSet, TreeSet이 있다.
3-1. HashSet
HashSet 클래스는 Set 컬렉션 클래스에서 가장 많이 사용되는 클래스이며, 해시 알고리즘을 사용하여 검색 속도가 매우 빠르다. HashSet 클래스는 내부적으로 HashMap 인스턴스를 이용해 요소를 저장한다.
HashSet 클래스는 Set 인터페이스를 구현하므로 요소를 순서에 상관없이 저장하고, 중복된 값은 저장하지 않는다. 만약 저장 순서를 유지해야 한다면 JDK 1.4부터 제공하는 LinkedHashSet 클래스를 사용하면 된다.
3-2. TreeSet
TreeSet 클래스는 데이터가 정렬된 상태로 저장되는 이진 검색 트리(binary search tree)의 형태로 요소를 저장한다.
이진 검색 트리는 데이터를 추가하거나 제거하는 등의 기본 동작 시간이 매우 빠르다. JDK 1.2부터 제공되는 TreeSet 클래스는 NavigableSet 인터페이스를 기존의 이진 검색 트리의 성능을 향상시킨 레드-블랙 트리(Red-Black tree)로 구현한다.
4. Map
- 순서 (X)
- 키의 중복 (X)
- 값의 중복 (O)
a67628) Map 인터페이스는 위의 List, Queue, Set 인터페이스와 다르게 Collection 인터페이스를 상속받지 않으며, 저장 방식 또한 다르다. Map 인터페이스를 구현한 Map 컬렉션 클래스들은 키와 값을 하나의 쌍으로 저장하는 Key-Value 방식을 사용한다. 키와 값으로 구성되는 데이터는 매핑(mapping) 또는 엔트리(entry)라고 불린다.
대표적인 Map컬렉션 클래스에 속하는 클래스는 HashMap, Hashtable, TreeMap이있다.
4-1. HashMap
HashMap 클래스는 Map 컬렉션 클래스에서 가장 많이 사용되는 클래스 중 하나이다. JDK 1.2부터 제공된 HashMap 클래스는 해시 알고리즘을 사용하여 검색 속도가 매우 빠르다.
keySet() 메소드를 이용하면 해당 맵에 포함된 모든 키 값을 하나의 집합(set)으로 반환해준다.
4-2. Hashtable
JDK1.0부터 사용해온 HashMap 클래스와 같은 동작을 하는 클래스이다. Hashtable 클래스에서 사용할 수 있는 메소드는 HashMap 클래스에서 사용할 수 있는 메소드와 거의 같다.
기존 코드와의 호환성을 위해서 남아있는 클래스이므로, Hashtable보다는 HashMap 클래스를 사용하는 것이 좋다.
4-3. TreeMap
TreeMap 클래스는 키와 값을 한 쌍으로 하는 데이터를 이진 검색 트리(binary search tree)의 형태로 저장하여 데이터를 추가하거나 제거하는 등의 기본 동작 시간이 매우 빠르다. JDK 1.2부터 제공된 TreeMap 클래스는 NavigableMap 인터페이스를 기존의 이진 검색 트리 성능을 향상시킨 레드-블랙 트리(Red-Black tree)로 구현한다.
Ref.
https://bangu4.tistory.com/194
https://st-lab.tistory.com/146
https://kevinntech.tistory.com/16
https://soft.plusblog.co.kr/24
https://jee-young.tistory.com/31
https://vanslog.io/posts/language/java/why-use-deque-instead-of-stack/
https://velog.io/@newdana01/Java-큐-구현시-ArrayDeque와-LinkedList-성능-차이-Deque-Queue-인터페이스
https://www.tcpschool.com/java/java_collectionFramework_concept
