[Java] Deque의 구현

백준 1021번 회전하는 큐

• 위 문제를 풀며 학습한 Deque의 구현 방식별 차이점을 정리하고자 한다.

Deque in Java.util

Deque란 Double ended Queue로서 양단에서 삽입 삭제가 가능한 자료구조이다.

• Queue를 상속받는 인터페이스이다.
• 아래 4 종류의 구현체를 통해 구현 가능하다.
  1. ArrayDeque
  2. ConcurrentLinkedDeque
  3. LinkedBlockingDeque
  4. LinkedList
• 여담으로 발음은 deck이다.

Deque vs List

List 인터페이스를 LinkedList로 구현한다면 똑같은 Deque인데 어떤 차이점을 가지는가?

• Deque는 List와 달리 인덱스를 통한 원소 접근을 지원하지 않는다.
• 성능관련 이야기는 구현체에서 다루겠다.

구현체

이제 구현체를 보자. Deque 구현시 보통 ArrayDeque, LinkedList 두 가지를 주로 사용한다. 또, 이들의 성능 차이를 알아보자.

• 속도
  - ArrayDeque가 LinkedList보다 더 빠르다
  • 출처의 성능 실험에 따르면 배열이 연결리스트보다 cache-locality에 적절하여 두 배 정도 빠르다고 한다.
• 메모리
  - ArrayDeque는 다음 노드 참조를 위한 공간이 필요 없기에 더 적은 메모리 공간이 사용된다.

ArrayDeque vs LinkedList

Deque arrayDeck = new ArrayDeque<>();
LinkedList linkedListDeque = new LinkedList<>();

• 위 두 변수는 모두 Deque으로 사용 가능하다. 다만, 앞서 말했듯이 LinkedList는 원소 인덱스 접근이 가능하여 linkedListDeque.indexOf()를 사용 가능하지만 arrayDeck은 사용할 수 없다.

정리

Deque 구현	ArrayDeque	LinkedList
속도	빠르다	느리다
메모리	더 적게 사용	더 많이 사용
인덱스 접근	불가능	가능

출처

자바 공식 문서: https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html
성능 실험: http://javaqueue2010.blogspot.com/

수정사항

List<Integer> ls = new LinkedList<>();

• ls는 LinkedList에만 구현된 매소드는 사용할 수 없고 오직 List에 정의되어 있는 매소드만 사용할 수 있다. 때문에 Deque으로 사용하기 위해서는 다음과 같이 선언해야한다.

  LinkedList<Integer> LinkedListDeque = new LinkedList();