[Java] ConcurrentLinkedDeque

ConcurrentLinkedDeque, java.util.concurrent.ConcurrentLinkedDeque, CLD, lock-free deque

정의

java.util.concurrent.ConcurrentLinkedDeque<E> 는 lock-free Deque. ConcurrentLinkedQueue 의 양방향 버전. JDK 1.7 추가.

양 끝 모두에서 add/remove 가능, 모든 연산이 CAS 기반.

내부 구조

이중 연결 리스트 (prev, next 모두 volatile) 를 lock-free 알고리즘으로 관리. ConcurrentLinkedQueue 의 단방향보다 복잡하다.

복잡도

작업	시간	동시성
addFirst, addLast, offerFirst, offerLast	amortized O(1)	lock-free
pollFirst, pollLast, removeFirst, removeLast	amortized O(1)	lock-free
peekFirst, peekLast	O(1)	volatile read
size	O(n), 부정확	약함

사용 사례

• 양 끝에서 동시 작업이 일어나는 큐 (예: 일부 work-stealing 패턴)
• stack + queue 혼용 동시성

ConcurrentLinkedQueue 와의 선택

대부분의 경우 ConcurrentLinkedQueue 가 충분. 양쪽 끝 연산이 모두 필요할 때만 Deque 선택.

시나리오	권장
FIFO 만	ConcurrentLinkedQueue
양 끝 add/remove	ConcurrentLinkedDeque
Producer-Consumer (blocking)	BlockingQueue 구현체

참고

• Object
• Iterable
• Collection
• Queue
• Deque
• ConcurrentLinkedQueue
• BlockingQueue