Java Collection Framework

개요

프로그래밍을 학습하는데 있어서 '자료구조' 와 '알고리즘'은 필수적일 것이다. 알고리즘을 학습하기 전에 최소한의 자료구조는 학습하고 난 뒤에 하는 것이 순차적인 것처럼. (능력이 된다면 알고리즘을 공부하면서 자료구조를 깨닫는 사람도 있겠지만 난....차근차근 밑바닥을 쌓아가는 스타일)

'자료구조'는 Data Structure 라고 하는데, 직역하면 데이터 구조라는 뜻이다. 여기서 더 풀어서 설명하자면 '일련의 일정 타입들의 데이터 또는 관계를 나타낸 구성체'라고 설명할 수 있다.

자료구조와 알고리즘은 서로 뗄 수 없는 의존적인 관계이기 때문에 자료구조에 대한 이해가 있어야한다. 왜 상호의존적이냐?라고 묻는다면 어떤 알고리즘 문제를 풀기 위해 문제를 해석한 다음 보통 자료구조를 선택한다. 자료구조를 선택하면 해당 자료구조에 맞는 알고리즘을 선택하는데 보다 더 효율적인 알고리즘을 선택할 수 있다는 장점이 있다.

예로들어 순서가 있는 데이터들이 있을 때 삽입(insert/add), 삭제(remove/delete)가 빈번하게 발생한다면 LinkedList를, 아닐경우에는 ArrayList를 쓰듯이 각 자료구조별로 장단점을 갖고 있기 때문에 알고리즘 선택에 있어서 매우 중요한 역할을 담당한다.

이렇듯 자료구조는 프로그래밍의 가장 기본이기 때문에 많은 언어들에서도 표준 라이브러리로 다양한 자료구조를 지원하고 있다.

자료구조

자료구조 분류법은 많은 분류법이 있지만, 대표적으로 많이 분류되는 방법은 선형 자료구조(Linear Data Structure)과 비선형 자료구조(Nonlinear Data Structure)로 나눌 수도 있다. 이러한 분류를 보통 '형태에 따른 자료구조'라고 보고, 각 자료구조에 알맞게 구체화 된 것들을 '구현된 자료구조'이라고 한다. 물론 언어별로 관점이 조금씩 달라서 'A는 B다'라고 딱 떨어지게 정의할 수는 없으니 대략적으로만 이해하도록 하자.

먼저 선형 자료구조(Linear Data Structure)에 대해 알아보자.

선형 자료구조는 쉽게 생각해서 데이터가 일렬로 연결된 형태라고 보면 된다. 우리가 흔히 쓰는 int[] 배열 같은 것이라 생각하면 쉽다. 선형 자료구조는 대표적으로 리스트(List)와 큐(Queue), 덱(Deque)이 있다.

비선형 자료구조(Nonlinear Data Structure)는 선형 자료구조의 반대다. 일렬로 나열된 것이 아닌, 각 요소가 여러 개의 요소와 연결 된 형태를 생각하면 된다. 쉽게 생각해서 거미줄 같다고 보면된다. 대표적인 비선형 자료구조는 그래프(Graph)와 트리(Tree)가 있다.

그리고 앞으로 설명 할 자료구조 중 위 두 가지 분류에 해당되지 않는 자료구조가 있는데 집합(Set)이 있다. 보통 기타 자료구조 또는 집합 자료구조로 본다. 집합의 경우는 데이터가 연결 된 형식이 아니다.

JAVA Collection Framework

Java Collections FrameWork의 의미부터 이해 할 필요가 있다. Java는 뭐... 말 그대로 Java 언어를 의미하고, Collections 는 우리가 어떤 일정한 부류의 것을 수집하여 한 공간에 모아놓은 것을 컬렉션(Collection)이라 한다. 예로들면 동전 수집이라던가 우표 수집이 대표적인 예일 것이다. 그 의미처럼 Java에서도 비슷한 류의 데이터들을 쉽게 다루기 위해 모아놓은 것들을 가공 및 처리 할 수 있도록 지원하는 자료구조라는 뜻이다.

Framework는 무슨 뜻일까? frame 이라는 단어를 보면 딱 떠오르는 것이 틀(뼈대)이다. 건물을 공사하는 것을 길 가다가 보면 땅 위에 철근들이 여기저기 박혀있고 주변을 나무로 감싸서 전체적인 틀을 만든다. 사람으로 치자면 뼈일 것이다. 이렇듯 Framework란 어떤 문제를 해결하기 위한 구조의 뼈대가 되는 기본 구조를 의미한다.

그렇다면 위의 단어들을 종합하면, 일정 타입의 데이터들이 모여 쉽게 가공 할 수 있도록 지원하는 자료구조들의 뼈대(기본 구조)라는 의미다.

컬렉션 프레임워크는 자바 프로그래밍에서 빠질 수 없는 필수적인 요소이다. 위에서 컬렉션은 다수의 요소를 하나의 그룹으로 묶어 효율적으로 저장하고, 관리할 수 있는 기능을 제공하는 일종의 컨테이너라고 설명했다. 배열은 크기가 고정되어 있는데에 반해, 컬렉션 프레임워크는 가변적인 크기를 갖는 (Resizable) 등의 특징을 갖는다. 또한 데이터 삽입, 탐색, 정렬 등 편리한 API 를 다수 제공한다. 이런 이점으로 개발자는 배열보다는 적절한 컬렉션 클래스를 선택해 사용하는 것이 권장된다.

