deque는 왜 사용하고 어떤 알고리즘과 시간 복잡도로 구현 되었는지 알아보자

deque는 왜 쓰는 걸까?

코딩 테스트 문제를 풀 때 마다 deque를 자주 사용한다.
주로 배열의 양방향으로 요소를 넣고 뺄 때 사용하는데 단순히 양방향으로 빼고 넣기 때문에 쓰는지 궁금해졌다.

deque란?

보통 큐(queue)는 선입선출(FIFO) 방식으로 작동한다. 반면, 양방향 큐가 있는데 그것이 바로 데크(deque)다.

즉, 앞, 뒤 양쪽 방향에서 엘리먼트(element)를 추가하거나 제거할 수 있다.

데크는 양 끝 엘리먼트의 append와 pop이 압도적으로 빠르다.

컨테이너(container)의 양끝 엘리먼트(element)에 접근하여 삽입 또는 제거를 할 경우, 일반적인 리스트(list)가 이러한 연산에 O(n)이 소요되는 데 반해, 데크(deque)는 O(1)로 접근 가능하다.
출처

deque는 어떻게 구현됐을까?

참고링크 -> deque의 구현 코드를 잘 설명해 놓았다.

참조링크를 요약해보면 파이썬의 deque는 cpython으로 작성 되었으며 이중 연결 리스트로 구현 되어있다.

deque의 시간 복잡도

출처

deque는 양끝의 요소에 append, pop 할 때 시간 복잡도가O(1)이며
인덱스로 조회할 시에는 O(N)이다.
파이썬 공식 문서에서는 인덱스로 조회할 경우 빠른 조회를 원하면 리스트를 사용하라고한다. 리스트의 인덱스 조회 시간복잡도는 O(1)이기 때문

정리

• deque는 앞 뒤 요소를 넣고 빼야하는 문제가 있을 때 시간복잡도를 줄이기 위해 사용하자
• 인덱스 조회의 속도가 중요할 땐 그냥 리스트를 사용하자