ArrayDeque vs. LinkedList

ArrayDeque는 자바 공식 문서에 의하면 Deque 인터페이스의 크기를 조정할 수 있는 배열의 구현이라고 적혀있다.

ArrayDeque와 LinkedList는 두개 전부 Deque 인터페이스를 구현하며, ArrayDeque는 배열의 특징을 가지며, LinkedList의 경우 List의 특징을 가지고 있다.

간단히 배열과 리스트의 차이를 알아보자.

Array vs. List

Array

Array는 같은 특성을 갖는 요소들이 메모리 상에 데이터가 연속적으로 저장된다.
메모리 상에 순차적으로 접근할 수 있기 때문에 순차 리스트이다.
이 때 각 요소에 접근하기 위해서 인덱스라는 것을 사용하여 순회하게 된다.

List

List 또한 배열과 마찬가지로 같은 특성을 갖는 요소들을 저장하지만, 배열과 달리 메모리 상에 연속적으로 저장되지 않고, 불연속적으로 데이터가 저장된다. 이 때 다음 요소에 접근하기 위해 포인터를 통해 연결된다.

Insert & Delete

• 배열 : 추가하거나 삭제하려고 할 때, List 보다 속도가 느리다. 왜냐하면 배열은 한 번 생성이 되면 크기가 고정되기 때문에 새로운 배열에 복사하여 크기를 조정해야 하기 때문이다.

• 리스트 : 추가나 삭제가 용이하다. 삽입 시에는 새로 들어오는 요소를 가리키는 방향으로 수정하면 되고, 삭제하는 경우에는 연결을 끊어버리면 되기 때문이다.

Search

• 배열 : 배열은 인덱스로 곧바로 이동할 수 있기 때문에 검색에 용이하다.
• 리스트 : 어느 요소에 가기 위해서는 처음부터 목표지점까지 이동해야 하기 때문에 검색은 배열보다 느리다.

그렇다면, 큐 구현에는 어떤 것이 더 좋은 것일까?

간략하게, 다음의 이유가 있다.

• LinkedList의 경우, 캐시에서 요소를 찾을 수 없기 때문에 메모리 효율이 ArrayDeque보다 비효율적이다.

• 양쪽 끝에서 작업을 할 경우, LinkedList보다 ArrayDeque가 더 효율이 좋다.

ArrayDeque보다 LinkedList가 더 좋은 경우는 순회 중 값을 삭제하는 것이다.

결론

앞으로 Queue를 구현할 일이 있다면 ArrayDeque를 사용하자.

Reference

• https://stackoverflow.com/questions/6163166/why-is-arraydeque-better-than-linkedlist
• https://docs.oracle.com/javase/8/docs/api/java/util/ArrayDeque.html
• https://docs.oracle.com/javase/8/docs/api/java/util/LinkedList.html