큐
-
[JAVA] 큐 구현은 어느것이 적당할까? LinkedList vs ArrayDeque알고리즘/알고리즘 Tip! 2020. 4. 20. 12:42
보통 배열의 경우 고정된 크기가 주어지기 때문에 검색이 빠르지만 삽입 삭제시 배열 크기 재 조정때문에 추가 비용 및 연산이 발생합니다. 그리고 공간 비효율성과 배열의 재배치가 일어납니다. 그렇다면 큐는 배열보다는 리스트로 구현하는게 낫지 않을까 하는 생각이 들 수 있습니다. 그러나 Queue를 구현할때 ArrayDeque로 구현하는 것이 LinkedList로 구현하는 것보다 빠르다고 Java API document는 설명하고 있습니다. 왜 ArrayDeque가 LinkedList보다 빠른걸까요?? 그 이유는 다음과 같이 2개 입니다. 출처 : http://javaqueue2010.blogspot.com/ ArrayDeque는 Array에 의해 지원되며 Array는 LinkedList보다 cache-loc..