컬렉션 프레임워크는 JDK 1.2 버전부터 java.util 패키지에서 지원한다. JDK 1.2 이전에는 Vector, Properties, Stack, Hash Tables, Dictionary 같은 것들이 제공 되었는데, 통일성이 없었고 표준화된 인터페이스가 존재하지 않았다.

기본 구조라고 한다면 딱 떠올라야 할 것이 있다. 바로 Interface(인터페이스)다. 인터페이스 자체가 기본 뼈대(추상 구조)로 이뤄져 있기 때문이다. 이렇듯 실제로 자바에서 제공하는 Collection은 크게 3가지 인터페이스로 나뉘어있다.

크게 List(리스트), Queue(큐), Set(집합)으로 나뉘어 있다. 앞서 설명한 '형태에 따른 자료구조'라고 보면 된다. 그리고 각 분야별로 '구현' 된 것들이 있다.

말로 하면 이해하기 힘들 것이니 아래 이미지를 보자.

컬렉션 프레임워크 종류

점선은 구현 관계이고, 실선은 확장 관계다. (인터페이스끼리는 다중 상속이 가능하다) 또한 Collection을 구현한 클래스 및 인터페이스들은 모두 java.util 패키지에 있다.

그럼 위에서 설명했던 것을 적용해보자. List, Queue, Set 이 3가지의 형태에 따른 자료구조들이 있다. 그리고 Queue와 Set에는 조금 더 구체화 되어 Deque과 SortedSet이라는 형태에 따른 자료구조가 있는 것이다. 그리고 이 형태에 따른 자료구조들은 각각 '구현'이 되어 class로 제공된다. 바로 주황색 부분이 '구현된 자료구조'라고 보면 된다. 자바에서 Interface를 class파일에서 쓰면 보통 '구현한다'라고 한다. 이러한 메커니즘에 기반하여 이해하면 될 것이다.

위 그림에 대해 추가적으로 설명을 하자면 Queue 는 인터페이스는 존재하나, 직접 구현된 클래스는 존재하지 않는다. 위 계층도를 살펴보면 LinkedList 가 List 인터페이스와 Deque 인터페이스를 둘다 구현하고 있는 모습을 볼 수 있다. 따라서 Queue 를 구현하려면 LinkedList 를 사용하여 구현할 필요가 있다. (PriorityQueue 는 FIFO 가 아닌, 요소의 우선순위에 따라 출력 순서가 바뀌므로 일반적인 Queue 가 아니다)

※ 참고

참고로 Map에 대해 Collection(컬렉션)이라고 보는 분들이 있다.

이는 관점 차이이긴 한데, 일단 Java에서는 Collection 이라고 보지 않는다. 아래 링크를 보면 Collections API 에 대한 FAQ에서 왜 Map이 Collection Interface를 상속하지 않는지 설명하고 있다.

docs.oracle.com/javase/8/docs/technotes/guides/collections/designfaq.html#a14

[내용 원문]
Why doesn't Map extend Collection?
This was by design. We feel that mappings are not collections and collections are not mappings. Thus, it makes little sense for Map to extend the Collection interface (or vice versa).

즉, 매핑(mapping)이 collections 이라고 보기 힘들고, collections 또한 mapping이라고 보기 힘들다는 것이다. 그렇기 때문에 의도적으로 Collections Interface를 상속하지 않았다는 뜻이다.

그리고 Collection Interface과 Map Interface의 호환성 문제도 있다.

첫 번째로 Collection Interface를 보면 이를 상속하여 구현된 클래스들은 모두 단일 데이터를 처리하지만, Map은 키(key)와 데이터(value)가 쌍을 이루며 처리하기 때문에 굳이 Map을 위해 Collection에서 Map과 관련한 메소드를 만들고 Map에서 Collection을 상속할 필요가 없다.

두 번째로는 Iterable Interface와 Map 간의 문제도 있다. Iterable은 반복가능한 형태를 의미한다.
그런데 Map은 구조상 키(key)에 대응되는 값(value)이라는 특징을 갖고 있는데, 반복자로 뱉기 위해서는 key와 value 중 어느 것으로 반복할 것인가? 즉, Iterable Interface의 iterator() 을 구현함에도 문제가 발생할 수 밖에 없다. (그래서 내부적으로 key 와 value의 별도 인터페이스도 있다.)

마지막으로 Java에서는 상속이라는 모델링 자체가 한가지 유형의 공통성을 모델링 한다는 것에 의미가 있는데 위 1번, 2번 이유 모두 상속과는 거리가 멀다.

즉, "Java에서 Map은 Collection이다"라고 한다면 "의미적으로는 맞을 수 있으나 Java 에서는 collection이라고 보진 않는다."

위에서 설명했던 내용을 정리하고 Collection에서 List, Queue, Set, Map에 대해 간략히 알아보자.

1. 컬렉션 프레임워크의 이점

컬렉션 프레임워크는 아래와 같은 이점으로 프로그램의 유지보수를 쉽게 만들어준다.

List, Queue, Set, Map 등의 인터페이스를 제공하고, 이를 구현하는 클래스를 제공하여 일관된 API 를 사용할 수 있다.
가변적인 저장 공간을 제공한다. 고정적인 저장 공간을 제공하는 배열에 대비되는 특징이다.
자료구조, 알고리즘을 구현하기 위한 코드를 직접 작성할 필요 없이, 이미 구현된 컬렉션 클래스를 목적에 맞게 선택하여 사용하면 된다.
제공되는 API 의 코드는 검증되었으며, 고도로 최적화되어 있다.

