list.pop(0), deque.popleft() 무엇이 다를까?
pop(0)과 popleft()의 차이는 시간이다.
list: 고정된 사이즈의 메모리를 갖는 array로, 삽입 순서대로 저장된다.deque(double-ended queue): 큐의 앞뒤에서 모두 삭입/삭제가 가능하다.
-
리스트의 마지막 원소 삭제의 시간복잡도는
O(1)이지만, 특정 인덱스의 원소를 삭제하기 위해서는 그 원소 뒤의 모든 원소들을 한 칸씩 옮겨야하기 때문에 시간복잡도는O(n)이다.
-
덱의
popleft()는 front += 1 의 형태의 연산만을 수행하기 때문에O(1)의 빠른 복잡도로 원소 삭제가 가능하다.
그럼 무조건 deque를 쓰는 것이 좋겠구나!
queue 용도로 사용할 때는 그렇다.
stack 등 다른 용도로 사용하는 경우에는 list와 deque의 수행시간에는 차이가 없다. 오히려 deque는 list처럼 인덱스를 통한 접근이 불가능하기 때문에 중간에 있는 값에 접근하려면 list를 사용하는 것이 훨씬 효율적이다.
