안녕하세요 오늘은 자바의 LinkedList와 ArrayDeque의 차이에 대해 알아보고 각각 언제 사용해야 하는지에 대해 알아보는 시간을 갖도록 하겠습니다.
LinkedList의 경우 이중 연결 리스트로 구현되어 있으며, 각 요소는 이전 요소와 다음 요소에 대한 참조를 가지고 있습니다. 따라서 요소를 삽입하거나 삭제할 때 유연성이 높으나 인덱스를 통한 접근 시 비효율적이기 때문에 추가 삭제가 빈번하게 발생하는 작업에서 유용합니다.
ArrayDeque의 경우 동적으로 크기가 조정되는 배열로 구현되어 있으며 Queue의 서브인터페이스인 Deque를 기반으로 만들어져 큐와 스택의 기능을 모두 제공하기 때문에 양쪽 끝에서의 요소 삽입 및 삭제가 가능합니다. 또한 LinkedList에 비해 cache-locality에 더 친숙하여 연산 속도가 더 빠르다고 합니다. 인덱스를 통한 접근 시 빠르지만 추가 삭제 시 상대적으로 느리게 됩니다. 따라서 요소의 추가 삭제가 빈번하지 않거나 임의 접근이 필요한 경우에 유용합니다.
하지만 Queue를 사용하는 경우 ArrayDeque를 사용하는 것이 항상 LinkedList보다 더 효율적입니다. Queue의 경우 FIFO 방식으로 동작하기 때문에 추가 삭제의 경우 O(1)의 속도로 동작합니다. 따라서 ArrayDeque로 생성된 Queue의 경우 양 끝에서만 추가 삭제가 발생하기 때문에 LinkedList와 성능 차이가 발생하지 않습니다. 또한 LinkedList와 달리 다음 노드에 대한 참조를 유지할 필요가 없기 때문에 더 적은 메모리를 사용합니다. 실제로 자바 공식문서에서도 ArrayDeque를 사용하는 것을 권장하고 있습니다.
요약하자면 ArrayDeque를 사용해서 Queue를 생성하는 것이 속도와 메모리 측면 모두 이득이기 때문에 ArrayDeque를 사용하는 것이 더 낫다고 할 수 있겠습니다.
