*본 게시물은 개인 공부를 기록하기 위해 작성하였으며, 내용에 오류가 있을 수 있음을 밝힙니다.
컬렉션 프레임워크란?
컬렉션 : 여러 객체를 모아 놓은 것.
프레임워크 : 표준화, 정형화된 체계적인 프로그래밍 방식
-> 컬렉션 프레임워크 : 데이터를 효율적으로 저장하고 처리하기 위한 자료구조와 알고리즘을 제공하는 Java의 표준 라이브러리.
<Collection 인터페이스 상속 계층도>
위 그림은 Collection 인터페이스 상속 계층도이고, 여기서 검은색 박스는 인터페이스, 파란색 박스는 각 인터페이스를 상속받아 구현한 클래스들이다.
각 인터페이스들에 대해 간단하게 설명하자면,
List는 순서 O, 중복 O
Set은 순서 X, 중복 X
Map은 Key, Value쌍으로 데이터를 저장하는 자료구조이며, key는 중복 X, value는 중복O
Q) 돌발 퀴즈
아래의 3문장 중 어떤 문장이 틀린 문장일까요? 이유는? - 정답은 맨 아래에
1. Stack st = new Stack();
2. Queue q = new Queue();
3. Queue q = new LinkedList();
<Collection 인터페이스들을 구현한 클래스들 간단한 설명>
ArrayList
- 배열 기반 리스트
- 접근(탐색)이 빠르다.(인덱스)
- 삽입/삭제는 느리다.
- Vector와 달리 동기화X -> 락(lock)을 걸 필요가 없어서 빠르게 작동하고, 코드가 가벼워짐. But 멀티스레드 환경에서 위험할 수 있음.
LinkedList
- 접근(탐색)이 느리다.
- 삽입/삭제는 빠르다.
Stack
- LIFO 자료구조
PriorityQueue
- 일반적인 Queue가 먼저 들어온 순서대로 나가는 것과 달리, 정해진 우선순위가 높은 값이 먼저 나가는 큐, 우선순위 큐에 저장할 객체는 필수적으로 Comparable 인터페이스를 구현해야함.
-> 최단거리를 구할 경우, 작업 스케줄링 등에 사용
Deque
- 양쪽 끝에서 삽입과 삭제가 가능한 자료구조.
HashSet
- 데이터의 중복X 순서X, null값도 하나만 저장 가능.
- 가장 빠르고 기본적인 Set.- 내부적으로 HashMap 사용.- 삽입/삭제/탐색 속도 빠름 : O(1) //대신 순서를 전혀 예측할 수 없다.
--> 빠른 중복 제거 필요시 사용
Linked HashSet
- 입력한 순서를 유지하는 Set.- 속도는 HashSet보다 느림 (O(1)이지만 링크 관리 비용 존재)
--> 순서를 유지하면서 중복 제거 할 때 사용
TreeSet
- 정렬된 상태를 유지하는 Set. (자동 정렬)- Comparable, Comparator 필요- 속도는 O(log n)
--> 정렬된 상태로 데이터를 저장하고 싶을 때 사용
HashMap
- 일반적인 Map 구현체.- 순서 X, key중복 X, value중복 O- null key 1개, null value 여러 개 가능.- 동기화 X -> 스레드 안전 X but 빠름. (여러 스레드가 동시에 접근하면 문제가 생길 수 있으나 단일 스레드 환경에서는 불필요한 lock이 없어서 훨씬 빠르다.)
Linked HashMap
- 입력 순서를 유지하는 HashMap (입력 순서 그대로 키가 유지됨)- 성능은 HashMap보다 약간 떨어짐.
--> 입력 순서를 기억해야 할 때 사용
TreeMap
- Key를 기준으로 정렬된 Map (기본은 오름차순) ex) 입력 순서에 관계없이 {1=A, 2=B, 3=C...}- 속도는 O(log n)으로 Map 중 가장 느림.- null key 불가, null value는 가능.
--> 정렬이 필요할 때 사용
<간단한 성능 비교>
컬렉션 프레임워크의 대표적인 자료 구조인 ArrayList와 LinkedList를 성능(실행시간) 측면에서 비교해 보겠다.
(사실 성능은 시간복잡도+공간복잡도를 모두 고려해야 하지만 여기서는 시간적인 측면만 고려해서 작성하겠다.)
- Big O Notation
그전에 성능을 객관적인 수치로 비교하기 위해 필요한 개념인 Big O Notation에 대해 간단히 설명하자면, Big O Notation은 알고리즘이나 연산이 입력 크기 n에 따라 실행시간이 얼마나 빠른지를 표현하는 수학적 도구이다.
예를 들어, for문으로 i=1~10까지 반복한다면 10번의 연산이 필요하다. 이때 입력값의 크기 n=10이고, 연산도 총 10번이 필요하다. 즉, 입력값 n번만큼의 연산이 필요하므로 이를 Big O Notation으로 O(n)으로 표기한다.
그럼 for문 안에 for문이 중첩되어 있는 경우에는 어떨까? 위의 예시와 동일하게 입력값의 크기를 n=10이라고 하자. 즉, i가 1~10인 for문을 중첩하여 쓴 경우를 생각해 보자. 첫 번째 for문의 각 i마다 두 번째 for문의 i는 1~10까지 순회한다. 첫 번째 for문도 i값이 10개이므로 총 연산 수는 10의 제곱인 100이 된다. 즉, 입력값이 n일 때, n^2번만큼의 연산이 필요하므로 Big O Notation으로 O(n^2)으로 표기한다.
Big O Notation에는 주의해야 할 점이 있다.
첫 번째로는 O(?)의 ?에 들어갈 식은 최고차항만 표기하고, 계수는 항상 1로 한다는 것이다. 예를 들어, 어떤 알고리즘의 입력값의 크기가 n일 때, 연산 수가 2n^2 + 3n + 1이라고 하면, 최고차항인 2차항의 계수가 1이라는 점만 ?에 쓴다는 것이다. 따라서 이 경우에 Big O Notation은 O(2n^2)이 아닌 O(n^2)이 된다.
두 번째는 Big O Notation에서는 "최악의 경우 시간복잡도"를 기준으로 쓴다는 것이다. 예를 들어, ArrayList에 데이터를 삽입할 때, 최선의 경우는 마지막 인덱스에 데이터를 삽입하는 경우이고, 이때 단 한 번의 연산만이 필요하다. 평균적인 경우는 정중앙에 데이터를 삽입하는 경우인데, 이 경우 오른쪽 절반의 데이터들을 모두 한 칸씩 오른쪽으로 옮겨야 하므로 ArrayList의 크기가 n인 경우, (1/2)n번의 연산이 필요하다. 최악의 경우는 인덱스 0번에 데이터를 삽입하는 경우이고, 모든 데이터를 오른쪽으로 옮겨야 한다. 즉, ArrayList의 크기가 n인 경우, n번의 연산이 필요하다. 따라서 ArrayList에서 데이터를 삽입하는 경우의 시간 복잡도를 Big O Notation으로 표기하면 O(n)이 된다.
Big O Notation을 왜 알아야 하는가?
-> 개발자는 소프트웨어의 성능을 향상하기 위해 존재한다. 여기서 말하는 SW의 성능 향상이란 프로그램의 실행시간 즉, 시간복잡도를 의미하고 이를 수학적으로 표현하는 방법이 바로 Big O Notation이다. 컬렉션 프레임워크의 존재 이유는 데이터를 얼마나 효율적으로 관리하고 처리하느냐에 있는데, 이를 Big O Notation을 통해 객관적으로 파악할 수 있기 때문이다. 컬렉션 프레임워크의 다양한 클래스들을 상황에 맞게 사용하면 SW의 성능을 향상시켜 비용을 줄일 수 있다는 것이다.
따라서 우리는 주어진 문제 상황에서 어떤 자료구조를 사용하는 것이 효율적 일지에 대해 반드시 이해하고 있어야 한다.
이제 이 Big O Notation을 도입하여 ArrayList와 LinkedList에서 상황 별로 어떤 자료구조가 왜 효율적인지에 대해 설명해 보겠다.
<ArrayList>
크기가 n인 ArrayList에서 데이터를 탐색하는 경우는 인덱스를 통해 단 한 번의 연산으로 가능하다. -> O(1)
같은 ArrayList에서 데이터를 2번 인덱스에 삽입하려는 경우, 그림의 파란색 화살표와 같이 2번부터 n번까지의 모든 데이터를 오른쪽으로 한 칸씩 밀어야 한다. 따라서 (n-2)+1번의 연산이 필요하다. 인덱스 0번에 데이터를 삽입해야 하는 최악의 경우에는 총 n+1번의 연산이 필요하다.-> O(n)
<LinkedList>
크기가 n인 LinkedList에서 데이터를 탐색하는 경우는 순차적으로 모든 노드를 순회해야 하므로 마지막 인덱스에 있는 데이터를 찾아야 하는 최악의 경우 총 n번의 연산이 필요하다. -> O(n)
같은 LinkedList에서 데이터를 0번과 1번 인덱스에 삽입하려는 경우, 그림의 빨간색 화살표와 같이 노드 0번의 next를 Data로 바꾸고, 노드 1번의 prev를 Data로 바꾸면 된다. 따라서 총 2번의 연산만이 필요하고, 어떤 위치에 삽입하든 항상 동일하다. -> O(1)
결과를 정리하면, 데이터를 탐색하는 경우는 ArrayList가 유리하고, 데이터를 삽입, 삭제하는 경우는 LinkedList가 유리하다.
이처럼 어떤 자료구조를 쓰느냐에 따라 상황에 따른 효율이 크게 달라질 수 있다.
돌발퀴즈 정답 : 2번 - 인터페이스는 객체를 생성할 수 없다. 3번은 타입은 Queue이지만 LinkedList 클래스의 객체.