Hola de nuevo En previsión del inicio del curso para desarrolladores de Python, hemos preparado para usted un pequeño material de autor sobre listas vinculadas en Python.
Python es un lenguaje muy conveniente y multifacético, pero por defecto no tiene una estructura de datos como una lista vinculada o LinkedList. Hoy compartiré mis mejores prácticas sobre este tema y hablaré un poco sobre cuál es esta estructura de datos. Este artículo será de interés para aquellos que primero se encuentran con el tema de las listas vinculadas y quieren entender cómo funcionan desde un punto de vista algorítmico.
¿Qué es una LinkedList?
Una lista enlazada o lista enlazada es una estructura de datos. Una lista vinculada proporciona la capacidad de crear una cola bidireccional a partir de cualquier elemento. Cada elemento de dicha lista se considera un nodo. De hecho, un nodo tiene su valor, así como dos enlaces a los nodos anteriores y posteriores. Es decir, la lista está "vinculada" por nodos que ayudan a subir o bajar la lista. Debido a estas características estructurales, puede organizar una pila, una cola o una doble cola desde una lista vinculada.
Visualicemos definiciones secas. Ahora tenemos gatos que están sentados en cajas. Y en cada cuadro dice lo que está en orden y lo que debe representar.
Lo que haremos con una lista vinculada:- Compruebe si este o aquel elemento está contenido en él;
- Agregar nodos al final;
- Obtener el valor de un nodo por índice;
- Eliminar nodos.
De hecho, hay muchas más opciones para trabajar con ellos, pero nos detendremos en la implementación de estos pasos básicos. Habiendo entendido por qué principio están construidos, usted mismo puede implementar fácilmente sus propios métodos.
Tendrás que comenzar creando dos clases:
class Box: def __init__ (self,cat = None): self.cat = cat self.nextcat = None class LinkedList: def __init__(self): self.head = None
En el caso general, tenemos un nodo que tiene algún valor en su interior: un gato y un enlace al siguiente nodo. Es decir, en la clase Box, respectivamente, hay un gato y un enlace al siguiente cuadro. Como cualquier lista, el coherente también tiene un comienzo, es decir, la cabeza. Como inicialmente no hay nada allí, el elemento inicial se establece en Ninguno.
Es el ítem en la lista
Comencemos con uno simple. Para verificar si hay algún gato en particular en uno de los cuadros ubicados en serie, debe recorrer la lista completa, verificando el valor existente con los valores del elemento en la lista.
def contains (self, cat): lastbox = self.head while (lastbox): if cat == lastbox.cat: return True else: lastbox = lastbox.nextcat return False
Agregar nodo al final de la lista
Primero necesitas crear una nueva caja, y ya poner un nuevo gato en ella. Después de eso, debe verificar, comenzando desde el principio de la lista vinculada, si hay un enlace al siguiente en el nodo actual y si hay uno, luego vaya a él, de lo contrario, el nodo es el último, por lo que debe crear un enlace al siguiente nodo y poner el mismo cuadro nuevo en él, que creamos
def addToEnd(self, newcat): newbox = Box(newcat) if self.head is None: self.head = newbox return lastbox = self.head while (lastbox.nextcat): lastbox = lastbox.nextcat lastbox.nextcat = newbox
Obtener un nodo por índice
Mediante el índice catIndex queremos obtener un nodo de cuadro, pero como el índice no se proporciona para los nodos como tales, necesitamos encontrar algún tipo de reemplazo, es decir, una variable que actúe como índice. Esta variable es boxIndex. Revisamos toda la lista y verificamos el "número de serie" del nodo, y si coincide con el índice deseado, producimos el resultado.
def get(self, catIndex): lastbox = self.head boxIndex = 0 while boxIndex <= catIndex: if boxIndex == catIndex: return lastbox.cat boxIndex = boxIndex + 1 lastbox = lastbox.nextcat
Eliminar nodo
Aquí consideramos la eliminación de un elemento no por índice, sino por valor, para introducir al menos alguna variedad.
La búsqueda comienza desde el principio de la lista, es decir, desde el primer cuadro de una fila, y continúa hasta que se agoten los cuadros, es decir, hasta que el headcat se convierta en Ninguno. Verificamos si el valor almacenado en el nodo actual coincide con el que queremos eliminar. Si no, entonces seguimos adelante. Sin embargo, si coincide, lo eliminamos y "volvemos a vincular" los enlaces, es decir, eliminamos el cuadro N-ésimo, mientras que el cuadro N-1 ahora se refiere al cuadro N + 1.
def removeBox(self,rmcat): headcat = self.head if headcat is not None: if headcat.cat==rmcat: self.head = headcat.nextcat headcat = None return while headcat is not None: if headcat.cat==rmcat: break lastcat = headcat headcat = headcat.nextcat if headcat == None: return lastcat.nextcat = headcat.nextcat headcat = None
Eso es todo, ¡gracias por leer el material! De hecho, la estructura LinkedList no es complicada, y es importante entender cómo funciona desde adentro. Por supuesto, en Python podría haberse implementado en expresiones lambda, habría ocupado mucho menos espacio, pero aquí intenté explicar su estructura y el principio de su funcionamiento en Python lo más detallado posible, en lugar de perseguir la optimización.
El código fuente se puede
encontrar aquí .