참고 포스팅
이전 Array 포스팅에 이어서 컬렉션 프레임워크라는 데이터 구조에 대해 살펴보겠습니다.
1. 개요
자바 "컬렉션 프레임워크"란 데이터를 저장하는 자료 구조와 데이터를 처리하는 알고리즘을 구조화하여 클래스로 구현해 놓은 것입니다.
즉, 자바에서 자료 구조를 쉽게 다룰 수 있도록 지원하는 표준 라이브러리입니다.
1) 자료 구조
일련의 일정한 타입들의 데이터들의 관계를 나타낸 구성체를 의미합니다.
특히 알고리즘과 깊은 의존관계를 갖습니다. 자료구조에 대한 깊은 이해가 있어야 조금 더 효율적인 알고리즘을 선택할 수 있게 됩니다.
예를 들어, 순서가 있는 데이터들의 삽입과 삭제가 빈번하게 발생한다면 LinkedList를 구현하고, 아닌 경우, ArrayList를 구현하게 됩니다.
자료 구조의 분류
선형 자료구조
쉽게 말하면, 데이터가 일렬로 이어져 있는 형태라고 생각하면 됩니다. 일반적으로 배열이 이러한 구조를 갖습니다.
대표적인 자료구조는 리스트(List), 큐(Queue), 덱(Deque - Double Ended Queue)가 있습니다.
비선형 자료구조
선형 구조의 반대의미로, 일렬로 나열된 것이 아닌, 각 요소가 여러 개의 요소와 연결된 형태를 생각하면 됩니다.
쉽게 말해서 거미줄과 같은 형태라고 생각하면 편합니다.
대표적인 자료구조로 그래프(Graph)와 트리(Tree)가 있습니다.
집합 자료구조
데이터가 연결된 형태가 아니라, 테이블에 무작위로 넣어둔 값정도로 생각하면 됩니다.
2) Collection Framework
Java Collection Framework의 의미.
-
Collection : 동일한 형태의 데이터를 수집하여 하나의 공간에 모아놓은 것을 의미합니다.
즉, 동일 타입의 데이터를 쉽게 다루기 위해 모아놓고 가공 및 처리가 가능하도록 지원하는 자료구조를 말합니다.
-
Framework : 구조의 뼈대를 의미.
결론적으로, 동일한 타입의 데이터를 모아 쉽게 가공할 수 있도록 지원하는 자료 구조의 뼈대를 말합니다.
자바 컬렉션 프레임워크는 대표적으로 Collection 인터페이스가 있습니다. 이와 관련된 자료 구조의 인터페이스 및 구현체를 알아보고 내부 동작을간단하게 구현해보겠습니다.
💡 원시타입도 컬렉션 프레임워크에 담을 수 있을까?
불가능합니다. 컬렉션 프레임워크에 저장할 수 있는 데이터는 오직 객체(Object) 뿐입니다.
원시(primitive) 타입을 적재하기 위해서는 Wrapper 클래스로 박싱하는 절차가 추가돼야 합니다.
2. Collection Framework 종류
컬렉션 프레임워크는 크게 Collection 인터페이스와 Map 인터페이스로 나뉩니다.
List와 Set 컬렉션 프레임워크는 공통된 부분이 많기 때문에 Collection 이라는 상위 인터페이스를 상속 받도록 되어있습니다.
Map 인터페이스 컬렉션들은 두개의 데이터를 묶어 한쌍으로 다루기 때문에 Collection 인터페이스와 분리되었습니다.
💡
대부분의 컬렉션 프레임워크는 List, Set, Map 3가지 중 하나를 구현하고 있으며, 구현한 인터페이스의 이름이 클래스에 포함된다는 특징이 있습니다.(ArrayList, HashSet, HashMap 등...)
그러나 Vector, Stack, Properties 와 같은 클래스들은 컬렉션 프레임워크가 만들어지기 전에 존재했던 클래스들이기 때문에 컬렉션 프레임워크의 명명법에 따르지 않는 것입니다. 추가로 Vector 또는 Properties와 같은 기존의 클래스들은 호환을 위해 남겨진 것들이므로 가급적이면 사용하지 않는 것을 권장합니다.
Iterable 인터페이스
컬렉션 인터페이스의 최상위 인터페이스
컬렉션 프레임워크 내부에서 데이터를 순회하기 위해서 iterator()라는 메서드를 통해서 객체를 생성하게 되는데 이 이터레이터 객체를 관리하는 인터페이스 입니다.
| 메서드 | 설명 |
|---|---|
| default void forEach(Consumer < ? super T > action> | 함수형 프로그래밍 전용 루프 메서드 |
| Iterator< T > iterator() | 컬렉션에서 이터레이터를 구현 |
| default Spliterator< T > spliterator() | 파이프라이닝 관련 메서드 |
💡 Collection을 상속받아야만 iterator 사용이 가능한가?? Map은??
참고로 Map은 iterable 인터페이스를 상속 받지 않았기 때문에 iterator() 와 spliterator() 는 Map 컬렉션에 구현이 되어 있지 않습니다. 따라서 직접적으로 Map 컬렉션을 순회할 수는 없고 Stream 을 사용하거나 간접적으로 키를 Collection으로 반환하여 루프문으로 순회하는 식으로 이용합니다.
Collection 인터페이스
List, Set, Queue에 상속을 하는 실질적인 최상위 컬렉션 인터페이스입니다.
이를 통해, 다형성을 활용하여 다양한 종류의 컬렉션 자료형을 받아 자료를 삽입하거나 삭제, 탐색 기능을 사용할 수 있습니다.
| 메서드 | 설명 |
|---|---|
| boolean add(Object o) boolean addAll(Collection c) |
지정된 객체 또는 Collection 객체들을 Collection 안에 추가 |
| boolean contains(Object o) boolean containsAll(Collection c) |
지정된 객체 또는 Collection 객체들이 Collection에 포함되어 있는지 확인 |
| boolean remove(Object o) boolean removeAll(Collection c) |
지정된 객체 또는 지정된 Collection에 포함된 객체들을 삭제 |
| boolean retainAll(Collection c) | 지정된 Collection에 포함된 객체들만을 남기고 다른 객체들은 Collection에서 삭제. 사실 상 removeAll의 대칭버전(교집합 동작) 이 작업으로 Collection에 변화가 있으면 true 없으면 false를 반환 |
| void clear() | Collection 에 저장된 모든 객체를 삭제 |
| boolean equals(Object o) | 동일한 Collection인지 비교 |
| int hashCode() | Collection의 hash code를 반환 |
| boolean isEmpty() | Collection이 비어있는지 확인 |
| Iterator iterator() | Collection의 iterator를 얻어서 반환 (상위 Iterable 인터페이스를 상속) |
| int size() | Collection에 저장된 객체의 개수를 반환 |
| Object[] toArray() | Collection에 저장된 객체를 객체배열(Object[])로 반환 |
| Object[] toArray(Object[] a) | 지정된 배열에 Collection의 객체를 저장해서 반환 |
💡 참고
JDK 1.8 부터는 함수형 프로그래밍을 위해 parallelStream, removeIf, stream, forEach 디폴트 메서드가 추가되었습니다.
Collection<Number> col1 = new ArrayList<>();
col1.add(1);
Collection<Number> col2 = new HashSet<>();
col1.add(1);
Collection<Number> col3 = new LinkedList<>();
col1.add(1);List 인터페이스
List Interface는 대표적인 선형 자료구조로 주로 순서가 있는 데이터를 목록으로 이용하기 위해 만들어진 인터페이스입니다.
저장 순서가 유지되는 컬렉션을 구현할 때 사용합니다.
같은 요소의 중복 저장을 허용합니다.
배열과 마찬가지로 index로 접근이 가능합니다.
앞선 포스팅에서도 언급했지만 배열과 리스트 간의 가장 큰 차이점은 리스트는 동적으로 크기를 변경할 수 있다는 점입니다.(동적 크기 할당)
요소 사이마다 빈공간을 허용하지 않아 요소 삽입/삭제 할때마다 배열의 이동이 발생합니다.
| 메서드 | 설명 |
|---|---|
| boolean add(Object o) boolean addAll(Collection c) |
지정된 객체 또는 Collection 객체들을 Collection 안에 추가 |
| boolean contains(Object o) boolean containsAll(Collection c) |
지정된 객체 또는 Collection 객체들이 Collection에 포함되어 있는지 확인 |
| boolean remove(Object o) boolean removeAll(Collection c) |
지정된 객체 또는 지정된 Collection에 포함된 객체들을 삭제 |
| boolean retainAll(Collection c) | 지정된 Collection에 포함된 객체들만을 남기고 다른 객체들은 Collection에서 삭제. 사실 상 removeAll의 대칭버전(교집합 동작) 이 작업으로 Collection에 변화가 있으면 true 없으면 false를 반환 |
| void clear() | Collection 에 저장된 모든 객체를 삭제 |
| boolean equals(Object o) | 동일한 Collection인지 비교 |
| int hashCode() | Collection의 hash code를 반환 |
| boolean isEmpty() | Collection이 비어있는지 확인 |
| Iterator iterator() | Collection의 iterator를 얻어서 반환 (상위 Iterable 인터페이스를 상속) |
| int size() | Collection에 저장된 객체의 개수를 반환 |
| Object[] toArray() | Collection에 저장된 객체를 객체배열(Object[])로 반환 |
| void add(int index, Object element)boolean addAll(int index, Collection c) | 지정된 위치(index)에 객체(element) 또는컬렉션에 포함된 객체들을 추가한다. |
| Object remove(int index) | 지정된 위치(index)에 있는 객체를 삭제하고 삭제된 객체를 반환한다. |
| Object get(int index) | 지정된 위치(index)에 있는 객체를 반환한다. |
| Object set(int index, Object element) | 지정된 위치(index)에 객체(element)를 저장한다. |
| int indexOf(Object o) | 지정된 객체의 위치(index)를 반환한다. (순방향) |
| int lastIndexOf(Object o) | 지정된 객체의 위치(index)를 반환한다. (역방향) |
| List subList(int fromIndex, int toIndex) | 지정된 범위(from ~ to)에 있는 객체를 반환한다. |
| ListIterator listIterator()ListIterator listIterator(int index) | List의 객체에 접근할 수 있는 ListIterator를 반환한다. |
| void sort(Comparator c) | 지정된 비교자(comparator)로 List를 정렬한다. |
💡 리스트를 구현한 클래스
- ArrayList
- LinkedList
- Vector
- Stack
ArrayList 클래스
- Object[]을 사용하면서 내부 구현을 통해 동적으로 크기를 관리합니다.
- 데이터의 저장순서가 유지되고 중복을 허용합니다.
- 데이터량에 따라 capacity를 자동으로 늘였다가 줄입니다.
- 단방향 포인터 구조로 자료에 대한 순차적인 접근에 강점이 있어 조회가 빠릅니다.
- 하지만 중간 요소의 삽입/삭제의 경우, 뒤에 있는 요소들은 한 칸씩 밀려야 하거나 당겨야 하기 때문에 비효율적인 모습을 보입니다.
List<Integer> arrayList = new ArrayList<>();
arrayList.add(10);
arrayList.add(20);
arrayList.get(0); // 10
arrayList.get(1); // 20LinkedList 클래스
- 노드(데이터 + 주소)를 연결하여 리스트 처럼 만든 컬렉션(배열 X)
- 순서에 따라 노드간에 참조를 가지고 있습니다. 따라서 물리적인 메모리는 따로 생성됩니다.
- 데이터의 중간 삽입, 삭제가 빈번한 경우에 빠른 성능을 보장합니다.
- 하지만 요소 검색 시 처음 노드부터 찾으려는 노드가 나올때까지 연결된 노드를 모두 방문해야 한다는 점에서 성능이 떨어집니다.
- 자바의 LinkedList는 Doubly LinkedList(양방향 포인터 구조)로 이루어져 있습니다.
- LinkedList 는 리스트 용도 이외에도 스택, 큐, 트리 등의 자료 구조의 근간이 됩니다.
List<String> linkedList = new LinkedList<>();
linkedList.add("Hello");
linkedList.add("World");
linkedList.get(0); // "Hello"Vector 클래스
- ArrayList의 구형 버전입니다.
- ArrayList와의 차이는 모든 메서드가 동기화(synchronized) 되어있어 Thread-Safe 하다는 접입니다.
- 구버전 자바와의 호환성을 위해서 남겨두었으며 잘 사용하지 않습니다.
💡
만약 협업에서 컬렉션에 동기화가 필요한 경우, Collection 유틸 클래스인 Collections.synchronizedList() 메서드를 사용하여 ArrayList를 동기화 처리하여 사용합니다.
List<Integer> vector = new Vector<>();
vector.add(10);
vector.add(20);
vector.get(0); // 10Stack 클래스
- 후입선출(LIFO) 자료구조입니다.
- 들어올 때에는 push 나갈 때에는 pop을 사용합니다.
- Stack은 Vector를 상속하기 때문에 문제점이 많아서 잘 안쓰입니다.(대신 ArrayDeque를 사용합니다.)
Stack<Integer> stack = new Stack<>();
stack.push(30);
stack.push(50);
stack.pop(); // 50
stack.pop(); // 30Queue 인터페이스
Queue Interface는 선형 자료구조로 주로 순서가 있는 데이터를 기반으로 선입선출(FIFO) 을 위해서 만들어진 인터페이스 입니다. 일반적으로 Stack과 많이 비교되는 자료 구조입니다.
해당 구조에서 가장 앞쪽에 있는 위치를 헤드(head)라고 하며, 후위를 꼬리(tail)라고 부릅니다.
Collection 종류를 보면 알 수 있듯이 Queue를 상속하고 있는 Deque(Double Ended Queue, 덱)이라는 Interface도 있습니다. 두 인터페이스의 차이점은 Queue는 단방향으로 선입선출이 일어나지만, Deque는 양방향으로 삽입삭제가 가능한 자료구조 입니다.
💡 Queue/Deque 를 구현하는 클래스
- LinkedList
- ArrayDeque
- PriorityQueue
| 포함 | 포함 | 메서드 | 리턴타입 | 설명 |
|---|---|---|---|---|
| deque | queue | add(E e) | boolean | 요소를 꼬리에 추가, 만약 큐가 모두 찼을 경우 IllegaStateException 예외 발생 |
| deque | queue | offer(E e) | boolean | 요소를 꼬리에 추가, 예외 발생 X |
| deque | queue | peek() | E | 헤드를 삭제하지 않고 검색 후 요소 반환 |
| deque | queue | poll() | E | 헤드를 검색 및 삭제 후 요소 반환 |
| deque | addLast(E e) | void | 요소를 꼬리에 추가, 만약 큐가 모두 찼을 경우 IllegaStateException 예외 발생 | |
| deque | addFirst(E e) | void | 요소를 헤드에 추가, 만약 큐가 모두 찼을 경우 IllegaStateException 예외 발생 | |
| deque | offerLast(E e) | boolean | 요소를 꼬리에 추가 - offer(E e)와 동일 | |
| deque | offreFirst(E e) | boolean | 헤드에 요소 추가 | |
| deque | peekFirst() | E | 헤드에 있는 요소를 삭제하지 않고 반환 - peek() 와 동일 | |
| deque | peekLast() | E | 꼬리에 있는 요소를 삭제하지 않고 반환 | |
| deque | pollFirst() | E | 헤드를 검색 및 삭제하면서 요소 반환 - poll()과 동일 | |
| deque | pollLast() | E | 꼬리를 검색 및 삭제하면서 요소 반환 | |
| deque | size() | int | 요소의 갯수 반환 |
LinkedList는 List Interface도 구현하지만, Deque도 구현한 클래스 입니다.
따라서, LinkedList를 사용할 수 있는 용도로 3가지가 있습니다.
-
List
-
Deuqe
-
Queue
Deque 또는 Queue를 LinkedList처럼 Node 객체로 연결해서 관리하고 싶다면 LinkedList를 사용하면 됩니다. 일반적인 큐 자료구조를 사용하고 싶다면, LinkedList를 생성하여 Queue로 선언해주면 됩니다.
Queue<T> queue = new LinkedList<>();
그렇다면 PriorityQueue는 뭘까요?
말그대로 우선순위 큐를 의미합니다. 큐의 내부는 선입선출의 원리에 의해서 먼저 들어온순서로 나가도록 구현되어 있습니다. 하지만, 우선순위 큐에는 우선순위가 있어서 우선순위가 높은 노드가 먼저 나오도록 하는 원리입니다. 따로 정렬방식을 지정하지 는다면 낮은 숫자가 높은 우선순위(default)를 얻습니다.다만, 사용자가 정의한 객체를 타입으로 사용할 경우에 Comparator 또는 Comparable을 통해 정렬방식을 구현해줘야 합니다.
Set 인터페이스
