Python list append 연산

• python list 자료구조에서 시간 복잡도 O(1) 연산
  a[i] -> O(1)
  a.append(element) -> O(1)
  a.pop() -> O(1)
• python의 list 자료구조는 배열처럼 구현되어있음 (C++ vector와 비슷) -> python의 list들의 element들을 메모리 상의 연속적인 위치에 배치되며, 때문에 인덱스를 사용하여 접근이 가능함
• append같이 list의 크기가 달라지는 경우 (할당된 크기를 넘기면),
  fragmetation에 걸리지만 않으면 O(1)인듯
  
• 근데 궁금한게 공식 문서에도 append 연산이 O(1)의 시간복잡도를 갖는다고 적혀있는데 메모리 공간 뒤에 다른 data가 있으면 결국엔 다 복사해줘야하니까 worst case에는 O(n)만큼 걸리는게 아닌가싶음

reference: https://github.com/zpoint/CPython-Internals/blob/master/BasicObject/list/list.md