deque(collection)

Deques support thread-safe, memory efficient appends and pops from either side of the deque with approximately the same O(1) performance in either direction.

Though list objects support similar operations, they are optimized for fast fixed-length operations and incur O(n) memory movement costs for pop(0) and insert(0, v) operations which change both the size and position of the underlying data representation.

 

간단히 말해서 Deque는 스레드 세이프하고, 양 끝의 데이터를 꺼내거나 추가할 때 거의 상수 시간의 복잡도를 같는 자료구조를 말한다. 내부적으로 doubly linked list를 사용해서 만든다고 한다.

list 자료구조는 고정된 길이일 때 최적의 효율을 나타내는 반면, 가장 처음의 요소를 꺼내거나 중간 인덱스에 요소를 추가하게 되면 내부적으로 데이터 표현의 사이즈나 위치가 변경되기 때문에 최악의 경우 O(n)의 시간이 걸린다.

또한 deque는 중간에 접근을 할 때는 매우 느리다.