What You Should Know about the Python List

Photo by Giammarco Boscaro on Unsplash

I often use Python, but I really don’t care about the way how Python works internally. So today I focus on the Python list and explain inside the implementation of it. Python’s list.append and list.pop change the list size dynamically, which make them run fast in O(1) time. Please note that list.pop for the last item only takes constant time. In this post, I’ll show the reason why it has become possible.

We call the data structure like Python list the dynamic array and call normal array the static array. This post is structured as follows.

1. What is a dynamic array?
2. The way how dynamic array appends or pops an item
3. How to balance append and pop

I explain these based on MIT’ Table Doubling, Karp-Rabin lecture.

1. What is a dynamic array?

Dynamic array resizes its size when we append or pop an item. Of course, resizing isn’t always the case. Dynamic array adjusts the balance of append and expand, pop and shrink for efficient resizing.

Dynamic array generates a new array and copies items from an old array when an item fills up an old array. The figure below shows an example of expanding an array. I separate append and copy for easily understood. Both appending an item and copying…