Saturday, March 2, 2019
Python lists are arrays but they use dynamic growth to have a constant insertion amortized time. This post shows how it's done.Lately I’ve been reviewing some algorithms and some data structures. A python list is basically a dynamic array that allows to read and append at constant time. An array has constant read time O(1) but linear O(n) write time as everytime you need to add a new element a new array needs to be allocated in memory and copied to the new location. Python list has a constant insertion time.