Listas doble mente enlazadas con python

Para esta nueva entrega en CódigoFacilito me gustaría hablemos sobre una forma más sencilla de implementar las estrcuturas de datos pilas y colas. Y no, no te preocupes, no implementaremos nuestras propias estructuras y/o algoritmos, si no que haremos uso de las que Python ya nos ofrece. Recordemos que Python viene con baterias incluidas.

Será un post sumamente interesante, así que te invito a que te quedes.

Bien, ahora sí, son más por añadir, comencemos.

Listas como estructuras

Probablemente los primero que se nos viene a la mente la oir los conceptos de pilas y colas en Python es pensar que podemos implementar estas estructuras con objetos de tipo listas, ya que las listas nos ofrecen los métodos insert, append y pop, métodos que, respectivamente, nos permite insertar un elemento en un índice en particular, insertar un elemento al final de la colección o eliminar el último elemento de la coleccíón.

Recordemos que las pilas y colas funciona con el principio el último en entrar es el primero en salir para las pilas y el primero en llegar es el primero en salir para las colas.

Por lo tanto, para implementar, por ejemplo una pila nuestro código pudiera quedar de la siguiente manera.

pila = []

# Agregar elementos a la pila (push)
pila.append(10)
pila.append(20)
pila.append(30)

# Eliminar elementos de la pila (pop)
elemento = pila.pop()  # Elimina y retorna el último elemento agregado (30)
print(elemento)  # Output: 30

# Imprimir la pila actual
print(pila)  # Output: [10, 20]

Esto puede verse bien, y de hecho va funcionar, sin embargo si trabajamos con un gran número de datos, por ejemplo miles, cientos de miles o millones de registros, el perfomance comienza a decaer.

Tareas como insertar un nuevo elemento al principio de un colección de miles de registro es algo que ya computacionalmente hablando para python es costoso.

Veamos.

import timeit

def inser_elements():
    numbers = []

    for element in range(0, 100_000):
        numbers.insert(0, element)

if __name__ == '__main__':
    result = timeit.timeit(inser_elements, number=1)
    print(result)

Una tarea como insertar 100K registros le toma a Python poco más de 2 segundos. Algo que no esta del todo bien.

Deque

Por lo tanto, siempre que quieres realizar tareas que impleque insertar o eliminar elementos al princio final de la colección, por ejemplo cuando trabajar con pilas o colas, te recomiendo dejar a un lado las listas y usar deque.

Deque por su abreviación: double-ended queue, es una lista doble mente finalizada, esto quiere decir que acciones como añadir al principio o final de la colección, o así como eliminar elementos al principio o final de la colección, tiene una complejidad O1, el mejor performance que podemos obtener en la notación Big O.

Y lo mejor de todo es que deque ya se encuentra en la biblioteca estandar de Python así que no hay que instalar absolutamente nada simplemente importamos y listo

Veamos.

from collections import deque

mi_deque = deque()

mi_deque.append(10)
mi_deque.append(20)
mi_deque.append(30)

mi_deque.appendleft(5)

print(mi_deque[1]) 

mi_deque.pop()
mi_deque.popleft()

print(mi_deque) 

Importamos de collections y comenzamos a definir ya sea nuestro pila o cola.

Podemos añadir elementos al final de la colección con append, o añadir elementos al principio de la colección con appendleft.

Lo mismo con pop, para eliminar elementos de la derecha o popleft para eliminar elementos de la izquieda.

import timeit
from collections import deque

def inser_elements():
    numbers = deque()

    for element in range(0, 100_000):
        numbers.appendleft(element)

if __name__ == '__main__':
    result = timeit.timeit(inser_elements, number=1)
    print(result)

Siguiendo con nuestro ejemplo anterior, utilizando deque logramos reducir el tiempo de ejecución para insertar un 100l registros de 2.23 segundo a

0.01 Milisegundos

Definitivamente Deque es la mejor opción para realizar tareas que impliequen adir o modificar elementos al principio o final de la colección.

Ahora ya lo sabes, siempre que quieres implementar una pila o cola con Python definitivamente te recomiendo usar Deque.

y cuéntanos, ya conocías Deque, ya lo has utilizado en alguno de tus proyectos, déjanoslo saber en la sección de comentarios.