ArrayDeque

 

지금까지 알고리즘 문제 풀이를 하면서 Queue를 구현할 때 LinkedList를 주로 사용을 해왔다.

그러다 다른 사람들이 Queue를 구현할 때 ArrayDeque를 사용하는 것을 보고 ArrayDeque에 대해 자세히 알아보고 다른 자료구조들과의 장단점을 비교해보고 싶었다.

🔍 ArrayDeque

---

ArrayDeque는 Queue의 서브 인터페이스인 Deque 인터페이스를 구현한 구현체이다.

public interface Deque<E> extends Queue<E> {
...
}

public class ArrayDeque<E> extends AbstractCollection<E>
                           implements Deque<E>, Cloneable, Serializable
{...}

 

❗ ArrayDeque는 스택 또는 큐로 사용할 수 있다.

 

 

🖥️ Stack 또는 Queue로 사용하는 예시

// Stack으로 사용
Deque<String> stack = new ArrayDeque<>();
stack.push("first");
stack.push("second");
 
String get = stack.getFirst(); // "second" 
String pop = stack.pop(); // "second"

 

// Queue로 사용
Deque<String> queue = new ArrayDeque<>();
queue.offer("first");
queue.offer("second");

String get = stack.getLast(); // "second" 
String pop = stack.poll(); // "first"

 

🆚 Stack

public class Stack<E> extends Vector<E> 

 

Stack에 대한 공식 문서에서 아래와 같이 말하고 있다.

A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class.

 

LIFO 스택 작업은 Deque 인터페이스와 그 구현을 사용하면 보다 완전하고 일관되어 Deque가 우선적으로 사용되어야 한다.

 

🤔 LIFO 스택 작업에서 Stack보다 왜 Deque를 사용해야만 할까?

 

1️⃣ Class와 Interface

Stack은 Vector 클래스를 상속받고 있다.

자바는 다중 상속을 지원하지 않기 때문에 Stack 역시 다중 상속을 지원하지 않는다.

반면, 자바에서 클래스는 여러 인터페이스를 구현할 수 있다.

따라서, 객체지향 설계 관점에서 Deque 인터페이스는 Stack 클래스보다 유연성을 제공한다.

 

2️⃣ Lock

Stack은 모든 작업에 Lock이 사용된다.

• 단일 스레드 실행 성능이 저하될 수 있다.

Deque는 작업에 Lock을 사용하지 않아 단일 스레드에서 문제가 발생하지 않는다.

• 다중 스레드 실행의 경우에서 문제가 발생하는거 아닌가 ❓
  • ArrayDeque에 대한 동기화 데코레이터를 구현할 수 있다.

 

3️⃣ Iteration

Stack과 Deque 모두 java.util.Collection 인터페이스의 하위 유형으로 Iterable이 가능하다.

하지만, 동일한 순서로 동일한 요소를 넣은 Stack 객체와 Deque 인스턴스에 iteration 순서가 다르다.

 

Stack

• bottom → top

Stack<Integer> myStack = new Stack<>();
myStack.push(3);
myStack.push(2);
myStack.push(1);

Iterator<Integer> it = myStack.iterator();
while(it.hasNext()) {
     System.out.println(it.next());
}
// 결과
// 3
// 2
// 1

 

 

Deque

• top → bottom

Deque<Integer> myStack = new ArrayDeque<>();
myStack.push(3);
myStack.push(2);
myStack.push(1);

Iterator<Integer> it = myStack.iterator();
while(it.hasNext()) {
      System.out.println(it.next()); 
}
// 결과
// 1
// 2
// 3

 

Deque의 iterator가 기대하는 LIFO 스택작업에서의 순서로 작동한다.

 

4️⃣ 초기 용량 설정

Stack은 초기 용량 설정을 지원하지 않아 데이터의 삽입이 많아지면 배열을 복사하는 상황이 빈번하게 발생한다.

반면, ArrayDeque는 생성자로 배열의 초기 크기를 지정해줄 수 있고 용량를 초과하면 기존 용량의 2배로 늘려주거나 줄여주는 로직이 존재한다.

 

👀 ArrayDeque와 LinkedList

---

일반적으로 사용하는 Deque의 구현체는 ArrayDeque와 LinkedList이다.

LinkedList는 List와 Queue의 구현체이다.

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{ ... }

 

🤖 비교

• ArrayDeque 은 Deque 인터페이스의 구현체이며 크기가 재설정을 할 수 있다.
• LinkedList 는 List 의 구현체다.
• LinkedList 는 null 요소를 추가할 수 있지만 ArrayDeque 은 불가능하다.
• LinkedList 는 반복중에 현재 요소를 제거하는 것이 효율적이고, ArrayDeque 은 양쪽 끝에서 추가, 제거가 효율적이다.
• LinkedList 는 ArrayDeque 보다 더 많은 메모리를 소모한다.
• 메모리 소모량이 적을 때는 iterate 효율이 좋은 ArrayDeque 를 사용하고 스택의 사이즈가 커지거나 심한 변동이 예상될 때는 즉각적인 메모리 공간 확보를 위해 LinkedList 를 사용한다.

 

✖️ 연산 속도

ArrayDeque는 Array에 의해 지원되어 LinkedList보다 참조 지역성이 좋아 연산 속도가 더 빠르다.

 

📦 메모리

ArrayDeque는 LinkedList와 달리 다음 노드에 대한 참조를 유지할 필요가 없다.

따라서, LinkedList보다 더 메모리 효율적이다.

 

ArrayDeque 공식문서에서도 아래와 같이 LinkedList보다 속도와 메모리 측면에서 더 효율적이라고 말한다.

 

"This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue.”

 

🤯 Null

ArrayDeque는 null을 추가할 수 없지만, LinkedList는 null을 추가할 수 있다.

LinkedList<Integer> linkedList = new LinkedList<>();
ArrayDeque<Integer> arrayDeque = new ArrayDeque<>();

linkedList.add(null);
System.out.println(queue.size()); // 1

arrayDeque.add(null); // throw Exception

 

📕 참고자료

Introduction to the Java ArrayDeque | Baeldung

Why is ArrayDeque better than LinkedList

Java 의 Stack 대신 Deque

Java Deque vs. Stack | Baeldung

ArrayDeque (Java Platform SE 8 )