📌 테스트 내용
어제 자바를 이용해 알고리즘 스터디를 진행하다가 큐의 선언이 c++과 달리
자바에서는 큐를 선언할때 LinkedList와 ArrayDeque를 이용하는 것을 확인할 수 있었다. 단순한 호기심으로 둘의 성능 차이는 어떻게 되고 언제 사용할지 궁금하여 테스트를 진행해보았다.
💡 큐의 선언
Queue< Integer> q1 = new LinkedList< Integer>();
Queue< Integer> q1 = new ArrayDeque< Integer>();
두개의 성능 차이를 확인하기 위해 간단히 테스트 해보면,
위 코드는 1000만 개의 요소를 각각 LinkedList를 이용한 큐와 ArrayDeque를 이용한 큐에 추가하고, 큐에서 모든 요소를 제거하는 작업을 수행하고 있다. 즉, 요소의 추가와 제거가 빈번하게 발생하는 경우에는 ArrayDeque를 이용하는 것이 더 빠른 성능을 보임을 확인할 수 있다.
다만, ArrayDeque 클래스는 중간에 요소를 삽입하는 메소드가 없다. 따라서 중간에 요소를 삽입하는 기능이 필요한 경우는 LinkedList를 이용하는 것이 좋다.
💡 ArrayList와 ArrayDeque의 차이점은?
- ArrayList
1) 요소를 추가할 때 해당 요소 뒤에 있는 모든 요소를 한 칸씩 오른쪽으로 이동
2) ArrayList는 요소를 추가할 때마다 배열의 크기를 조절해야 하기 때문에, ArrayDeque에 비해 더 많은 메모리 할당이 발생- ArrayDeque
1) 내부 구현에서 양쪽 끝에 포인터를 가지고 있기 때문에, 양쪽 끝에 요소를 추가하는 경우에는 상수 시간에 요소를 추가할 수 있다.
그럼 단순 접근할때 성능차이는?
이번에도 ArrayDeque가 근소하지만 접근하는 데 걸리는 시간이 더 짧음을 확인할 수 있다.
ArrayDeque는 내부적으로 요소를 배열에 저장하기 때문에, 인덱스로 요소에 바로 접근할 수 있는 반면,
LinkedList는 각 요소가 자신 다음에 연결된 요소를 참조하고 있어서, 특정 인덱스의 요소에 접근하려면 처음부터 해당 인덱스까지 모든 요소를 순회해야 한다. 따라서 LinkedList를 이용하는 것이 앞쪽 요소에 접근하는데 시간이 더 걸린다.
📌 정리
-
ArrayDeque를 이용해 선언
-- 큐의 앞과 뒤에서 빠르게 요소를 추가하고 삭제하는 경우 linkedlist보다 성능이 좋다
-- 중간에 요소를 삽입하거나 삭제하는 메소드 제공하지 않음
-- 큐와 스택의 기능을 모두 제공하면서도 내부 구현이 배열로 이루어져 있어서 빠른 접근 속도를 제공
-- 실제로 문서에서도 linkedlist보다 빠름을 언급
-
LinkedList를 이용해 선언
-- 중간에 요소를 삽입하거나 삭제해야 하는 경우 이용
앞으로 알고리즘 풀 때 왠만하면 arraydeque를 이용하는 것이 좋을 것 같다는 생각이 들었다.
