En este post te mostraré una lista ligada en Python que después se podría modificar como una cola o pila (ya que se pueden insertar elementos al inicio y al final).
Las operaciones que manejaremos con esta lista enlazada son:
- Agregar al inicio
- Agregar al final
- Saber si elemento existe
- Eliminar un elemento
- Obtener cabeza
- Obtener cola
- Recorrer lista
Por cierto, vamos a usar ciclos y no recursión para las operaciones. De esta manera el código queda más simple.
El nodo de la lista
La lista se compone de nodos o elementos que van enlazados entre sí. Cada nodo tiene dos cosas: el dato que guarda y un apuntador al nodo siguiente, del mismo tipo.
Python es un lenguaje bonito (no como C en donde tienes que solicitar memoria hasta para respirar) así que podemos guardar cualquier tipo de dato en los nodos, no importa si son cadenas, listas, objetos, números, etcétera.
Digamos que el dato será de tipo genérico.
Agregar elemento al final
Veamos cómo agregar un nodo al final de la lista enlazada usando Python. Lo que hacemos es recorrer la lista hasta el final y asignarlo ahí:
Por cierto, si el nodo es None (eso sería cuando la lista está vacía) entonces el nuevo nodo será la cabeza de la lista (ya que sería el primero en la lista).
Añadir elemento al inicio de la lista enlazada
Ahora veamos la operación de agregar un elemento a la lista pero al inicio. En este caso solo debemos crear un nuevo nodo (que será la nueva cabeza o nuevo inicio) y hacer que su siguiente sea el que antes era el inicio:
Ten en cuenta que en ambas funciones que agregan un nodo a la lista (estructura de datos) de Python regresan un nodo que será el apuntador al inicio o cabeza de la lista.
Obtener inicio y final de cola/pila
Otra operación interesante con esta lista ligada de Python es la de obtener la cabeza o inicio, y el final o la cola. En este caso solo recorremos y regresamos el nodo.
Obviamente para el caso de la cabeza simplemente regresamos el nodo que nos envían como argumento, ya que es el inicio de la lista.
Saber si elemento existe
Para saber si un elemento existe dentro de la lista enlazada que estamos creando basta recorrer toda la lista y comparar el dato de cada nodo con la búsqueda.
Si encontramos un dato de un nodo que coincida con la búsqueda entonces regresamos True.
En caso de terminar de recorrer la lista y no haber encontrado nada, regresamos False.
Nota: esto puede funcionar con objetos de cualquier tipo (incluso instancias de tus propias clases), solo debes implementar el método __eq__.
Eliminar elemento de lista enlazada con Python
Ahora veamos la operación en donde eliminamos un elemento. En este caso lo que hago es ir comparando el siguiente nodo del nodo actual, ya que no puedo ir hacia atrás en caso de que el elemento actual sea el que quiero eliminar.
Lo que hago cuando encuentro el elemento a eliminar es hacer que su elemento anterior apunte a su elemento siguiente.
Nota: igual y se podría hacer algo con el operador del de Python (así como lo hicimos en C++), pero supongo que el recolector de basura se encarga de liberar la memoria porque ya nadie tiene una referencia a ese nodo.
Poniendo todo junto
A continuación muestro un ejemplo en donde usamos las funciones expuestas y trabajamos con la lista enlazada.
Ten en cuenta que en este caso he usado cadenas pero puede usarse cualquier tipo de dato e incluso objetos.
Por cierto, he dejado todas las funciones globales y sin pertenecer a una clase en común.
Esto es porque he hecho el ejemplo rápidamente y no pensé en hacerlo una clase desde un inicio. Incluso así, sería muy fácil agruparlo en una clase por ti mismo.
Para terminar te dejo con más tutoriales de Python y Estructura de datos en mi blog.
Bonus
Mientras grababa el vídeo explicativo hice un ejemplo con una clase para demostrar que se pueden usar objetos como datos de los nodos. Aquí el código:
