In this article we’re going to go over common list mutation and query operations and their runtime complexity. Python lists are implemented as dynamic arrays, so the time complexity of list operations is equivalent to the time complexity of dynamic arrays.
Just as a refresher on the big O of a dynamic array data structure, here’s a table from wikipedia:
|Insert/delete at beginning||O(N)|
|Insert/delete at end||O(1) amortized|
|Insert/delete in middle||O(1)|
Given a list of integers stored in the variable
numbers, here’s are tables of the run time complexity of query and mutation actions. Query actions do not change the existing list, but mutations do.
Note: assume that all index values used in the examples are in range.
|Get element at index 5||
|Get subarray between index 2 and 7 (including 7)||
|Add 3 to the end of the list||
|Insert 3 to the beginning of the list||
|Insert 3 to the middle of the list||
|Pop the last element on the list||
|Pop an element from the middle of the list||
|Pop an element from the beginning of the list||
|Add a list of elements to the end of the list||
Why are inserts to the end of a list O(1)? Doesn’t python have to allocate a new list and copy all the existing lists over?
Good question! Python actually over-allocates in proportion tho the list size, which means that not all appends result in full list copies. Taking into account the over allocation, python claims to have a O(1) append runtime.tags: