Como crear una lista doblemente enlazada, y usarla para tus aplicaciones en Python
En nuestro artículo anterior mostramos como realizar una lista enlazada simple y este articulo será bastante similar a ese, te recomendamos pasar por ese artículo si eres nuevo en las estructuras de datos, manos a la obra.
Lista doblemente enlazada
Como su nombre lo indica la lista doblemente enlazada permite los nodos tengan referencias, al nodo siguiente y al nodo anterior facilitando algunas operaciones en los distintos marcos de aplicación.
Nodo de la lista enlazada doble
Para poder hacer el nodo de la lista tenemos que tener en cuenta distintas cosas una de ellas es que ahora en vez de tener una sola referencia tenemos 2 referencias una es a un nodo siguiente que seria el próximo en la lista y otra al nodo anterior. Para tener en cuenta, el primer nodo solo tendrá referencia al nodo siguiente ya que al ser el primer nodo no existe una referencia a un nodo anterior, al igual que el ultimo nodo este solamente tendrá al anterior.
Proceso para Insertar en la lista
Para crear el método append o insert en la lista seguiremos el siguiente algoritmo.
- Verificar si ya existen nodos en la lista o la lista esta vacía
- Si la lista esta vacía insertamos el primer nodo
- Si la lista no está vacía buscamos el ultimo nodo, le asignamos como referencia next el nuevo nodo y al nuevo nodo le asignamos como anterior el que antes era el último nodo
- Asignamos como último nodo el nuevo nodo.
Listo así de simple es el proceso de insertar un nuevo nodo pero vamos al código.
Codigo de ejemplo Nodo y Lista enlazada doble
Complejidad
La complegidad de esta lista enlazada doble como podemos ver en el caso de la insercion es de O(1).
Para el caso de la búsqueda en el peor caso es de O(n)
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.
