Python Sequence Classes

• python은 list/tuple/str이 built in 되어 있음
  

Compact Arrays

Not Compact Array

Insertion

add(i, o)

• i = n 일 경우가 best case
• i = 0 일 경우 worst case
  : 이 경우 O(n)
  

Element Reemoval

• best case
  : i = n
• worst case
  : i = 0
  : O(n) times
  

Performance

Growable Array-based Array List

Doubling Strategy Analysis

Python Implementation