[Time Complexity] Python - Deque vs List performance comparison (append, appendleft, pop, popleft)

[Time Complexity] Python - Deque vs List performance comparison (append, appendleft, pop, popleft)

[시간 복잡도] 파이썬 - Deque vs List 퍼포먼스 비교 (append, appendleft, pop, popleft)

code	n = 10000	n = 100000	n = 1000000	Time Complexity
list.append()	0.0010249615	0.0093748569	0.0974259377	O(1)
deque.append()	0.0012080669	0.0113868713	0.1131999493	O(1)
list.insert(0,0)	0.0436980724	4.2723989487	430.9322969913	O(n)
deque.appendleft()	0.0010690689	0.0137970448	0.1067051888	O(1)
list.pop()	0.0013749599	0.0134758949	0.1310129166	O(1)
deque.pop()	0.0009977818	0.0100331306	0.1004290581	O(1)
list.pop(0)	0.0262870789	3.5589528084	372.6231980324	O(n)
deque.popleft()	0.0009810925	0.0101020336	0.0985748768	O(1)

결론

1. append와 pop의 경우에는 List와 Deque 둘 다 Time Complexity가 O(n)으로 별차이가 없음

2. appendleft와 popleft의 경우에 Deque가 훨씬 빠름