Lista circular - Python Ejemplo
En post anteriores las listas enlazadas permiten almacenar valores de manera dinamica y de una forma ordenada.
Los usos de las listas enlazadas son mucho mas generales con respecto a la variante que usaremos hoy, estamos hablando de las listas circulares, estas tienen la peculiaridad de que cuando llegamos a su final al llamar el metodo next podemos volver a encontrar el mismo elemento inicial.
Nodo
El nodo esta compuesto de 3 atributos, data, next y prev donde data es elemento que guardara el nodo, next es el nodo siguiente y prev es el nodo anterior. Adjuntamos el codigo del nodo
Metodo append
El metodo agregar funciona de la siguiente manera:
Primer paso crear un nuevo nodo y agregar el nodo cabeza a una varibale temporal
Si el nodo cabeza es nulo, entonces el nuevo nodo se asigna a head y tambien a next y prev.
Si no es nulo, la lista se recorre de forma de forma contrara conviertiendo el nodo temporal en el prev de temp, y asignando a siguente el nuevo nodo, a prev el nodo temporal y a siguente head
Complejidad
La complegidad de esta lista cirular como podemos ver en el caso de la insercion es de O(1).
Recuerda que puedes colaborar en el repositorio para agregarle funcionalidades nuevas, tambien puedes descargar el repo y utilizarlas en tu proyecto
El archivo utilizado en esta entrada lo puedes encontrar aqui.