2. 구성요소

컬렉션 프레임워크는 아래의 3가지 요소로 구성된다.

인터페이스 (Interfaces): 각 컬렉션을 나타내는 추상 데이터에 대한 인터페이스 (List, Set, Map 등). 클래스는 이 인터페이스를 구현하는 방식으로 작성되었기 때문에 상세 동작은 달라도 일관된 조작법으로 사용할 수 있다.
클래스 (Classes): 컬렉션 별 인터페이스의 구현 (Implementation). 위에서 언급했듯, 같은 List 컬렉션이더라도 목적에 따라 ArrayList, LinkedList 등으로 상세 구현이 달라질 수 있다.
알고리즘 (Algorithms): 컬렉션이 제공하는 연산, 검색, 정렬, 셔플 (Shuffle) 등에 대한 메소드.

3. Collection Framework 의 종류

컬렉션 프레임워크는 아래와 같이 크게 4개로 분류할 수 있다.

리스트 (List) : 인덱스 순서로 요소를 저장한다. 중복된 데이터를 저장할 수 있다.
큐 (Queue) : 데이터가 저장된 순서대로 출력되는 선입선출 (FIFO: First In First Out) 의 구조를 갖는 선형 자료구조이다.
집합 (Set) : 순서가 없으며, 데이터를 중복하여 저장할 수 없다. 집합 연산 (합집합, 교집합, 차집합 등) 을 지원한다.
맵 (Map) : Key-Value 쌍으로 데이터를 저장한다. 순서가 존재하지 않으며, Key 가 중복될 수 없다.

Iterable 인터페이스

컬렉션 인터페이스들의 가장 최상위 인터페이스
컬렉션들을 배우다 보면 자료들을 순회할때 Iterator 객체를 다뤄보게 될텐데, 이 Iterator 객체를 관리하는 인터페이스로 보면 된다.

여기서 Iterable이 뭐지? 라는 궁금증이 생길 수 있다. Iteration 이라는 단어가 '반복', '되풀이'를 의미한다. Iterable 이라 한다면 '반복 가능한' 이라는 정도로 이해하면 될 것이다.

그럼 왜 Collection Interface 상위에 Iterable 이 있는가?

저기서 제공하고 있는 class 들은 모두 객체형태로 내부 구현 또한 대개 Object[] 배열 형태가 아니라 각각의 객체를 갖고 움직인다. 그래서 객체의 데이터들을 모두 순회하면서 출력하려면 사용자들이 각각의 데이터 순회 방법을 알거나 하나씩 get() 같은 메소드를 통해 데이터를 하나씩 꺼내와야 한다.

하지만 Iterable 에서는 인터페이스를 보면 알겠지만 for-each 제공한다. 즉, Iterable 인터페이스를 쓰는 모든 클래스들은 기본적으로 for-each 문법을 쉽게 사용할 수 있다. 한마디로 반복자로 구현되어 나오게 하는 것이다.

메서드	설 명
default void forEach(Consumer<? super T> action)	함수형 프로그래밍 전용 루프 메서드
Iterator<T> iterator()	컬렉션에서 이터레이터를 구현
default Spliterator<T> splierator()	파이프라이닝 관련 메소드

※ 참고

참고로 Map은 iterable 인터페이스를 상속받지 않기 때문이 iterator()와 spliterator()는 Map 컬렉션에 구현이 되어 있지 않다. 따라서 직접적으로 Map 컬렉션을 순회할 수는 없고 스트림(Stream)을 사용하거나 간접적으로 키를 Collection으로 반환하여 루프문으로 순회하는 식을 이용한다.

Collection 인터페이스

List, Set, Queue에 상속을 하는 실질적인 최상위 컬렉션 타입
즉, 업캐스팅으로 다양한 종류의 컬렉션 자료형을 받아 자료를 삽입하거나 삭제, 탐색 기능을 할 수 있다. (다형성)

메서드	설 명
boolean add(Object o) boolean addAll(Collection c)	지정된 객체(o) 또는 Collection(c)의 객체들을 Collection에 추가
boolean contains(Object o) boolean containsAll(Collection c)	지정된 객체(o) 또는 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 디폴트(default) 메서드가 추가되었다.

Collection<Number> col1 = new ArrayList<>();
col1.add(1);

Collection<Number> col2 = new HashSet<>();
col1.add(1);

Collection<Number> col3 = new LinkedList<>();
col1.add(1);

※ 참고

Collection 인터페이스의 메서드를 보면 요소(객체)에 대한 추가, 삭제, 탐색은 다형성 기능으로 사용이 가능하지만, 데이터를 get 하는 메서드는 보이지 않는다. 왜냐하면 각 컬렉션 자료형 마다 구현하는 자료 구조가 제각각 이기 때문에 최상위 타입으로 조회하기 까다롭기 때문이다.

List 인터페이스

저장 순서가 유지되는 컬렉션을 구현하는 데 사용
같은 요소의 중복 저장을 허용
배열과 마찬가지로 index로 요소에 접근
리스트와 배열의 가장 큰 차이는 리스트는 자료형 크기가 고정이 아닌 데이터 양에 따라 동적으로 늘어났다 줄어들수 있다는 점이다. (가변)
요소 사이에 빈공간을 허용하지 않아 삽입/삭제 할때마다 배열 이동이 일어난다

