[cs] LinkedList보다 ArrayDeque

알고리즘 문제를 풀다보면 Queue 자료구조를 사용해야 할 때 LinkedList를 사용하면 시간초과가 나지만 ArrayDeque를 사용하면 통과하는 경우가 있다. 둘다 Queue의 동작을 기대하고 사용하는데 왜 속도차이가 날까

• ArrayDeque와 LinkedList의 속도차이는 캐시 적중률에 의해 발생한다.
• LinkedList는 데이터를 추가할 때 힙에 노드를 생성하고 앞 뒤 노드와 링크로 연결한다. 이때 VM은 메모리에 비연속적으로 노드를 생성한다.
• 반면에 ArrayDeque는 메모리에 연속적으로 배치되어 있다.
• 이러한 차이는 CPU의 캐시적중률(성능)에 영향을 미친다.

즉, 링크 상 노드가 바로 앞뒤에 있다고 하더라도 메모리 상에서는 노드가 연속적으로 배치 되어있지 않기 때문에 ArrayDeque에 비해 캐시적중률이 낮고 속도가 느리다. 중간 index에 삽입과 삭제 등이 일어나지 않는 Queue를 사용해야 하는 경우에는 ArrayDeque를 사용하는 것이 성능상 이점이 많다.