Python-033-Implementando la pila usando listas enlazadas-mejorando la complejidad del tiempo
En la pila anterior, la complejidad del tiempo del algoritmo bajo amortización es O (1), y la capa inferior es una lista de Python, que es una matriz dinámica. Es una matriz de longitud fija en la memoria y el tamaño no se puede cambiar, por lo que debemos cambiarla a una matriz más grande para guardar nuevos datos. Si bien es muy sencillo de implementar, no es perfecto.
En nuestros artículos anteriores, detallamos varias formas de utilizar listas enlazadas. Antes de implementar la lista enlazada, solo se declaraba el objeto nodo, pero al usar el programa debemos usar la lista enlazada como un todo y como un objeto, para que la encapsulación sea mejor.
Hoy no escribiré esta lista enlazada. Usamos la clase anidada definida en la clase de pila como objeto de nodo de la lista vinculada. Debido a que hay muchas operaciones para crear un nodo, usamos ranuras para declarar las dos variables miembro del nodo para reducir el uso de memoria y mejorar la eficiencia.
Una lista enlazada es una estructura de datos que se puede cambiar en cualquier momento. Podemos cambiar su estructura en cualquier momento.
La implementación es la siguiente:
La complejidad temporal de cada operación del método de la pila implementada esta vez es O (1) y no se requiere amortización. Esto contrasta con una pila implementada con una matriz.
Las listas vinculadas son más rápidas y mañana usaremos listas vinculadas para implementar las colas.