How come list element lookup is O(1) in Python?

by

A list in Python is implemented as an array of pointers1. So, what’s really happening when you create the list:

["perry", 1, 23.5, "s"]

is that you are actually creating an array of pointers like so:

[0xa3d25342, 0x635423fa, 0xff243546, 0x2545fade]

Each pointer “points” to the respective objects in memory, so that the string "perry" will be stored at address 0xa3d25342 and the number 1 will be stored at 0x635423fa, etc.

Since all pointers are the same size, the interpreter can in fact add 3 times the size of an element to the address of li[0] to get to the pointer stored at li[3].

1 Get more details from: the horse’s mouth (CPython source code on GitHub).

Leave a Comment