ArrayList 클래스

배열을 이용하여 만든 리스트
데이터의 저장순서가 유지되고 중복을 허용
데이터량에 따라 공간(capacity)이 자동으로 늘어나거나 줄어들음
단방향 포인터 구조로 자료에 대한 순차적인 접근에 강점이 있어 조회가 빠르다
중간 요소에 삽입, 삭제가 일어나는 경우 그 뒤의 요소들은 한 칸씩 밀어야 하거나 당겨야 하기 때문에 삽입, 삭제에서는 비효율적이다.
단, 순차적으로 추가/삭제 하는 경우에는 가장 빠르다

List<String> arrayList = new ArrayList<>();

arrayList.add("Hello");
arrayList.add("World");

arrayList.get(0) // "Hello"

LinkedList 클래스

노드(객체)를 연결하여 리스트 처럼 만든 컬렉션 (배열이 아님)
데이터의 중간 삽입, 삭제가 빈번할 경우 빠른 성능을 보장한다. 해당 노드의 링크를 끊거나 연결만 해주면 되기 때문에
하지만 임의의 요소에 대한 접근 성능은 좋지 않다. 처음 노드부터 찾으려는 노드가 나올 때 까지 연결된 노드들을 모두 방문해야하기 때문에.
자바의 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 하다는 점이다.
Vector의 경우 항상 '동기화'를 지원한다. (쉽게 말하면 여러 쓰레드가 동시에 데이터에 접근하려하면 순차적으로 처리하도록 한다.) 그렇다보니 멀티 쓰레드에서는 안전하지만, 단일 쓰레드에서도 동기화를 하기 때문에 ArrayList에 비해 성능이 약간 느리다.
구버전 자바와 호환성을 위해 남겨두었으며 잘 쓰이진 않는다.

※ 참고

만일 현업에서 컬렉션에 동기화가 필요하면 Collections.synchronizedList() 메서드를 이용해 ArrayList를 동기화 처리하여 사용할 수도 있다.

List<Integer> vector = new Vector<>();

vector.add(10);
vector.add(20);

vector.get(0); // 10

Stack 클래스

후입선출 LIFO(Last-In-First-Out) 자료구조
마지막에 들어온 원소가 처음으로 나간다
들어올때는 push, 나갈때는 pop이라는 용어를 사용
Stack은 Vector를 상속하기 때문에 문제점이 많아 잘 안쓰인다. (대신 ArrayDeque 사용)

Stack<Integer> stack = new Stack<>();

stack.push(30);
stack.push(50);

stack.pop(); // 50
stack.pop(); // 30

Queue 인터페이스

선형 자료구조로 주로 순서가 있는 데이터를 기반으로 선입선출 FIFO(First-In-First-Out) 구조
처음 들어온 원소가 가장 먼저 나간다
자바에서는 Queue 는 인터페이스이고 필요에 따라 큐 컬렉션을 골라 사용할 수 있다.

PriorityQueue 클래스

우선 순위를 가지는 큐 (우선 순위 큐)
일반적인 큐와는 조금 다르게, 원소에 우선 순위(priority)를 부여하여 우선 순위가 높은 순으로 정렬되고 꺼낸다
수행할 작업이 여러 개 있고 시간이 제한되어 있을 때 우선순위가 높은 것부터 수행할때 쓰인다 (네트워크 제어, 작업 스케쥴링)
우선순위 큐에 저장할 객체는 필수적으로 Comparable 인터페이스를 구현해야한다. compareTo() 메서드 로직에 따라 자료 객체의 우선순위를 결정하는 식으로 동작되기 때문이다.
저장공간으로 배열을 사용하며, 각 요소를 힙(heap) 형태로 저장한다.
null 저장 불가능

※ 참고

힙(heap)은 이진 트리의 한 종류로 우선순위가 가장 높은 자료를 루트 노드로 갱신한다는 점으로, 가장 큰 값이나 가장 작은 값을 빠르게 찾을 수 있다는 특징이 있다.

// 우선순위 큐에 저장할 객체는 필수적으로 Comparable를 구현
class Student implements Comparable<Student> {
    String name; // 학생 이름
    int priority; // 우선순위 값

    public Student(String name, int priority) {
        this.name = name;
        this.priority = priority;
    }

    @Override
    public int compareTo(Student user) {
        // Student의 priority 필드값을 비교하여 우선순위를 결정하여 정렬
        if (this.priority < user.priority) {
            return -1;
        } else if (this.priority == user.priority) {
            return 0;
        } else {
            return 1;
        }
    }

    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", priority=" + priority +
                '}';
    }
}

public static void main(String[] args) {

    // 오름차순 우선순위 큐
    Queue<Student> priorityQueue = new PriorityQueue<>();

    priorityQueue.add(new Student("주몽", 5));
    priorityQueue.add(new Student("세종", 9));
    priorityQueue.add(new Student("홍길동", 1));
    priorityQueue.add(new Student("임꺽정", 2));

    // 우선순위 대로 정렬되어 있음
    System.out.println(priorityQueue);
    // [Student{name='홍길동', priority=1}, Student{name='임꺽정', priority=2}, Student{name='주몽', priority=5}, Student{name='세종', priority=9}]

    // 우선순위가 가장 높은 값을 참조
    System.out.println(priorityQueue.peek()); // Student{name='홍길동', priority=1}

    // 차례대로 꺼내기
    System.out.println(priorityQueue.poll()); // Student{name='홍길동', priority=1}
    System.out.println(priorityQueue.poll()); // Student{name='임꺽정', priority=2}
    System.out.println(priorityQueue.poll()); // Student{name='주몽', priority=5}
    System.out.println(priorityQueue.poll()); // Student{name='세종', priority=9}
}

