Summary

• All of the Objects used in Python are defined as PyObject extension.
• We can treat List in Python basically the same as C lang’s.
  • Access to an element in a List in Python takes O(1) time complexity, which is the same as C lang’s random access to an array.
  • Access to elements in a List using slice in Python takes O(k) time complexity (k means the slice’s length) because it is implemented as new memory allocation and copy elements using for loop.
  • list.pop(x) takes O(n) time complexity (len(list) is n) because the elements that have bigger indices than x have to be moved to the previous array.

References

• Pythonのlist型の実装を読んでみる - 今日も窓辺でプログラム