© BEST-BACKGROUNDS/Shutterstock.com
Hay muchas aplicaciones para las listas enlazadas, como en el procesamiento de música e imágenes y la representación de gráficos, árboles y estructuras de datos más elaboradas. Pero, ¿por qué querrías invertir una lista enlazada? Entremos en eso.
¿Qué es una lista enlazada invertida?
Como probablemente podrías adivinar, es una lista enlazada que… ¡ha sido invertida! Normalmente, cada nodo apunta al siguiente nodo en una lista, comenzando desde el nodo principal y terminando en el nodo final. Pero, cuando invierte una lista enlazada, los punteros se invierten, de modo que la cabeza se convierte en la cola y la cola se convierte en la cabeza. Considere el caso simple de una lista de 5 nodos. Esto normalmente se vería así:
cabeza → nodo1 → nodo2 → nodo3 → nodo4 → nodo5 → cola
una vez que invertimos la lista, obtenemos:
cola → nodo5 → nodo4 → nodo3 → nodo2 → nodo1 → cabeza
Incluso si la lista se vuelve más larga e involucra más valores de datos, el principio sigue siendo el mismo.
¿Por qué querría invertir un ¿Lista enlazada?
Dado que una lista enlazada invertida sigue siendo una lista enlazada, en esencia, muchas de las aplicaciones son similares. Como tal, las listas invertidas todavía se usan para implementar otras estructuras de datos, en pilas y en colas. Pero, hay algunos usos únicos que las listas de enlaces inversos aportan a la tabla:
Dado que los elementos están invertidos, podemos imprimir los elementos y procesar la lista en orden inverso. Esto es útil si desea mostrar el historial de Internet de un navegador. Si desea eliminar algunos elementos cerca del final de la lista, invertirlo lo hace mucho más fácil. Esto se debe a que estos elementos ahora están al principio de la lista. Esto puede ahorrar mucho tiempo, especialmente si la lista tiene un tamaño considerable. No necesita recorrer toda la lista si invierte la lista. A veces, queremos realizar un algoritmo recursivo en una lista completa, ejecutando operaciones en cada nodo. En algunos de estos casos, puede tener más sentido procesarlos en orden inverso. Otra razón para usar una lista enlazada invertida es verificar si la lista es palindrómica, lo que significa que la secuencia es la misma hacia adelante o hacia atrás. Un ejemplo de esto sería el número 212. Se mire como se mire, la secuencia de valores de datos es idéntica.
Cómo invertir una lista vinculada
En general, existen dos enfoques para invertir una lista vinculada: el enfoque iterativo y el enfoque recursivo. Echemos un vistazo a estos.
El enfoque iterativo
En este método, repetimos la ejecución del algoritmo hasta que cada puntero se haya invertido. Hacemos esto rastreando nuestros nodos usando los atributos”anterior”,”actual”y”siguiente”. Podemos asignarlos como tales:
while (actual !=NULL) { siguiente=actual-> siguiente actual-> siguiente=anterior anterior=actual actual=siguiente } head_ref=anterior
La declaración”while”básicamente itera sobre cada nodo que no es nulo.
La siguiente línea realiza un seguimiento del siguiente nodo en la lista, para que no lo perdamos una vez que invertimos los punteros.
Luego, establecemos el atributo”siguiente”del nodo actual en el nodo anterior, invirtiendo los punteros.
La siguiente línea establece el atributo”anterior”en el nodo anterior, haciendo un seguimiento de él como lo hicimos nosotros el siguiente nodo.
La penúltima línea dice que el puntero”actual”está en el siguiente nodo, por lo que podemos movernos iterativamente a lo largo de la lista.
Por último, establecemos el”head_ref ” puntero al último nodo de la lista original, que será el primer nodo de la lista invertida. Por lo tanto, establecemos esto como el nuevo nodo principal.
Así es como podemos implementar este proceso en Python:
class Node: def __init__(self, data): self.data=data self. next=Ninguno class LinkedList: def __init__(self): self.head=Ninguno def push(self, new_data): new_node=Node(new_data) new_node.next=self.head self.head=new_node def reverse(self): prev_node=Ninguno nodo_actual=self.head mientras que nodo_actual no es Ninguno: nodo_siguiente=nodo_actual.siguiente nodo_actual.siguiente=nodo_anterior nodo_anterior=nodo_actual nodo_actual=nodo_siguiente self.head=nodo_anterior def imprimirLista(self): nodo_actual=self.head while nodo_actual: print( current_node.data, end=””) current_node=current_node.next my_list=LinkedList() my_list.push(16) my_list.push(2) my_list.push(19) my_list.push(71) print(“Lista enlazada dada”) mi_lista.printList() mi_lista.reverse () print(“\nLista enlazada inversa”) my_list.printList()
Primero, definimos las clases”Nodo”y”ListaEnlazada”. Luego, definimos la función”push”, que se usa para agregar un nuevo nodo al principio de la lista, que se designa como el nodo principal.
Luego, vemos implementada la función”reverse”de la misma manera que se describió anteriormente.
Finalmente, estamos definiendo la función”printList”para la clase”LinkedList”, que imprime el valor de los datos en cada nodo, que continúa hasta que”current_node ” es igual a “Ninguno”, lo que indica que hemos llegado al final de la lista. Vea la captura de pantalla para ver cómo funciona esto en Python.
El enfoque iterativo para revertir una lista enlazada, implementado en Python.
©”TNGD”.com
El enfoque recursivo
El otro método para revertir una lista enlazada es el enfoque recursivo. Mientras que los enfoques iterativos funcionan mediante el uso de bucles o instrucciones repetitivas para resolver un problema, los enfoques recursivos ejecutan la misma función en ejemplos cada vez más pequeños del mismo problema. Una vez que se resuelven estos subproblemas, las soluciones se combinan para dar un resultado general al problema inicial. Veamos cómo funciona la recursividad para invertir una lista enlazada:
Primero, dividimos la lista en dos partes, el primer nodo y la lista restante.
Luego, llamamos al “ reverse” para la lista restante.
Esta lista invertida se vincula al primer nodo, y el puntero principal original se establece en NULL. El nuevo puntero principal se establece en el nuevo nodo principal y la lista se invierte.
Aquí se muestra cómo se implementa esto:
class Node: def__init__(self, data): self. datos=datos self.next=Ninguno class LinkedList: def__init__(self): self.head=Ninguno def push(self, new_data): new_node=Node(new_data) new_node.next=self.head self.head=new_node def reverse_recursive( self, nodo_actual): si nodo_actual es Ninguno o nodo_actual.siguiente es Ninguno: return nodo_actual rest=self.reverse_recursive(nodo_actual.siguiente) nodo_actual.next.next=nodo_actual nodo_actual.next=Ninguno return rest def reverse(self): self. head=self.reverse_recursive(self.head) def printList(self): nodo_actual=self.head while nodo_actual: print(nodo_actual.datos, end=””) nodo_actual=nodo_actual.siguiente print() mi_lista=LinkedList() mi_lista. push(16) mi_lista.push(2) mi_lista.push(19) mi _list.push(71) print(“Lista enlazada dada”) my_list.printList() my_list.reverse() print(“Lista enlazada inversa (recursiva):”) my_list.printList()
Mucho de este código es lo mismo que el proceso iterativo. La principal diferencia está, como era de esperar, en la función inversa utilizada.
En este caso, definimos la función”reverse_recursive”como una función del nodo actual. Cada nodo después de este se invierte recursivamente llamando a la función inversa con el siguiente nodo como entrada hasta que el nodo actual sea igual a”Ninguno”. Esto sucede cuando se llega al final de la lista, o en el caso simple donde solo hay un nodo en la lista.
Entonces, el nodo actual se invierte actualizando el atributo”siguiente”del siguiente nodo al nodo actual, y el atributo”siguiente”del nodo actual a”Ninguno”. El nodo actual se convierte en la cola de la lista invertida.
El enfoque recursivo para revertir una lista enlazada, implementado en Python.
©”TNGD”.com
Conclusión
Cuando necesita revertir una lista enlazada, puede elegir entre un enfoque iterativo y un enfoque recursivo. Mientras que los enfoques iterativos se basan en repetir las mismas instrucciones en un ciclo”while”para cada nodo, las funciones recursivas ejecutan su función en instancias más pequeñas del mismo problema. Invertir una lista enlazada puede ser útil para detectar la palindromicidad de una lista y modificar elementos al final de la lista original.
Cómo invertir una lista enlazada, con ejemplos Preguntas frecuentes (FAQ)
¿Qué es una lista de enlaces invertidos?
Una lista de enlaces invertidos es una lista enlazada que tiene el orden de sus elementos invertido, de modo que el último nodo se convierte en el primero nodo de la nueva lista y los punteros están invertidos.
¿Por qué querría invertir una lista vinculada?
Invertir una lista puede ser útil para determinando si una lista es palindrómica, modificando elementos al final de la lista original (como ahora están al principio), o cuando desea usar ciertos algoritmos que son mejores para usar con una lista invertida.
¿Cómo se puede revertir una lista enlazada?
Las formas más comunes de revertir una lista enlazada son a través de funciones iterativas o recursivas. Donde el enfoque iterativo funciona recorriendo la lista y cambiando los punteros de cada nodo, la función inversa recursiva funciona invirtiendo la lista aparte del nodo principal y luego actualizando los punteros del nodo actual.
Cómo ¿Se invierten las listas con enlaces dobles y las listas con enlaces circulares?
Puede invertir una lista con enlaces dobles de la misma manera que una lista con enlaces simples, pero debe actualizar el”siguiente”y atributos”prev”de cada nodo en consecuencia. Para las listas enlazadas circulares, debe actualizar el atributo”siguiente”del nodo final para que apunte al nuevo nodo principal.
¿Cuál es la complejidad temporal de invertir una lista enlazada?
La complejidad del tiempo es igual a O(n), donde n es el número de nodos, porque debe atravesar la lista para invertir los punteros, independientemente del método que utilice.
¿Cuál es la complejidad espacial de invertir una lista enlazada?
La complejidad espacial es igual a O(1) con respecto al enfoque iterativo, ya que las variables temporales que necesita para invertir la lista permanecen constante. Para el enfoque recursivo, la complejidad del espacio es igual a O(n), ya que debe almacenar cada llamada de la función recursiva en una pila.