Deque 인터페이스

Deque(Double-Ended Queue)는 양쪽으로 넣고 빼는 것이 가능한 큐를 말한다.
스택과 큐를 하나로 합쳐놓은 것과 같으며 스택으로 사용할 수도 있고, 큐로 사용할 수도 있다.
Deque의 조상은 Queue이며, 구현체로 ArrayDeque와 LinkedList 등이 있다.

ArrayDeque 클래스

스택으로 사용할 때 Stack 클래스보다 빠르며, 큐로 사용할 때는 LinkedList보다 빠르다.
사이즈에 제한이 없다.
null 요소는 저장되지 않는다

Deque	Queue	Stack
offerLast()	offer()	push()
pollLast()	-	pop()
pollFirst()	poll()	-
peekFirst()	peek()	-
peekLast()	-	peek()

Deque<Integer> deque = new ArrayDeque<>();

deque.offerLast(100); // [100]
deque.offerFirst(10); // [10, 100]
deque.offerFirst(20); // [20, 10, 100]
deque.offerLast(30); // [20, 10, 100, 30]

deque.pollFirst(); // 20 <- [10, 100, 30]
deque.pollLast(); // [10, 100] -> 30
deque.pollFirst(); // 10 <- [100]
deque.pollLast(); // [] -> 100

LinkedList 클래스

LinkedList는 List 인터페이스와 Queue 인터페이스를 동시에 상속받고 있기 때문에, 스택 / 큐 로서도 응용이 가능하다.
실제로 LinkedList 클래스에 큐 동작과 관련된 메서드를 지원한다. (push, pop, poll, peek, offer ..등)

Queue<String> linkedList = new LinkedList<>(); // Queue 타입으로 받음

linkedList.offer("Hello");
linkedList.offer("World");
linkedList.offer("Power");

linkedList.poll(); // "Hello" - 선입선출

System.out.println(linkedList); // [World, Power]

왜 여기서 LinkedList가 또 나와? 싶을 것 같다. 그림을 보면 알겠지만 LinkedList는 List(리스트)를 구현하기도 하지만, Deque(덱)도 구현한다. 그리고 Deque Interface는 Queue Interface를 상속받는다.

즉, LinkedList는 사실상 3가지 용도로 쓸 수 있다는 것이다.

List
Deque
Queue

실제로도 LinkedList class를 보면 다음과 같이 List와 Deque를 모두 구현한다.

왜 LinkedList를 받을까? 간단하게 말하자면, 앞서 List를 설명할 때도 말했지만, ArrayList와 LinkedList의 차이점은 Object[] 배열로 관리하느냐, Node라는 객체를 연결하여 관리하느냐의 차이였다.

마찬가지다. Deque 또는 Queue를 LinkedList 처럼 Node 객체로 연결해서 관리하길 원한다면 LinkedList를 쓰면 된다. 원리 자체는 크게 다르지 않기 때문에 LinkedList 하나에 다중 인터페이스를 포함하고 있는 것이다.

반대로 ArrayList처럼 Object[] 배열로 구현되어 있는 것은 ArrayDeque 이다. 물론 LinkedList와 ArrayDeque 둘 다 Deque을 구현하고 있고, Deque은 Queue를 상속받기 때문에 Queue로도 쓰일 수 있다.

만약 자바에서 지원하는 컬렉션에서 '일반적인 큐'를 사용하고자 한다면 LinkedList로 생성하여 Queue로 선언하면 된다.

Set 인터페이스

Set(세트)는 말 그대로 '집합'이다
데이터의 중복을 허용하지 않고 순서를 유지하지 않는 데이터의 집합 리스트
순서 자체가 없으므로 인덱스로 객체를 검색해서 가져오는 get(index) 메서드도 존재하지 않는다
중복 저장이 불가능하기 때문에 심지어 null값도 하나만 저장할 수 있다

HashSet 클래스

배열과 연결 노드를 결합한 자료구조 형태
가장 빠른 임의 검색 접근 속도를 가진다
내부적으서 HashMap으로 구현됨
추가, 삭제, 검색, 접근성이 모두 뛰어나다
대신 순서를 전혀 예측할 수 없다

좀 더 상세하게 말하자면 hash에 의해 데이터의 위치를 특정시켜 해당 데이터를 빠르게 색인(search)할 수 있게 만든 것이다. 즉, Hash 기능과 Set컬렉션이 합쳐진 것이 HashSet이다. 그렇기 때문에 삽입, 삭제, 탐색이 매우 빠른 컬렉션 중 하나다.

Set<Integer> hashSet = new HashSet<>();

hashSet.add(10);
hashSet.add(20);
hashSet.add(30);
hashSet.add(10); // 중복된 요소 추가

hashSet.size(); // 3 - 중복된건 카운트 X

hashSet.toString(); // [20, 10, 30] - 자료 순서가 뒤죽박죽

LinkedHashSet 클래스

