ArrayDeque, LinkedList 의 삽입 추출 시 걸리는 수행 시간을 측정하고 비교, 정리한 글 입니다.
연산 | ArrayDeque | LinkedList |
---|---|---|
삽입 | O(1) | O(1) |
추출 | O(1) | O(1) |
[리스트 시간복잡도 비교 정리 글] 에서 살펴본 것 처럼 같은 시간복잡도라도 실행 속도에 많은 차이가 있음을 확인할 수 있었습니다. 데크도 이와 같이 실행 속도에 차이가 나는지 측정해보고 정리해보려 합니다.
Deque<Integer> arrayDeque = new ArrayDeque<>();
// ArrayDeque<Integer> 1억개 삽입
for (int i = 0; i < 100000000; i++) {
arrayDeque.offer(1);
}
Deque<Integer> linkedList = new LinkedList<>();
// LinkedList<Integer> 1억개 삽입
for (int i = 0; i < 100000000; i++) {
linkedList.offer(1);
}
리스트 때와 비슷하게 같은 O(1)의 시간복잡도를 가지더라도 삽입속도가 많이 차이나는 것을 확인할 수 있습니다. Node 객체를 생성하는 비용이 많이드는 작업이 수반된다는 이유로 이렇게 더 오랜 시간이 소모된다는 것을 알 수 있습니다.
// ArrayDeque<Integer> 10만 개 추출
for (int i = 0; i < 100000; i++) {
arrayDeque.poll();
}
// LinkedList<Integer> 10만 개 추출
for (int i = 0; i < 100000; i++) {
linkedList.poll();
}
추출은 둘다 매우 빠른 속도로 실행되고, 어느 것을 사용해도 무방할 만큼 거의 차이를 보이지 않습니다. 반면에 삽입에서 속도차이가 많이 발생하기 때문에 코딩테스트나, 실무에서는 ArrayDeque를 사용하는게 더 바람직 해 보입니다.
❗️결론
비슷한 시간 복잡도라도 ArrayDeque가 LinkedList에 비해 삽입 속도가 더 빠르다는 것을 확인할 수 있다.
코딩테스트나, 실무에서는 동적 배열로 구현된 ArrayDeque를 사용하도록 하자!