[Java] 큐 구현시 ArrayDeque과 LinkedList 성능 차이 (+ Deque, Queue 인터페이스)

bfs, dfs 문제 풀이를 하며 다른 사람들의 풀이를 보고 있는데, 큐를 구현할 때 어떤 사람은 ArrayDeque를, 어떤 사람은 LinkedList를 사용하는 것을 보았다. 이 둘은 어떤 차이가 있을까?

ArrayDeque vs LinkedList

ArrayDeque는 Queue의 서브인터페이스인 Deque의 구현체이고, LinkedList는 List와 Queue의 구현체이다. 따라서 LinkedList는 List의 특징을 가지고 있고, ArrayDeque은 배열의 특성을 가지고 있다고 할 수 있다. 이것을 기억하고 아래의 차이점들을 살펴보자.

연산 성능

ArrayDeque을 배열의 측면에서 바라봤을 때, deque의 양끝에서 삽입/삭제 연산이 일어날 경우 시간 복잡도가 O(1)이므로 삽입/삭제 성능이 우수하다. 또한 Random access가 가능하기에 원소 조회 시에도 속도가 빠르다. LinkedList도 삽입/삭제 연산 성능이 좋지만, 특정 원소에 접근 시의 성능은 ArrayDeque에 비해 떨어진다.

또한 ArrayDeque는 LinkedList에 비해 cache-locality에 더 친숙하여 연산 속도가 더 빠르다.

메모리

ArrayDeque은 LinkedList와 달리 다음 노드에 대한 참조를 유지할 필요가 없기 때문에 더 적은 메모리를 사용한다.

이런 차이점 때문에 큐 구현 시 ArrayDeque가 LinkedList보다 속도와 메모리 측면에서 더 효율적이라고 할 수 있으며, 이는 자바 공식문서에도 언급되어있다.

"This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue."

이외에도 다음과 같은 차이점들이 있다.

기타

• ArrayDeque은 크기 조정이 가능하다.
• ArrayDeque은 null을 요소로 추가할 수 없지만 LinkedList는 null을 추가할 수 있다.

참고
Why is ArrayDeque better than LinkedList