[JAVA] 큐 구현은 어느것이 적당할까? LinkedList vs ArrayDeque

보통 배열의 경우 고정된 크기가 주어지기 때문에 검색이 빠르지만

삽입 삭제시 배열 크기 재 조정때문에 추가 비용 및 연산이 발생합니다.

그리고 공간 비효율성과 배열의 재배치가 일어납니다.

그렇다면 큐는 배열보다는 리스트로 구현하는게 낫지 않을까 하는 생각이 들 수 있습니다. 

 

그러나 Queue를 구현할때 ArrayDeque로 구현하는 것이 LinkedList로 구현하는 것보다 빠르다고

Java API document는 설명하고 있습니다.

 

왜 ArrayDeque가 LinkedList보다 빠른걸까요??

그 이유는 다음과 같이 2개 입니다. 출처 : http://javaqueue2010.blogspot.com/

 

 

<수행속도>

ArrayDeque는 Array에 의해 지원되며 Array는 LinkedList보다  cache-locality에 좀 더 친숙하다고 합니다.

(LinkedList는 다음 노드가 있는 곳으로 가려고 다른 간접적인 경로를 거쳐갑니다.)

 

<메모리>

ArrayDeque는 다음 노드에 대한 추가 참조를 유지할 필요가 없으므로 LinkedList보다 메모리 효율적입니다.

 

 

즉, 쉽게 말해서

 

큐 라는 자료구조의 특징을 살펴보자면 큐는 FIFO 특성을 갖고 있습니다.

삽입은 큐의 맨 처음 삭제는 큐의 맨 마지막에 일어납니다.

따라서 중간에 삽입되거나 삭제되는 경우가 없습니다.

 

만약에 배열의 삽입 삭제가 빈번하지 않고 양끝에서만 삽입 삭제의 연산이 일어난다고 가정했을때

시간복잡도는 O(1)으로 리스트와 별 차이가 없게 됩니다.

심지어 컴파일 할때도 바이트코드로 변형시키거나 캐싱할때 배열은 최적화( loop optimization )가 잘되고 리스트는 그렇지 않다고 합니다. 

 

이 토론은 https://okky.kr/article/445763 에서 좀 더 자세하게 다루고 있으니

참고 하시면 좋을것 같습니다.