No, no es barato. Quitar un elemento del frente de la lista (usando list.pop(0) , por ejemplo) es una operación O(N) y debe evitarse . De manera similar, insertar elementos al principio (usando list.insert(0, <value>) ) es igualmente ineficiente.

Esto se debe a que, después de cambiar el tamaño de la lista, sus elementos deben cambiarse. Para CPython, en el caso de l.pop(0) , esto se hace con memmove mientras que para l.insert(0, <value>) , el cambio se implementa con un ciclo a través de los elementos almacenados .

Las listas están diseñadas para un acceso aleatorio rápido y operaciones O(1) en su extremo .

Sin embargo, dado que está realizando esta operación comúnmente, debería considerar usar un deque del módulo de collections (como sugirió @ayhan en un comentario). Los documentos en deque también resaltan cómo los objetos de list no son adecuados para estas operaciones:

Aunque los objetos de lista admiten operaciones similares, están optimizados para operaciones rápidas de longitud fija e incurren en costos de movimiento de memoria O(n) para operaciones pop(0) e insert(0, v) que cambian tanto el tamaño como la posición de la representación de datos subyacente. .

^{(Énfasis mío)}

La estructura de datos deque ofrece complejidad O(1) para ambos lados (principio y final) con appendleft / popleft y append / pop para el principio y el final respectivamente.

Por supuesto, con tamaños pequeños, esto genera algunos requisitos de espacio adicionales (debido a la estructura del deque ) que generalmente no deberían ser motivo de preocupación (y, como señaló @juanpa en un comentario, no siempre se cumple) como los tamaños de las listas crecer. Finalmente, como señala el comentario perspicaz de @ShadowRanger, con tamaños de secuencia realmente pequeños, el problema de hacer estallar o insertar desde el frente se trivializa hasta el punto de que realmente no preocupa.

Entonces, en resumen, para listas con muchos elementos, use deque si necesita agregar/abrir rápidamente desde ambos lados, de lo contrario, si está accediendo aleatoriamente y agregando al final, use list s.

Eliminar elementos del frente de una lista en Python es O(n), mientras que eliminar elementos de los extremos de una colección.deque es solo O(1). Como resultado, una deque sería excelente para su propósito, sin embargo, debe tenerse en cuenta que acceder o agregar/eliminar desde el medio de una deque es más costoso que para una lista.

El costo O(n) para la eliminación se debe a que una lista en CPython simplemente se implementa como una matriz de punteros, por lo que su intuición con respecto al costo de cambio para cada elemento es correcta.

Esto se puede ver en la página Python TimeComplexity en Wiki.