Deque vs list 속도 차이

1. Deque

 Deque는 Double-ended Queue 입니다. 

이는 양 끝에 삽입/삭제를 지원한다는 것입니다. 양 끝에 삽입/삭제 시 O(1)의 시간복잡도를 만족하게 됩니다.

 내부적으로는 double-linked list로 구현되어 있습니다.

• append() : deque의 right end에 요소 추가
• appendleft() :  deque의 lef end에 요소 추가
• pop() : deque의 right end의 요소 삭제
• popleft() : deque의 left end의 요소 삭제

 

2. List

 Deque와는 다르게 python의 List는 fixed size memory blocks(array)로 구현되어 있습니다.

이름은 List여서 링크드 리스트처럼 보이지만 고정된 사이즈의 메모리를 갖는 array 형태입니다.

 

 List의 마지막 원소를 삭제는 O(1)이지만, 그림처럼 첫번째 원소를 삭제하면 삭제 후 모든 원소를 앞으로 이동시키기 때문에 시간 복잡도가 O(n)입니다. 자료구조 뒤에서 추가/삭제는 덱과 리스트는 속도 차이가 없지만, 첫번째 원소를 추가 삭제한다면 극명한 속도 차이가 발생합니다.

 삽입, 삭제의 operation()이 앞, 뒤, 중간 등에서 발생한다면 list 보다는 deque 사용을 우선적으로 고려하는 것이 속도 측면에서는 훨씬 좋을 것입니다.

 

 

 

 

 

출처

https://wellsw.tistory.com/122

[파이썬] 덱 vs 리스트 속도 차이? (deque vs list speed 차이)