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

Question

Acabo de aprender Python. Leyendo los tutoriales oficiales. Me encontré con esto:

Mientras APPENDs y pops desde el final de la lista son rápidos, haciendo inserciones o las paletas desde el principio de una lista es lento (debido a que todos los demás elementos tienen que ser cambiado por uno).

Hubiera supuesto que un lenguaje maduro como Python tendría todo tipo de optimizaciones, entonces ¿por qué Python no parece usar listas enlazadas para que las inserciones puedan ser rápidas?

Answer 1

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

Answer 2

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

Answer 3

list se implementa como una lista de arrays. Si desea insertar con frecuencia, puede usar un deque (pero tenga en cuenta que el recorrido al medio es caro).

Como alternativa, puede usar un montón. Está todo allí si te tomas el tiempo de mirar los documentos.

Answer 4

Lo que Python llama "listas" no son realmente listas vinculadas; son más como matrices. Vea list entry from the Python glossary y también How do you make an array in Python? de Python FAQ.

Answer 5

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

Ver How are lists implemented?

Como usted ha mencionado, esta aplicación hace que las inserciones en el comienzo o la mitad de una lista de Python lenta porque cada elemento de la matriz a la derecha del punto de inserción tiene que ser cambiado a lo largo de un elemento. Además, algunas veces la matriz tendrá que cambiar su tamaño para acomodar más elementos. Para insertar en una lista vinculada, aún necesitará O (n) tiempo para encontrar la ubicación donde va a insertar, pero la inserción real será O (1), ya que solo necesita cambiar las referencias en los nodos inmediatamente. antes y después de su punto de inserción (suponiendo una lista doblemente vinculada).

Por lo tanto, la decisión de hacer que las listas de Python usen matrices dinámicas en lugar de listas vinculadas no tiene nada que ver con la "madurez" de la implementación del idioma. Simplemente hay intercambios entre diferentes estructuras de datos y los diseñadores de Python decidieron que los arreglos dinámicos 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, por lo que las matrices dinámicas son una mejor opción en este caso.

Consulte la tabla siguiente en el artículo matriz Wikipedia dinámico para una comparación de diversas características de rendimiento de estructura de datos:

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