순서를 가지는 Set 자료
추가된 순서 또는 가장 최근에 접근한 순서대로 접근 가능
만일 중복을 제거하는 동시에 저장한 순서를 유지하고 싶다면, HashSet 대신 LinkedHashSet을 사용하면 된다

Set<Integer> linkedHashSet = new LinkedHashSet<>();

linkedHashSet.add(10);
linkedHashSet.add(20);
linkedHashSet.add(30);
linkedHashSet.add(10); // 중복된 수 추가

linkedHashSet.size(); // 3 - 중복된건 카운트 X

linkedHashSet.toString(); // [10, 20, 30] - 대신 자료가 들어온 순서대로 출력

TreeSet 클래스

이진 검색 트리(binary search tree) 자료구조의 형태로 데이터를 저장
중복을 허용하지 않고, 순서를 가지지 않는다
SortedSet Interface의 이름을 보면 알 수 있듯 이를 구현한 TreeSet은 데이터의 '가중치에 따른 순서'대로 정렬되어 보장한다는 것이다.
정렬, 검색, 범위 검색에 높은 성능을 뽐낸다.
Tree 라는 자료구조 자체가 데이터를 일정 순서에 의해 정렬하는 구조다. 거기에 더해진 것이 바로 Set인 중복값 방지 자료구조인 것이다

Set<Integer> treeSet = new TreeSet<>();

treeSet.add(7);
treeSet.add(4);
treeSet.add(9);
treeSet.add(1);
treeSet.add(5);

treeSet.toString(); // [1, 4, 5, 7, 9] - 자료가 알아서 정렬됨

EnumSet 추상 클래스

Enum클래스와 함께 동작하는 Set 컬렉션이다
중복 되지 않은 상수 그룹을 나타내는데 사용된다
산술 비트 연산을 사용하여 구현되므로 HashSet 보다 훨씬 빠르며, 적은 메모리를 사용한다
단, enum 타입의 요소값만 저장할 수 있고, 모든 요소들은 동인한 enum 객체에 소속되어야 한다
EnumSet은 추상 클래스고 이를 상속한 RegularEnumSet 혹은 JumboEnumSet 객체를 사용하게 된다.

enum Color {
    RED, YELLOW, GREEN, BLUE, BLACK, WHITE
}

public class Client {
    public static void main(String[] args) {
        // 정적 팩토리 메서드를 통해 RegularEnumSet 혹은 JumboEnumSet 을 반환
        // 만일 enum 상수 원소 갯수가 64개 이하면 RegularEnumSet, 이상이면 JumboEnumSet 객체를 반환
        EnumSet<Color> enumSet = EnumSet.allOf(Color.class);

        for (Color color : enumSet) {
            System.out.println(color);
        }

        enumSet.size(); // 6

        enumSet.toString(); // [RED, YELLOW, GREEN, BLUE, BLACK, WHITE]
    }
}

Map 인터페이스

키(Key)와 값(value)의 쌍으로 연관지어 이루어진 데이터의 집합
값(value)은 중복되서 저장될수 있지만, 키(key)는 해당 Map에서 고유해야만 한다.
만일 기존에 저장된 데이터와 중복된 키와 값을 저장하면 기존의 값은 없어지고 마지막에 저장된 값이 남게 된다.
저장 순서가 유지 되지 않는다

추상 메서드	설명
void clear()	Map의 모든 객체를 삭제
boolean containsKey(Object key)	지정된 key객체와 일치하는 객체가 있는지 확인
boolean containsValue(Object value)	지정된 value객체와 일치하는 객체가 있는지 확인
Set entrySet()	Map에 저장된 key-value쌍을 Map.Entry타입의 객체로 저장한 Set을 반환
boolean equals(Object o)	동일한 Map인지 비교
Object get(Object key)	지정한 key객체에 대응하는 value객체를 반환
int hashCode()	해시코드를 반환
boolean isEmpty()	Map이 비어있는지 확인
Set keySet()	Map에 저장된 모든 key객체를 반환
Object put(Object key, Object value)	Map에 key객체와 value객체를 연결(mapping)하여 저장
void putAll(Map t)	지정된 Map의 모든 key-value쌍을 추가
Object remove(Object key)	지정한 key객체와 일치하는 key-value객체를 삭제
int size()	Map에 저장된 key-value쌍의 개수를 반환
Collection values()	Map에 저장된 모든 value객체를 반환

※ 참고

Map 인터페이스의 메소드를 보면, Key값을 반환할때 Set 인터페이스 타입으로 반환하고, Value값을 반환할때 Collection 타입으로 반환하는걸 볼 수 있다.
Map 인터페이스에서 값(value)은 중복을 허용하기 때문에 Collection 타입으로 반환하고, 키(key)는 중복을 허용하
지 않기 때문에 Set 타입으로 반환하는 것이다.

Map.Entry 인터페이스

Map.Entry 인터페이스는 Map 인터페이스 안에 있는 내부 인터페이스이다.
Map 에 저장되는 key - value 쌍의 Node 내부 클래스가 이를 구현하고 있다.
Map 자료구조를 보다 객체지향적인 설계를 하도록 유도하기 위한 것이다.

Map.Entry 내부 인터페이스 와 HashMap 안의 Map.Entry를 구현하고 있는 Node 내부 클래스

