© Profit_Image/Shutterstock.com
Es posible que tenga la cabeza en torno a los arreglos, pero hay muchas estructuras de datos que puede usar en la programación. En cierto modo, una lista enlazada es similar a una matriz, pero existen algunas diferencias clave. Explore qué es una lista enlazada, los diferentes tipos y cómo usar una con este artículo.
¿Qué es una lista enlazada?
Al igual que una matriz, una lista lineal es una estructura de datos eso es lineal. Pero la diferencia radica en la forma en que almacenan y acceden a los datos. Mientras que una matriz almacena elementos en un bloque de memoria contiguo, una lista enlazada contiene elementos como nodos, y cada nodo apunta al siguiente elemento de la lista. Como tales, no se almacenan de forma contigua y no se accede a los elementos mediante un índice. En su lugar, se asignan punteros a cada nodo, que dictan qué nodo es el siguiente en la secuencia. Al igual que con una matriz dinámica, las listas vinculadas se pueden modificar agregando o eliminando nodos según sea necesario.
¿Cuáles son los beneficios?
Ahora que hemos cubierto exactamente qué es una lista enlazada, es posible que se pregunte por qué quiere usar uno. Estas son algunas ventajas:
A menos que esté utilizando una matriz dinámica, el tamaño de la matriz tiende a ser fijo, mientras que las listas vinculadas se pueden aumentar o disminuir según corresponda. Insertar o eliminar elementos requiere un tiempo constante, a diferencia de las matrices. donde será necesario cambiar otros elementos. Las listas vinculadas tienden a ser más fáciles con las limitaciones de memoria, particularmente con grandes volúmenes de datos. Esto se debe a que la memoria solo se usa para los nodos requeridos, pero la naturaleza contigua de los arreglos significa que puede admitir algunos datos que no necesita para sus operaciones. Es más fácil mantener la persistencia de los datos con listas vinculadas, ya que los datos pueden serializarse más fácilmente que en arreglos. Esto simplifica la transmisión de datos entre múltiples programas, o después de que los programas hayan terminado. Cuando tenga datos escasos, es decir, con elementos vacíos, una matriz aún los almacenaría. Sin embargo, una lista vinculada solo almacena valores que no están vacíos.
¿Cuáles son los diferentes tipos de listas enlazadas?
Hay bastantes tipos diferentes de listas enlazadas que puede utilizar, cada una con sus propias cualidades. Le daremos un breve repaso aquí y cómo implementarlos en Python.
Lista enlazada simple
Como era de esperar, este es el tipo más simple de lista enlazada, donde solo puede recorrer la lista en una dirección. Cada puntero apunta al siguiente nodo, con el nodo final apuntando a nada o NULL. Esto también se conoce como una lista de enlace simple. El código para implementar una lista enlazada simple en Python es el siguiente:
class Node: def __init__(self, data): self.data=data self.next=None class LinkedList: def __init__(self): self. head=None def add(self, data): new_node=Node(data) if self.head es None: self.head=new_Node else: current_node=self.head while current_node.next is not None: current_node=current_node.next current_node.next=new_node def remove(self, data): if self.head es None: return if self.head.data==data: self.head=self.head.next return current_node=self.head while current_node.next is no Ninguno: si nodo_actual.siguiente.datos==datos: nodo_actual.siguiente=nodo_actual.siguiente.siguiente return def display(self): nodo_actual=self.head while cur rent_node no es Ninguno: print(current_node.data) current_node=current_node.next my_list=LinkedList() my_list.add(1) my_list.add(2) my_list.add(3) my_list.display() my_list.remove(2) my_list.display
Explicación
Este es un bloque de código bastante extenso, pero no demasiado difícil de entender.
Primero, estamos definiendo el”Nodo”y la”Lista Enlazada ” clases. La clase”Nodo”representa un nodo en la lista, cada uno con un puntero (indicado por”self.next”). La lista está representada por”LinkedList”, y hemos implementado un nodo de encabezado, lo que permite insertar o eliminar elementos más fácilmente.
La función”agregar”indica que se debe agregar un nuevo nodo a el final de la lista. Si la lista está vacía, el nodo de encabezado se establece en el nuevo nodo creado. Si no está vacío, la lista se recorre hasta el último nodo y apunta hacia el nuevo nodo.
La función”eliminar”funciona eliminando el primer nodo de la lista. Si este es el nodo de encabezado, el siguiente nodo se convierte en el nodo de encabezado. Si el nodo principal no tiene los datos proporcionados, se recorre la lista para encontrarlos. Una vez que encuentra el nodo con los datos proporcionados, su atributo”siguiente”se establece en el nodo siguiente, lo que elimina este nodo de la lista.
“Mostrar”recorre la lista e imprime los datos encontrados en cada nodo.
Los datos dentro de la lista se definen con la clase”LinkedList”al final, con nodos de valores de datos 1, 2 y 3. El nodo 2 se eliminó para mostrar el proceso de eliminación y ambas listas se imprimen para la salida. Mira la captura de pantalla para saber cómo funciona.
Los datos dentro de la lista se definen con la clase “LinkedList” al final, con nodos de valores de datos 1, 2 y 3.
©”TNGD”.com
Doblemente Lista enlazada
Esto es similar a una lista simple, excepto que el recorrido puede ocurrir en ambas direcciones, hacia adelante y hacia atrás. Para implementar esto, podemos usar el siguiente código:
class Node: def __init__(self, data): self.data=data self.prev=None self.next=None class DoublyLinkedList: def __init__(self): self.head=Ninguno self.tail=Ninguno def add(self,data): new_node=Node(data) si self.head es None: self.head=new_node self.tail=new_node else: new_node.prev=self.tail self.tail.next=new_node self.tail=new_node def remove(self, data): current_node=self.head while current_node is not None: if current_node.data==data: if current_node.prev is not None: current_node.prev.next=current_node.next else: self.head=current_node.next si current_node.next no es Ninguno: current_node.next.prev=current_node.prev else: self.tail=current_node.prev return current_node=current_node.next def display(self): current_node=self.head while current_node is not None: print(current_node.data) current_node=current_node.next my_list=DoublyLinkedList() my_list. add(1) my_list.add(2) my_list.add(3) my_list.display() my_list.remove(3) my_list.display()
Explicación
Mucho del código en este El ejemplo es similar, pero hay algunas diferencias.
Definimos la clase”Nodo”de manera similar, pero hay referencias al nodo anterior así como al siguiente nodo esta vez. De manera similar, la clase’”DoublyLinkedList” representa la lista, pero tiene instancias que funcionan como encabezado y final de la lista.
Al igual que antes, la función “agregar” agrega un nuevo nodo al final de la lista.. Pero si la lista está vacía, tanto la cabeza como la cola se establecen en este nuevo nodo. Cuando la lista no está vacía, el atributo”anterior”del nuevo nodo se establece en la cola actual y el atributo”siguiente”de la cola actual en el nuevo nodo, y la cola se cambia al nuevo nodo.
La función”eliminar”elimina el primer nodo de la lista con los datos proporcionados. Los atributos”anterior”y”siguiente”de los nodos adyacentes se actualizan para evitar el nodo actual, eliminándolo efectivamente de la lista. Si el nodo en cuestión es cabeza o cola, entonces este atributo también se actualiza para reflejar esto.
Por último, las funciones”display”y”my_list”son básicamente las mismas, pero esta vez hemos eliminó el nodo con valor de datos 3. Las capturas de pantalla ilustran la ejecución del código.
La función “añadir” añade un nuevo nodo al final de la lista.
©”TNGD”.com
Las funciones “display” y “my_list” son básicamente las mismas, pero esta vez He eliminado el nodo con valor de datos 3.
©”TNGD”.com
Listas enlazadas circulares
Otro tipo de lista enlazada es una lista circular. Como sugiere el nombre, esta es una lista donde no hay un”final”. El nodo final se conecta de nuevo al nodo inicial. Se ve un ejemplo con el siguiente código:
class Node: def __init__(self, data): self.data=data self.next=None class CircularLinkedList: def __init__(self): self.head=None def add (self, data): new_node=Node(data) if self.head es None: self.head=new_node new_node.next=self.head else: current_node=self.head while current_node.next is not self.head: current_node=nodo_actual.siguiente nodo_actual.siguiente=nuevo_nodo nuevo_nodo.siguiente=self.head def remove(self,data): si self.head es Ninguno: return if self.head.data==data: current_node=self.head while current_node.next no es self.head: current_node=current_node.next current_node.next=self.head.next self.head=self.head.next else: current_node=self.head while current_node.next no es self.head: if current_node.next.data==data: current_node.next=current_node.next.next return current_node=current_node.next def display(self): si self.head es Ninguno: devuelve nodo_actual=self.head while True: print(nodo_actual.datos) nodo_actual=nodo_actual.siguiente si nodo_actual es self.head: romper my_list=CircularLinkedList() my_list.add(1) my_list.add(2) my_list.add (3) my_list.display()
Explicación
Hay algunas diferencias clave aquí. El “nuevo_nodo.siguiente=self.head” significa que el nuevo nodo que se agrega es el último nodo de la lista y apunta al encabezado de la lista, que es el primer nodo.
El “ mientras que la línea current_node.next no es self.head” se usa para recorrer la lista vinculada y agregar elementos. Debido a que no hay un final verdadero, como con la lista de enlaces simples, debemos verificar si el nodo actual es el nodo principal, en lugar de si simplemente no es cero. Esto es para evitar cambiar el nodo principal.
El código “new_node.next=self.head” asegura que el nodo agregado a la lista esté conectado con el nodo principal.
El La función”eliminar”funciona de manera similar en el sentido de que, si los datos proporcionados están contenidos en el primer nodo, este se elimina y el siguiente nodo se convierte en el nuevo nodo principal. Si el nodo principal no contiene los datos proporcionados, la lista se recorre como antes, hasta que se encuentran los datos. El atributo”siguiente”se asigna al nodo después de este, que omite este nodo. En general, la función es la misma, pero la implementación es un poco más elaborada debido a la naturaleza circular de la lista.
La función”mostrar”también es muy similar, excepto que debemos verificar que estamos comenzando en el nodo principal y rompemos el recorrido una vez que llegamos a este punto nuevamente.
El código’new_node.next=self.head’garantiza que el nodo agregado a la lista esté conectado con el nodo principal.
©”TNGD”.com
La “pantalla” La función también es casi la misma, pero debemos comenzar en el nodo principal y romper el recorrido una vez que lleguemos a este punto nuevamente.
©”TNGD”.com
Listas enlazadas circulares dobles
Dado que hemos visto listas enlazadas simples, dobles y circulares, solo tiene sentido para terminar con una lista enlazada circular doble. Todo el bocado, pero no del todo esquivo. Como era de esperar, esto se refiere a una lista enlazada circular que podemos recorrer tanto en dirección hacia adelante como hacia atrás. La implementación de este tipo de lista se puede ilustrar así:
class Node: def __init__(self, data): self.data=data self.next=None self.prev=None class DoubleCircularLinkedList: def__init__(self): self.head=Ninguno def add(self, data): new_node=Node(data) si self.head es None: new_node.next=new_node new_node.prev=new_node self.head=new_node else: last_node=self.head. prev last_node.next=new_node new_node.prev=last_node new_node.next=self.head self.head.prev=new_node def remove(self,data): si self.head es Ninguno: return current_node=self.head while current_node.data !=datos: nodo_actual=nodo_actual.siguiente si nodo_actual==self.head: volver si nodo_actual==self.head: se lf.head=nodo_actual.siguiente nodo_actual.prev.siguiente=nodo_actual.siguiente nodo_actual.siguiente.prev=nodo_actual.anterior def mostrar(self): si self.head es Ninguno: return nodo_actual=self.head while True: print(nodo_actual.data) nodo_actual=nodo_actual.siguiente if nodo_actual==self.head: romper mi_lista=DoubleCircularLinkedList() mi_lista.agregar(1) mi_lista.agregar(2) mi_lista.agregar(3) mi_lista.mostrar()
Explicación
La diferencia clave entre una lista enlazada circular doble y una lista enlazada circular estándar es que, como antes con la lista enlazada no circular, la lista doble apunta cada nodo tanto al nodo anterior como al siguiente. Esto se logra actualizando los atributos”anterior”y”siguiente”del último nodo y el nuevo nodo al agregar un nodo. Al eliminar un nodo, estos atributos del nodo eliminado y los nodos adyacentes deben actualizarse. Si está eliminando el nodo principal, los punteros del último nodo deben actualizarse para reflejar esto.
La lista doble apunta cada nodo al nodo anterior así como al siguiente nodo.
©”TNGD”.com
Si está eliminando el nodo principal , entonces los punteros del último nodo deben actualizarse para reflejar esto.
©”TNGD”.com
Conclusión
Muchos tipos de listas enlazadas se pueden usar como una alternativa a las matrices, como cuando necesita insertar y eliminar elementos regularmente o tiene limitaciones de memoria. Aunque los arreglos funcionan más rápido cuando se trata de ciertas operaciones, las listas enlazadas no carecen de beneficios únicos, por lo que es útil comprender cómo funcionan.
A continuación…
Los datos de la lista enlazada Estructura y cómo usarla Preguntas frecuentes (Preguntas frecuentes)
¿Qué es una lista enlazada?
Una lista enlazada es una estructura de datos en la que los datos se almacenados en”nodos”, y no de forma contigua, como con una matriz. Pueden ser simples o circulares, donde el último implica el último nodo que apunta hacia atrás al nodo principal. También puede implementar listas doblemente enlazadas, donde el recorrido puede ocurrir hacia adelante y hacia atrás a través de la lista.
¿Cuáles son las ventajas y desventajas de las listas enlazadas?
Las listas vinculadas pueden ser mejores que las matrices cuando necesita insertar y eliminar datos con frecuencia o tiene limitaciones de memoria. Sin embargo, una matriz puede ser mejor cuando necesita usar la búsqueda binaria y, debido a que son contiguos, son más amigables con el caché. Si bien la inserción de elementos es más rápida, el acceso a un elemento en particular puede ser más lento porque debe recorrer toda la lista.
¿Cuáles son los diferentes tipos de listas enlazadas?
Los tipos de listas enlazadas incluyen listas simples y doblemente enlazadas, y listas enlazadas circulares y doblemente circulares.
¿Cómo se inserta o elimina un nodo de una lista enlazada?
Para insertar un nodo, debe crear el nuevo nodo y apuntar el atributo”siguiente”de este nodo al siguiente nodo de la lista, así como apuntar el atributo”siguiente”del nodo anterior a este nuevo nodo. Para eliminar un nodo, debe recorrer la lista para encontrar los datos proporcionados. Luego, debe apuntar el atributo”siguiente”del nodo anterior al nodo anterior al nodo que desea eliminar, de modo que se omita en la lista.
¿Cómo se atraviesa un lista enlazada?
Para recorrer la lista, comience con el nodo principal y avance a cada nodo en la secuencia hasta llegar al nodo final.
¿Cuál es la complejidad temporal de las operaciones de listas enlazadas?
Cada operación tiene su propia complejidad temporal. Las operaciones con una complejidad de tiempo de O(1) incluyen la inserción de un elemento al inicio y la eliminación de un elemento al inicio. La mayoría de las demás operaciones tienen una complejidad de O(n). Esto incluye acceder a un elemento, insertar o eliminar un elemento al final, insertar o eliminar un elemento en un índice específico y buscar un elemento en particular. Esto se debe a que la lista debe recorrerse, por lo que la complejidad depende del tamaño de la lista.
¿Cuáles son algunas alternativas a las listas enlazadas?
En cambio de una lista enlazada, podría usar una matriz, donde los datos se almacenan en un bloque contiguo. Las tablas hash se usan para asignar claves a índices en una matriz, por lo que podrían usarse en conjunto. O bien, podría usar un árbol, donde los nodos están conectados en un formato jerárquico. Los montones son un tipo de árbol binario y son otra opción. Por último, las pilas y las colas se pueden usar con matrices o listas vinculadas y, aunque no son tan flexibles como algunas opciones, ofrecen una modificación eficiente de los elementos.
¿Cuáles son algunas aplicaciones de ¿listas vinculadas?
Las listas vinculadas son útiles cuando no sabe el tamaño de la lista, quiere implementar más estructuras de datos, en el procesamiento de imágenes y música y para representar gráficos y árboles.