Respuesta.

Historia del tema

Las listas (list) son uno de los tipos de datos integrados básicos en Python desde las primeras versiones del lenguaje. Con el tiempo, su estructura interna ha mejorado, en particular, para aumentar el rendimiento y la comodidad de programación.

Problema

Es importante entender que las listas en Python no se implementan como listas enlazadas, sino como arreglos dinámicos. Esta idea errónea puede llevar a un código ineficiente o a un cálculo incorrecto de la complejidad de las operaciones.

Solución

Las listas se implementan como arreglos dinámicos que aumentan su tamaño de memoria asignada "bruscamente" (expandíéndose) cuando es necesario, para evitar costos constantes al agregar elementos. Esto permite insertar y eliminar elementos al final de la lista en un tiempo amortizado de O(1). La inserción o eliminación en el medio/principio requiere mover elementos, lo que toma O(n) tiempo.

Ejemplo de código:

my_list = [1, 2, 3]
my_list.append(4)      # Adición al final
my_list.insert(1, 'a') # Inserción por índice
print(my_list)

Características clave:

Cambio de tamaño dinámico sin que el usuario tenga que asignar/liberar memoria explícitamente.
La inserción y eliminación desde el final son operaciones rápidas, desde el principio/medio son lentas.
La lista puede contener elementos de cualquier tipo (heterogeneidad).

Preguntas capciosas.

¿Se puede considerar list en Python como análogo de un arreglo en C? ¿Cuál es la diferencia?

No, un arreglo en C contiene elementos de tipo fijo, ubicados de manera consecutiva en la memoria. La lista de Python es un arreglo de punteros a objetos, cada uno de los cuales apunta a un objeto independiente de tipo arbitrario en el heap.

¿Qué pasará si se insertan elementos al principio de la lista en un bucle? ¿Es rápido?

No, es lento: al insertar al principio (posición 0) se desplazan todos los elementos existentes a la derecha cada vez. La complejidad amortizada es O(n) por operación, lo que puede llevar a una degradación del rendimiento para listas grandes.

¿Cuál es la diferencia entre los operadores + y append/extend para listas?

crea una nueva lista sin cambiar las antiguas. append añade un elemento al final de la lista original. extend añade todos los elementos de otra secuencia a la lista, modificando el propio objeto.

lst1 = [1, 2]
lst2 = [3, 4]
lst3 = lst1 + lst2     # lst3 es una nueva lista
lst1.append(lst2)      # lst1 se convierte en [1, 2, [3, 4]]
lst1.extend(lst2)      # lst1 se convierte en [1, 2, 3, 4], si lst1 no se reinicia después de la anterior append

Errores comunes y anti-patrones

Uso de list para inserciones/eliminaciones frecuentes desde el principio (es mejor usar collections.deque)
Expectativa errónea de que list ocupa poca memoria y contiene datos "compactos", como los arreglos de C/Java
Involuntaria inserción de la lista dentro de sí misma (append de la lista en la misma lista)

Ejemplo de la vida real

Caso negativo

En un proyecto se utilizó una lista para almacenar y eliminar constantemente los primeros elementos. Se notó una desaceleración notable con grandes volúmenes de datos.

Pros:

Fácil de comenzar, muchos métodos integrados.

Contras:

El rendimiento se degradó, errores de memoria con grandes volúmenes.

Caso positivo

Después de identificar el problema, reemplazamos la lista por collections.deque, que está optimizado para tales operaciones.