[Java] ArrayDeque

ArrayDeque, java.util.ArrayDeque, Java ArrayDeque, 어레이덱, circular array deque

정의

java.util.ArrayDeque<E> 는 원형 배열 (circular buffer) 기반의 Deque 구현. JDK 1.6 도입.

Stack 으로 쓰면 java.util.Stack 보다 빠르고, Queue 로 쓰면 LinkedList 보다 빠르다. Stack / Queue / Deque 가 필요할 때 거의 항상 첫 번째 선택.

시각화

내부 구조

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

    transient Object[] elements;       // 백킹 배열
    transient int head;                // head 인덱스
    transient int tail;                // tail 인덱스 (next slot)
}

원형 배열 (circular array) 방식.

• head 와 tail 인덱스를 따로 관리
• 배열의 끝에 도달하면 다시 0 으로 (modular arithmetic)
• 가득 차면 2 배로 grow

초기 (size 8):  [_ _ _ _ _ _ _ _]
                 ↑head=tail=0

addLast: a, b, c
        [a b c _ _ _ _ _]
         ↑head    ↑tail=3

addFirst: x
        [a b c _ _ _ _ x]
                       ↑head=7  tail=3

수정된 인덱스 = (i + length) % length

복잡도

작업	시간
addFirst, addLast	amortized O(1)
removeFirst, removeLast	O(1)
peek*, getFirst, getLast	O(1)
contains, remove(Object)	O(n)
임의 인덱스 접근	불가 (List 가 아니므로)

amortized 인 이유는 가득 찼을 때 2 배 grow + copy 비용 때문. 평균은 O(1).

LinkedList vs ArrayDeque

항목	LinkedList	ArrayDeque
백킹	linked nodes	원형 배열
메모리 / 원소	노드 헤더 + 두 포인터 (~32B)	슬롯 1 개 (4-8B)
캐시 친화	✗	✓
addFirst / addLast	O(1)	amortized O(1)
null 허용	✓	✗
List 가능	✓ (인덱스 O(n))	✗
Deque 가능	✓	✓
실측 속도	느림	빠름

null 거부와 List 미구현이 단점이지만, 그 외에는 모든 면에서 LinkedList 보다 우월.

Stack 사용 예

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);              // head 쪽에 push
stack.push(2);
stack.push(3);
stack.peek();               // 3
stack.pop();                // 3

Deque<E> stack = new ArrayDeque<>() 패턴이 [[java] Vector]] 기반 Stack<E> 보다 두세 배 빠르다.

Queue 사용 예

Queue<Task> queue = new ArrayDeque<>();
queue.offer(task1);
queue.offer(task2);
Task t = queue.poll();      // task1 (FIFO)

함정

1. null 비허용

Deque<String> dq = new ArrayDeque<>();
dq.add(null);    // NullPointerException

이유: poll/peek 이 null 을 “비어 있음” 신호로 쓰는 의미와 충돌.

2. thread-safe 가 아님

ConcurrentLinkedDeque 또는 LinkedBlockingDeque 사용.

3. iterator 는 fail-fast iterator

순회 중 수정 시 CME.

참고

• Object
• Iterable
• Collection
• Queue
• Deque
• LinkedList
• ConcurrentLinkedDeque
• fail-fast iterator