Python의 List는 링크드 리스트가 아닌 고정된 사이즈를 갖는다.
매번 요소가 추가될 때마다 정해진 크기가 벗어나면 크기를 증가시키는 방식이다.
>>> import sys
>>> sys.getsizeof([1, 2, 3])
88
>>> sys.getsizeof([1, 2, 3, 4])
88
>>> sys.getsizeof([1, 2, 3, 4, 5])
104이러한 방식이기에 리스트의 마지막 요소를 삭제하는데 드는 시간 복잡도는 O(1)이지만 첫번째 요소를 삭제하는데 드는 시간 복잡도는 O(N)이다. 첫번째 요소를 삭제하는 경우 그 뒤에 있는 모든 요소들을 하나씩 앞으로 업데이트하기 때문이다.
하지만 deque의 경우 doubly linked list를 사용하여 모든 요소 삭제에 대한 시간복잡도가 O(1)을 갖는다.
즉, 리스트의 시작과 끝 부분에 변경이 빈번하다면 deque를 사용하는 것이 더 좋은 성능을 갖는다.
리스트
Deque
