Programming Languages/Python

파이썬의 deque : 사용법과 장점, 그리고 list 와의 비교

1. list VS. deque 자료구조의 큐(queue) 특징 선입선출(FIFO) 단방향 파이썬의 list fixed size memory blocks(array) 링크드 리스트 (X), 고정된 사이즈의 메모리를 갖는 array (O) 따라서, 마지막 원소를 삭제하는 연산은 O(1)의 시간복잡도를 갖지만 첫번째 원소 삭제 시 O(n)의 시간복잡도를 가진다 * 첫번째 원소를 삭제하면 삭제 후 남은 모든 원소를 앞으로 이동시키기 때문 파이썬의 deque 양방향 큐 (deque: double-ended queue의 줄임말) double-linked list로 구현되어 있다 큐의 앞, 뒤 양쪽 방향에서 element를 추가하거나 제거할 수 있다 그러므로 맨 앞의 element를 삭제해도 시간복잡도는 O(1)이..