1. Introducción
En este tutorial, implementaremos dos algoritmos de inversión de listas vinculadas en Java.
2. Estructura de datos de lista vinculada
Una lista vinculada es una estructura de datos lineal en la que un puntero en cada elemento determina el orden. Cada elemento de una lista vinculada contiene un campo de datos para almacenar los datos de la lista y un campo de puntero para apuntar al siguiente elemento de la secuencia. Además, podemos usar un puntero de cabeza para señalar el elemento inicial de una lista vinculada:
Después de invertir la lista vinculada, el encabezado apuntará al último elemento de la lista vinculada original y el puntero de cada elemento apuntará al elemento anterior de la lista vinculada original:
En Java, tenemos una clase LinkedList para proporcionar una implementación de lista doblemente enlazada de las interfaces List y Deque . Sin embargo, en este tutorial usaremos una estructura de datos de lista enlazada individualmente.
Comencemos primero con una clase ListNode para representar un elemento de una lista vinculada:
public class ListNode { private int data; private ListNode next; ListNode(int data) { this.data = data; this.next = null; } // standard getters and setters }La clase ListNode tiene dos campos:
- Un valor entero para representar los datos del elemento.
- Un puntero / referencia al siguiente elemento
Una lista vinculada puede contener varios objetos ListNode . Por ejemplo, podemos construir la lista enlazada de muestra anterior con un bucle:
ListNode constructLinkedList() { ListNode head = null; ListNode tail = null; for (int i = 1; i <= 5; i++) { ListNode node = new ListNode(i); if (head == null) { head = node; } else { tail.setNext(node); } tail = node; } return head; }3. Implementación de algoritmos iterativos
Implementemos el algoritmo iterativo en Java:
ListNode reverseList(ListNode head) { ListNode previous = null; ListNode current = head; while (current != null) { ListNode nextElement = current.getNext(); current.setNext(previous); previous = current; current = nextElement; } return previous; }En este algoritmo iterativo, usamos dos variables ListNode , anterior y actual , para representar dos elementos adyacentes en la lista vinculada. Para cada iteración, invertimos estos dos elementos y luego cambiamos a los siguientes dos elementos.
Al final, el puntero actual será nulo y el puntero anterior será el último elemento de la antigua lista vinculada. Por lo tanto, anterior también es el nuevo puntero principal de la lista enlazada invertida, y lo devolvemos del método.
Podemos verificar esta implementación iterativa con una prueba unitaria simple:
@Test public void givenLinkedList_whenIterativeReverse_thenOutputCorrectResult() { ListNode head = constructLinkedList(); ListNode node = head; for (int i = 1; i <= 5; i++) { assertNotNull(node); assertEquals(i, node.getData()); node = node.getNext(); } LinkedListReversal reversal = new LinkedListReversal(); node = reversal.reverseList(head); for (int i = 5; i>= 1; i--) { assertNotNull(node); assertEquals(i, node.getData()); node = node.getNext(); } }En esta prueba unitaria, primero construimos una lista vinculada de muestra con cinco nodos. Además, verificamos que cada nodo de la lista vinculada contiene el valor de datos correcto. Luego, llamamos a la función iterativa para invertir la lista vinculada. Finalmente, verificamos la lista enlazada invertida para asegurarnos de que los datos estén invertidos como se esperaba.
4. Implementación de algoritmos recursivos
Ahora, implementemos el algoritmo recursivo en Java:
ListNode reverseListRecursive(ListNode head) { if (head == null) { return null; } if (head.getNext() == null) { return head; } ListNode node = reverseListRecursive(head.getNext()); head.getNext().setNext(head); head.setNext(null); return node; }En la función reverseListRecursive , visitamos de forma recursiva cada elemento de la lista enlazada hasta llegar al último. Este último elemento se convertirá en el nuevo encabezado de la lista enlazada invertida. Además, agregamos el elemento visitado al final de la lista vinculada parcialmente invertida.
De manera similar, podemos verificar esta implementación recursiva con una prueba unitaria simple:
@Test public void givenLinkedList_whenRecursiveReverse_thenOutputCorrectResult() { ListNode head = constructLinkedList(); ListNode node = head; for (int i = 1; i <= 5; i++) { assertNotNull(node); assertEquals(i, node.getData()); node = node.getNext(); } LinkedListReversal reversal = new LinkedListReversal(); node = reversal.reverseListRecursive(head); for (int i = 5; i>= 1; i--) { assertNotNull(node); assertEquals(i, node.getData()); node = node.getNext(); } }5. Conclusión
En este tutorial, implementamos dos algoritmos para revertir una lista vinculada. Como siempre, el código fuente del artículo está disponible en GitHub.