Как Python осуществляет поиск элементов в списке со сложностью O(1)?

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

Элементы этого списка имеют разные размеры в памяти, поэтому нельзя получить доступ к li[3], просто добавив к li[0] размер, трижды превышающий размер каждого элемента. Как интерпретатор понимает, что для доступа к li[3] не нужно проходиться по списку?

Списки в Python реализованы как массивы указателей. Вот что на самом деле происходит, когда вы создаете список:

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

Вы создаете массив указателей на объекты PyObject (объекты Python на уровне C):

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

Каждый указатель «адресовывает» к соответствующим объектам в памяти, поэтому строка «perry» будет сохранена по адресу 0xa3d25342, а элемент с индексом 1 будет сохранен в 0x635423fa и т. д.

Поскольку все указатели имеют одинаковый размер, интерпретатор, чтобы перейти к указателю, хранящемуся в li[3], может просто добавить к li[0] трехкратный размер li[0].