- 글을 작성한 이유
- 백준을 풀며 보통 스택, 큐를 사용할 경우 LinkedList를 자주 사용하였으나 ArrayDeque이 더 유리하다는 얘기가 있어 알아보려고 한다
- ArrayDeque란
- 우리가 기존에 사용하는 배열이며 원형큐로 만들어져 있다
- LinkedList란
- 우리가 알고있는 연결리스트
- 비교
- 왜 빠를까
이 두가지를 비교하는 이유
평소 백준을 풀며 스택, 큐를 사용하는 경우 LinkedList를 자주 사용했었습니다. 하지만 ArrayDeque이 LinkedList보다 성능이 더 좋다고 얘기가 나와서 한번 직접 비교해보고 추가적으로 각 결과에 대한 이유를 한번 파헤쳐보려고 합니다.
ArrayDeque란
기본적으로 ArrayDeque은 아래와 같이 배열로 데이터를 저장한다.
그리고 아래와 같은 형태의 원형 큐로 사용됩니다.
아래와 같이 원형 큐로써 알맞는 인덱스를 찾기 위한 메서드 또한 존재합니다.
이 과정에서 기존의 배열보다 더 많은 공간을 요구할 경우 더 큰 배열을 선언하여 저장합니다.
정리
- 배열로 데이터를 저장한다.
- 원형 큐로 구현되었다.
- 배열이다보니 최대 저장 가능한 수는 int의 가장 큰 수만큼 저장이 가능할 것이다.
애초에 배열이 아니더라도 int를 넘어가는 데이터를 저장한다면 오버플로우가 발생해서 에러가 당신을 반길 것이다.
LinkedList란
기본적으로 우리가 알고 있는 연결리스트로 구현된다.
따라서 head와 tail은 포인터 개념으로 작동하며 처음에는 null로 지정된 모습을 볼 수 있다.
또한 각 노드는 앞, 뒤 노드를 가리키기 위한 포인터와 현재 값으로 구성되어 있다.
정리
- 연결리스트로 구성되어있다.
- 각 노드는 앞 뒤 노드의 주소를 가지고 있다.
비교
package org.example;
import java.util.ArrayDeque;
import java.util.LinkedList;
public class Blog {
static int LONG_TIME = 500_000;
static ArrayDeque<Integer> deque = new ArrayDeque<>();
static LinkedList<Integer> linkedList = new LinkedList<>();
public static void main(String[] args) {
System.out.println("LONG_TIME = " + LONG_TIME);
System.out.println("dequeCreateTime(LONG_TIME) = " + dequeCreateTime(LONG_TIME));
System.out.println("linkedCreateTime(LONG_TIME) = " + linkedCreateTime(LONG_TIME));
System.out.println("dequeFindTime(LONG_TIME) = " + dequeFindTime(LONG_TIME));
System.out.println("linkedFindTime(LONG_TIME) = " + linkedFindTime(LONG_TIME));
System.out.println("dequeDeleteTime(LONG_TIME) = " + dequeDeleteTime(LONG_TIME));
System.out.println("linkedDeleteTime(LONG_TIME) = " + linkedDeleteTime(LONG_TIME));
}
public static long dequeCreateTime(int n) {
long start = System.currentTimeMillis();
for (int i=0; i<n; i++) {
deque.add(i);
}
long end = System.currentTimeMillis();
return end - start;
}
public static long linkedCreateTime(int n) {
long start = System.currentTimeMillis();
for (int i=0; i<n; i++) {
linkedList.add(i);
}
long end = System.currentTimeMillis();
return end - start;
}
public static long dequeFindTime(int n) {
long start = System.currentTimeMillis();
for (int i=0; i<n; i++) {
deque.contains(i);
}
long end = System.currentTimeMillis();
return end - start;
}
public static long linkedFindTime(int n) {
long start = System.currentTimeMillis();
for (int i=0; i<n; i++) {
linkedList.contains(i);
}
long end = System.currentTimeMillis();
return end - start;
}
public static long dequeDeleteTime(int n) {
long start = System.currentTimeMillis();
for (int i=0; i<n; i++) {
deque.remove();
}
long end = System.currentTimeMillis();
return end - start;
}
public static long linkedDeleteTime(int n) {
long start = System.currentTimeMillis();
for (int i=0; i<n; i++) {
linkedList.remove();
}
long end = System.currentTimeMillis();
return end - start;
}
}
왜 LinkedList는 느릴까?
추가
데이터를 추가하는 경우에는 “ArrayDeque 더 느리지 않을까?” 라는 생각을 했다. 왜냐하면 ArrayDeque 배열로 구성된 만큼 초기 배열에서 계속 증가시키는 경우 느릴 것이라고 생각했기 때문이다. 하지만 예상과는 정 반대의 결과가 나왔다.
이유는 간단하다. ArrayDeque 데이터를 배열에 넣어주고 head나 tail의 값을 변경하는 로직인 반면 LinkedList는 새로운 노드를 만들고 그것을 연결하는 과정을 거치기 때문이다. 사실 그렇게 큰 차이를 만들어내지 않지만 50만이라는 매우 큰 숫자라면 이러한 근소한 차이도 크게 차이가 나게될 것이다.
또한 배열의 크기를 조정하는 것은 처음에는 +2만큼 늘리지만 64이상 큰 배열의 크기를 가진다면 2배씩 적용이 되기 때문에 이는 유의미하게 많은 차이를 이끌어내지 못한다.
조회
사실 조회를 생각하면 그렇게 좋은 자료구조가 아니다. 하지만 비교를 위해 조회도 추가시켜보았다.
ArrayDeque 4배는 빠른 모습을 볼 수 있다. 이는 배열이 연결리스트보다 CPU의 캐시에 친화적인 자료구조이기 때문이다. 보통 CPU가 값을 가져올 때 해당 값만을 가져오는 것이 아닌 근처 주소에 있는 데이터도 함께 가져온다. 배열의 경우 모든 데이터가 서로 붙어있어 하나의 데이터를 가져올 때 근처의 데이터를 가져오게 되며 이는 무조건 배열에 있는 데이터를 가져오게 된다. 하지만 연결리스트는 서로 주소를 저장하여 이어놨을 뿐 주소가 근처라는 보장을 하지 않는다. 따라서 연결리스트는 대부분의 경우에서 하나의 데이터 값을 가져올 때 다른 데이터를 함께 가져오지 못하여 메모리에 더 많은 접근을 하게 된다. 이 과정에서 조회를 하는 경우에 차이가 나게 된다.
삭제
데이터를 삭제하는 경우에는 데이터를 삭제하는 과정에서 큰 차이가 있다고 생각하면 된다. ArrayDeque 경우 배열에 해당 위치를 null로 지정한 후 tail 혹은 head의 위치를 조정하면 된다. 하지만 LinkedList의 경우 해당 노드의 모든 값을 null로 바꾸어 GC가 해당 노드를 처리하도록 만들고 앞, 뒤 노드의 연결을 이어주면 된다.
모든 과정에서 CPU 캐시에 의한 차이도 존재한다.
그럼 LinkedList는 무엇 때문에 만들어 둔 것일까?
결론부터 말하자면 LinkedList는 List도 implements를 받기 때문에 sort와 같은 리스트가 가지는 특성을 사용할 수 있지만 ArrayDeque는 List로 implements를 받지 않는다. 따라서 현재 head에서 4번째에 있는 값을 바꾸려면 LinkedList는 set으로 설정할 수 있는 반면 ArrayDeque는 그런 메서드가 존재하지 않는다. 순수 Deque의 시선에서는 Deque이 좋을 수 있지만 정렬과 같이 List의 기능을 사용하고 싶다면 LinkedList를 사용하는 것이 더 좋아보인다.
느낀점
- LinkedList를 애용하였지만 ArrayDeque을 사용해야할 것 같다.
- 직접 LinkedList와 ArrayDeque의 코드를 보며 성능차이도 느꼈지만 List 인터페이스를 상속받지 않은 차이도 존재하는 점을 보고 단순한 성능차이 이상을 깨닫는 것 같다.
- 직접 실험해보니 예상보다 큰 차이가 있어 놀라웠다. 특히 생성은 그렇게 차이가 없을 줄 알았는데 생각보다 차이가 커서 놀랐다.
