파이썬 deque vs list 성능차이

deque의 appendleft(), popleft() 함수 vs List의 insert() 함수

=> O(1) vs O(n) deque 이 성능이 훨 좋다

이유

덱은 더블 링크드 리스트로 되어있어. 양 끝에 요소를 추가/삭제 가능.

• 그래서 O(1) 로 끝.

반면 리스트의 경우

파이썬의 리스트는 고정 메모리 사이즈 를 갖고있어

• 마지막 원소 삭제는 O(1) 로 빠르지만, 첫번째 원소를 삭제하려면... O(n) 이나 걸려