¿Python usa listas enlazadas para listas? ¿Por qué la inserción es lenta?

Sólo estoy aprendiendo Python. Leyendo los tutoriales oficiales. Me encontré con esto:

Si bien los apéndices y los elementos emergentes del final de la lista son rápidos, hacer inserciones o elementos emergentes desde el principio de una lista es lento (porque todos los demás elementos deben desplazarse en uno).

Habría adivinado que un lenguaje maduro como Python tendría todo tipo de optimizaciones, ¿por qué Python no parece usar listas enlazadas para que las inserciones sean más rápidas?

Python utiliza un diseño de lista lineal en la memoria para que la indexación sea ​​rápida (O (1)).

Como Greg Hewgill ya ha señalado, las listas de python utilizan bloques de memoria contiguos para hacer que la indexación sea más rápida. Puede usar un deque si desea las características de rendimiento de una lista enlazada. Pero tu premisa inicial me parece defectuosa. La inserción indexada en medio de una lista enlazada (estándar) también es lenta.

Lo que Python llama “listas” no son realmente listas enlazadas; Son más como matrices. Consulte la entrada de la lista del glosario de Python y también ¿Cómo se crea una matriz en Python? de las preguntas frecuentes de Python.

list se implementa como un arraylist. Si desea insertar con frecuencia, puede usar un deque (pero tenga en cuenta que recorrer el medio es costoso).

Alternativamente, puede utilizar un montón. Todo está ahí si te tomas el tiempo de mirar los documentos.

Las listas de Python se implementan utilizando una serie de referencias a otros objetos. Esto proporciona una búsqueda O (1) en comparación con una búsqueda O (n) para una implementación de lista vinculada.

Ver ¿Cómo se implementan las listas?

Como mencionó, esta implementación hace que las inserciones en el principio o en la mitad de una lista de Python sean lentas porque cada elemento de la matriz a la derecha del punto de inserción debe desplazarse sobre un elemento. Además, a veces la matriz tendrá que redimensionarse para acomodar más elementos. Para insertarlo en una lista vinculada, aún necesitará O (n) tiempo para encontrar la ubicación donde insertará, pero la inserción real será O (1), ya que solo necesita cambiar las referencias en los nodos de inmediato. antes y después de su punto de inserción (suponiendo una lista con doble enlace).

Por lo tanto, la decisión de hacer que las listas de Python utilicen matrices dinámicas en lugar de listas vinculadas no tiene nada que ver con la “madurez” de la implementación del lenguaje. Simplemente hay compensaciones entre diferentes estructuras de datos y los diseñadores de Python decidieron que los arreglos dynamics eran la mejor opción en general. Es posible que hayan asumido que indexar una lista es más común que insertar datos en ella, lo que hace que las matrices dinámicas sean una mejor opción en este caso.

Consulte la siguiente tabla en el artículo de wikipedia de Dynamic Array para una comparación de varias características de rendimiento de la estructura de datos:

https://en.wikipedia.org/wiki/Dynamic_array#Performance