deque는 어떻게 빠른가

알고리즘 문제를 풀다보면 흔히 list보다 deque(double ended queue)가 훨씬 빠르다고 한다.

deque의 popleft()는 배열의 첫번째 데이터를 꺼내는 것으로 O(1)의 시간복잡도가 걸린다.

그 이유가 무엇인지 궁금하여 찾아보았다.

 

deque는 원형 큐를 확장하여 손쉽게 구현할 수 있다. 다음과 같이 초기화 가능하다.

class Deque:
    rear = 0
    front = 0
    MAX_SIZE = 100
    deq = list()
    
    def __init__(self):
    	self.rear = 0
        self.front = 0
        self.deq = [0 for i in range(self.MAXSIZE)]

 

이렇게 rear, front 변수를 활용하여 linkedlist와 비슷한 방식으로 삽입, 삭제시에 포인터 조정이 일어난다.

그래서 deque.popleft() 는 front += 1 형태의 연산만 수행하므로 O(1)의 시간복잡도가 가능한 것이다.

list.pop() 과 deque.pop()의 경우

맨 뒤의 값을 제거하는 것으로 수행시간에 큰 차이가 없어 stack으로 사용할 때는 list나 deque나 성능이 같다.

다만, queue가 필요할 때에는 deque로 개발하면 되겠다.

 

 

참고: https://codingsmu.tistory.com/124

파이썬으로 구현하는 덱(Deque)