deque와 list 차이

deque(double-ended queue)는 양쪽 끝에 원소를 추가하거나 삭제할 수 있음.

list는 마지막 원소를 추가 삭제하는 것을 기본으로 함.

 

deque(double-ended queue)

append, appendleft, pop, popleft를 사용하여 양쪽 끝에서 추가/삭제하므로 시간복잡도 : O(1)

 

list

마지막 끝에서 추가/삭제함을 기본으로 할 때 : O(1)

앞쪽에서 추가/삭제하거나 중간에서 추가/삭제 할 때 동적 배열을 원칙으로 하므로 시간 복잡도: O(n)

 

양쪽에서 삽입/삭제, 큐(FIFO), 데큐(FIFO), 스택 구현에는 deque가 유리함. 

• 큐, 데큐처럼 사용하고 싶으면 popleft, appendleft로 FIFO 구현 가능.
• 스택처럼 사용할 경우 pop, append 사용하여 구현가능.

임의의 위치에 있는 요소를 조회할 때는 list가 유리함. -> list[i]