collections.deque - 데크

[triger99]

데크의 popleft()가 list의 pop(0) 처럼 O(N)이 아닌 O(1)인 이유

[DockerIsFish]

LIST의 pop()는 O(1)이지만, pop(0)처럼 첫번째 원소를 삭제하면 삭제 후 모든 원소를 앞으로 이동시키기 때문에 시간 복잡도가 O(n)입니다.

하지만 dequeu 의 popleft()의 시간복잡도는 O(1)입니다. 그 이유는 내부적으로 deque은 double-linked list로 구현되어 있습니다. 그래서 양 끝의 요소의 추가/삭제가 O(1)을 만족하게됩니다.

double-linked list는 블럭을 앞 뒤로 잇는 leftlink와 rightlink가 블록 구조체에 정의되어 있습니다.

이러한 블록이 모여서 dequeobject를 만들며, dequeobject는 전체 오브젝트의 양 끝을 leftindex, rightindex에 따로 저장하고 있습니다.

deque.popleft() 연산 시, 첫번째 블록을 끊어버리고, 연결 노드 인덱스만 갱신하면 되기 때문에 dequeue 연산이 O(1) 만에 가능한 것이다.

출처 : https://velog.io/@bae12/Python-dequeue-%EC%97%B0%EC%82%B0%EC%9D%98-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84-%EB%B9%84%EA%B5%90-list-vs-collections.deque