[Java] 자바 데크(ArrayDeque, LinkedList) 시간 복잡도 비교 정리

---

ArrayDeque, LinkedList 의 삽입 추출 시 걸리는 수행 시간을 측정하고 비교, 정리한 글 입니다.

---

데크 시간 복잡도 (ArrayDeque, LinkedList)

연산	ArrayDeque	LinkedList
삽입	O(1)	O(1)
추출	O(1)	O(1)

[리스트 시간복잡도 비교 정리 글] 에서 살펴본 것 처럼 같은 시간복잡도라도 실행 속도에 많은 차이가 있음을 확인할 수 있었습니다. 데크도 이와 같이 실행 속도에 차이가 나는지 측정해보고 정리해보려 합니다.

---

Element 삽입 - O(1)

ArrayDeque

Deque<Integer> arrayDeque = new ArrayDeque<>();
// ArrayDeque<Integer> 1억개 삽입
for (int i = 0; i < 100000000; i++) {
	arrayDeque.offer(1);
}

LinkedList

Deque<Integer> linkedList = new LinkedList<>();
// LinkedList<Integer> 1억개 삽입
for (int i = 0; i < 100000000; i++) {
	linkedList.offer(1);
}

리스트 때와 비슷하게 같은 O(1)의 시간복잡도를 가지더라도 삽입속도가 많이 차이나는 것을 확인할 수 있습니다. Node 객체를 생성하는 비용이 많이드는 작업이 수반된다는 이유로 이렇게 더 오랜 시간이 소모된다는 것을 알 수 있습니다.

Element 추출 - O(1)

ArrayDeque

// ArrayDeque<Integer> 10만 개 추출
for (int i = 0; i < 100000; i++) {
	arrayDeque.poll();
}

LinkedList

// LinkedList<Integer> 10만 개 추출
for (int i = 0; i < 100000; i++) {
	linkedList.poll();
}

추출은 둘다 매우 빠른 속도로 실행되고, 어느 것을 사용해도 무방할 만큼 거의 차이를 보이지 않습니다. 반면에 삽입에서 속도차이가 많이 발생하기 때문에 코딩테스트나, 실무에서는 ArrayDeque를 사용하는게 더 바람직 해 보입니다.

❗️결론

비슷한 시간 복잡도라도 ArrayDeque가 LinkedList에 비해 삽입 속도가 더 빠르다는 것을 확인할 수 있다.

코딩테스트나, 실무에서는 동적 배열로 구현된 ArrayDeque를 사용하도록 하자!