메서드	설 명
boolean equals(Object o)	동일한 Entry 인지 비교
Object getKey( )	Entry 의 key 객체를 반환
Object getValue( )	Entry 의 value 객체를 반환
int hashCode( )	Entry 의 해시코드 반환
Object setValue(Object value)	Entry 의 value 객체를 지정된 객체로 바꾼다.

Map<String, Integer> map = new HashMap<>();
map.put("a", 1);
map.put("b", 2);
map.put("c", 3);

// Map.Entry 인터페이스를 구현하고 있는 Key-Value 쌍을 가지고 있는 HashMap의 Node 객체들의 Set 집합을 반환
Set<Map.Entry<String, Integer>> entry = map.entrySet();

System.out.println(entry); // [1=a, 2=b, 3=c]

// Set을 순회하면서 Map.Entry를 구현한 Node 객체에서 key와 value를 얻어 출력
for (Map.Entry<String, Integer> e : entry) {
    System.out.printf("{ %s : %d }\n", e.getKey(), e.getValue());
}

HashMap 클래스

Hashtable을 보완한 컬렉션
배열과 연결이 결합된 Hashing형태로, 키(key)와 값(value)을 묶어 하나의 데이터로 저장한다
중복을 허용하지 않고 순서를 보장하지 않는다
키와 값으로 null이 허용된다
추가, 삭제, 검색, 접근성이 모두 뛰어나다
HashMap은 비동기로 작동하기 때문에 멀티 쓰레드 환경에서는 어울리지않는다 (대신 ConcurrentHashMap 사용)

Map<String, String> hashMap = new HashMap<>();

hashMap.put("love", "사랑");
hashMap.put("apple", "사과");
hashMap.put("apple2", "사과"); // key 값은 중복이 불가능하지만 value는 중복 가능

// key가 중복될 경우 나중에 들어온 데이터로 덮어씌워짐.
hashMap.put("baby", "아기");
hashMap.put("baby", "아기 중복");
hashMap.put(null, "널값"); // null 허용

hashMap.get("apple"); // "사과"


// hashmap의 key값들을 set 집합으로 반환하고 순회
for(String key : hashMap.keySet()) {
    System.out.println(key + " => " + hashMap.get(key));
}
/*
love => 사랑
null => 널값
apple => 사과
baby => 아기 중복
apple2 => 사과
*/

LinkedHashMap 클래스

HashMap을 상속하기 때문에 흡사하지만, Entry들이 연결 리스트를 구성하여 데이터의 순서를 보장한다.
일반적으로 Map 자료구조는 순서를 가지지 않지만, LinkedHashMap은 들어온 순서대로 순서를 가진다.

Map<Integer, String> hashMap = new HashMap<>();

hashMap.put(10000000, "one");
hashMap.put(20000000, "two");
hashMap.put(30000000, "tree");
hashMap.put(40000000, "four");
hashMap.put(50000000, "five");

// {20000000=two, 40000000=four, 10000000=one, 30000000=tree, 50000000=five}
for(Integer key : hashMap.keySet()) {
    System.out.println(key + " => " + hashMap.get(key)); // HashMap 들어온 순서 보장X
}

// ----------------------------------------------

Map<Integer, String> linkedHashMap = new LinkedHashMap<>();

linkedHashMap.put(10000000, "one");
linkedHashMap.put(20000000, "two");
linkedHashMap.put(30000000, "tree");
linkedHashMap.put(40000000, "four");
linkedHashMap.put(50000000, "five");

//{10000000=one, 20000000=two, 30000000=tree, 40000000=four, 50000000=five}
for(Integer key : linkedHashMap.keySet()) {
    System.out.println(key + " => " + linkedHashMap.get(key)); // LinkedHashMap 들어온 순서 보장
}

TreeMap 클래스

이진 검색 트리의 형태로 키와 값의 쌍으로 이루어진 데이터를 저장 (TreeSet 과 같은 원리)
TreeMap은 SortedMap 인터페이스를 구현하고 있어 Key 값을 기준으로 정렬되는 특징을 가지고 있다.
정렬된 순서로 키/값 쌍을 저장하므로 빠른 검색(특히 범위 검색)이 가능하다
단, 키와 값을 저장하는 동시에 정렬을 행하기 때문에 저장시간이 다소 오래 걸리다
정렬되는 순서는 숫자 → 알파벳 대문자 → 알파벳 소문자 → 한글 순이다.

Map<Integer, String> treeMap = new TreeMap<>();

treeMap.put(1, "Toby");
treeMap.put(2, "Ruth");
treeMap.put(3, "jennifer");
treeMap.put(4, "Mark");
treeMap.put(5, "Dan");
treeMap.put(6, "Gail");

for(Integer key : treeMap.keySet()) {
    System.out.println(key + " => " + treeMap.get(key));
}
/*
1 => Toby
2 => Ruth
3 => jennifer
4 => Mark
5 => Dan
6 => Gail
*/

HashTable 클래스

자바 초기 버전에 나온 레거시 클래스
Key를 특정 해시 함수를 통해 해싱한 후 나온 결과를 배열의 인덱스로 사용하여 Value를 찾는 방식으로 동작된다
HashMap 보다는 느리지만 동기화가 기본 지원된다
키와 값으로 null이 허용 X

Map<String, Integer> hashtable = new HashMap<>();

hashtable.put("연필", 200);
hashtable.put("볼펜", 3000);
hashtable.put("샤프", 300);
hashtable.put("필통", 15000);

