Data structures: Python lists
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.