파이썬 collections의 deque를 사용하는 이유(feat. time complexity)

deque의 사용성에 대해 고민하게 된 계기

탐색 알고리즘 BFS를 구현하면서, 아래와 같이 deque 를 사용하게 되었다.

from collections import deque

deque는 큐 자료구조를 구현해 준다. popleft()를 사용하여 큐에 가장 먼저 들어간 데이터를 가장 먼저 나오게 해준다.
그런데, 이때 한가지 궁굼증이 생겼다.

우선, 둘의 기능이 완전히 같다.

[List의 pop(0)을 사용한 방법]

arr = [1, 2, 3, 4]

print(arr.pop(0))

[deque의 popleft()를 사용한 방법]

from collections import deque

arr = deque([1, 2, 3, 4])
print(arr.popleft())

두 가지 방법으로 arr배열의 가장 첫번째 데이터를 출력했다.
결과는 두 방법모두 "1"이 출력된다.

deque의 popleft()는 기존에 사용하던 list의 pop(0)과 뭐가 다른거지?

 

time complexity의 차이

우선, deque는 list와 dictionary와 거의 동일하게 생각하면 된다.

다만, 차이는 popleft()의 시간복잡도 차이이다.

list의 경우 pop()으로 마지막 값을 꺼내는 경우 O(1) [일정한 시간]이 걸린다. 
deque의 popleft()와 같은 기능을 하는 pop(0)은 어떨까?

pop(0)으로 가장 앞에있는 인덱스의 데이터를 꺼낼 때는 list 크기에 따라 읽어오는 시간이 달라진다 즉 O(N)의 시간이 걸린다.

하지만 deque를 사용할 경우 popleft()를 사용하면 리스트의 pop(0)과 같은 기능을 수행하면서도 걸리는 시간은 O(1)이 걸린다. 즉, index의 값으로 바로 값을 찾는다.

간단하게 정리하면, 아래의 표와 같다.

구현 방법	기능	시간 복잡도
pop()	배열의  마지막 데이터 꺼내기	O(1)
pop(0)	배열의 첫번째 데이터 꺼내기	O(N)
deque의 popleft()	배열의 첫번째 데이터 꺼내기	O(1)

deuqe/popleft()