for (String key : hashtable.keySet()) {
    System.out.println(key + " => " + hashtable.get(key));
}
/*
필통 => 15000
볼펜 => 3000
샤프 => 300
연필 => 200
*/

컬렉션 프레임워크 선택 시점

지금 까지 자바의 컬렉션 프레임워크 자료구조 종류에 대해 간단히 알아보았다. 워낙 종류도 많고 똑같은 자료구조 이지만 각 쓰임새와 특징에 따라 나누니 정리하기가 까다롭다.

그렇다고 컬렉션 마다 일일히 특징을 외우기 보다는, 아래 그림을 통해 언제 어느때에 어떤 컬렉션을 선택하여 사용하면 좋을지 추적해보자.

ArrayList
- 리스트 자료구조를 사용한다면 기본 선택
- 임의의 요소에 대한 접근성이 뛰어남
- 순차적인 추가/삭제 제일 빠름
- 요소의 추가/삭제 불리
LinkedList
- 요소의 추가/삭제 유리
- 임의의 요소에 대한 접근성이 좋지 않음
HashMap / HashSet
- 해싱을 이용해 임의의 요소에 대한 추가/삭제/검색/접근성 모두 뛰어남
- 검색에 최고성능 ( get 메서드의 성능이 O(1) )
TreeMap / TreeSet
- 요소 정렬이 필요할때
- 검색(특히 범위검색)에 적합
- 그래도 검색 성능은 HashMap보다 떨어짐
LinkedHashMap / LinkedHashSet : HashMap과 HashSet에 저장 순서 유지 기능을 추가
Queue : 스택(LIFO) / 큐(FIFO) 자료구조가 필요하면 ArrayDeque 사용
Stack, Hashtable : 가급적 사용 X (deprecated)

면접 예상 질문

Q. 컬렉션의 상속 구조에 대해 질문 및 각 인터페이스의 특징.

[예시]

List 인터페이스는 순서가 있고, 데이터의 중복을 허용 하며 색인을 사용하여 특정위치에 삽입하거나 접근할 수 있다.

구현 클래스의 ArrayList 경우 빠르고 순차적인 접근에 강점이 있고, vector는 모든 메소드가 동기화 되어 있는 강점이 있고, LinkedList 는 양방향 포인터 구조로 삽입/삭제가 빈번할때 빠른 성능을 보장 한다.(스택, 큐, 양방향 큐등을 만들기 위한 용도)

Map 인터페이스는 Key, Value 가 쌍으로 이루어져 있다.

구현 클래스의 HashMap 은 해시 테이블을 사용하고 중복을 허용하지 않으며, key-value 가 null을 허용 합니다.

HashTable 은 HashMap 보다 느리지만 동기화를 지원하고 key-value 가 null 을 허용하지 않습니다.

TreeMap 은 이진검색트리의 형태로 키와 값의 쌍으로 이루어진 데이터를 저장하며, 정렬된 순서로 저장이 되므로 검색이

빠릅니다. LinkedHashMap 은 HashMap을 상속받아 흡사 하나, 입력한 순서대로 반복 가능 합니다.

Q. ArrayList, HashSet, HashMap은 멀티 스레드 환경에서 안전하지 않는데, thread-safe 있게 사용하려면 어떻게 해야하는지

synchronized 를 통해서 thread-safe 한 리스트를 만들수 있다고 설명 가능

[ 꼬리 질문 ]

하지만 락이 걸렸을 때 대처 방안은??

(참고: https://cornswrold.tistory.com/209)

자바에서는 멀티스레드환경에서 안전하면서도, 스레드가 병렬적으로 작업을 처리할 수 있도록 java.util.concurrent 패키지에서 ConcurrentHashMap, ConcurrentLinkedQueue를 제공 한다. 이 구현체들은 부분(segment) 잠금을 사용하기 때문에 병렬적으로 작업 수행이 가능하다.

예를 들면, Map에 10개의 요소가 저장되어 있을 경우, 1개의 요소를 처리할 때 그 처리하는 곳이 포함된 부분만 락을 걸고 나머지부분은 다른스레드가 변경할 수 있게 하는 것이다. (1개의 요소를 처리할 때 나머지 10개 요소에 락을 거는것이 전체 잠금)

Map<K,V> map = new ConcurrentHashMap<K,V>();
Queue<E> queue = new ConcurrentQueue<E>();

참고

개요

자료구조

JAVA Collection Framework

컬렉션 프레임워크 종류

1. 컬렉션 프레임워크의 이점

2. 구성요소

3. Collection Framework 의 종류

Iterable 인터페이스

Collection 인터페이스

List 인터페이스

ArrayList 클래스

LinkedList 클래스

Vector 클래스

Stack 클래스

Queue 인터페이스

PriorityQueue 클래스

Deque 인터페이스

ArrayDeque 클래스

LinkedList 클래스

Set 인터페이스

HashSet 클래스

LinkedHashSet 클래스

TreeSet 클래스

EnumSet 추상 클래스

Map 인터페이스

Map.Entry 인터페이스

HashMap 클래스

LinkedHashMap 클래스

TreeMap 클래스

HashTable 클래스

컬렉션 프레임워크 선택 시점

면접 예상 질문

Q. 컬렉션의 상속 구조에 대해 질문 및 각 인터페이스의 특징.

Q. ArrayList, HashSet, HashMap은 멀티 스레드 환경에서 안전하지 않는데, thread-safe 있게 사용하려면 어떻게 해야하는지

티스토리툴바