Implementación de Java de lista enlazada circular

1. Introducción

En este tutorial, veremos la implementación de una lista enlazada circular en Java.

2. Lista enlazada circular

Una lista enlazada circular es una variación de una lista enlazada en la que el último nodo apunta al primer nodo, completando un círculo completo de nodos . En otras palabras, esta variación de la lista vinculada no tiene un elemento nulo al final.

Con este simple cambio, obtenemos algunos beneficios:

  • Cualquier nodo de la lista circular vinculada puede ser un punto de partida
  • En consecuencia, toda la lista se puede recorrer a partir de cualquier nodo
  • Dado que el último nodo de la lista enlazada circular tiene el puntero al primer nodo, es fácil realizar operaciones de poner y quitar de cola

Con todo, esto es muy útil en la implementación de la estructura de datos de la cola.

En cuanto al rendimiento, es lo mismo que otras implementaciones de listas vinculadas, excepto por una cosa: el desplazamiento desde el último nodo al nodo principal se puede hacer en tiempo constante . Con listas enlazadas convencionales, esta es una operación lineal.

3. Implementación en Java

Comencemos creando una clase de nodo auxiliar que almacenará valores int y un puntero al siguiente nodo :

class Node { int value; Node nextNode; public Node(int value) { this.value = value; } }

Ahora creemos el primer y último nodos en la lista enlazada circular, generalmente llamados cabeza y cola:

public class CircularLinkedList { private Node head = null; private Node tail = null; // .... }

En las siguientes subsecciones, veremos las operaciones más comunes que podemos realizar en una lista enlazada circular.

3.1. Insertar elementos

La primera operación que vamos a cubrir es la inserción de nuevos nodos. Al insertar un nuevo elemento, necesitaremos manejar dos casos:

  • La cabeza de nodo es nulo , es decir no hay elementos ya añadidos. En este caso, crearemos el nuevo nodo que agreguemos como cabeza y cola de la lista, ya que solo hay un nodo
  • La cabeza nodo no es nulo , es decir, hay uno o más elementos ya se han agregado a la lista. En este caso, la cola existente debe apuntar al nuevo nodo y el nodo recién agregado se convertirá en la cola.

En los dos casos anteriores, el nextNode para tail apuntará a la cabeza

Creemos un método addNode que tome el valor a insertar como parámetro:

public void addNode(int value) { Node newNode = new Node(value); if (head == null) { head = newNode; } else { tail.nextNode = newNode; } tail = newNode; tail.nextNode = head; }

Ahora podemos agregar algunos números a nuestra lista circular vinculada:

private CircularLinkedList createCircularLinkedList() { CircularLinkedList cll = new CircularLinkedList(); cll.addNode(13); cll.addNode(7); cll.addNode(24); cll.addNode(1); cll.addNode(8); cll.addNode(37); cll.addNode(46); return cll; }

3.2. Encontrar un elemento

La siguiente operación que veremos es buscar para determinar si un elemento está presente en la lista.

Para esto, arreglaremos un nodo en la lista (generalmente el encabezado ) como currentNode y recorreremos toda la lista usando el nextNode de este nodo , hasta que encontremos el elemento requerido.

Agreguemos un nuevo método containsNode que toma searchValue como parámetro:

public boolean containsNode(int searchValue) { Node currentNode = head; if (head == null) { return false; } else { do { if (currentNode.value == searchValue) { return true; } currentNode = currentNode.nextNode; } while (currentNode != head); return false; } }

Ahora, agreguemos un par de pruebas para verificar que la lista creada anteriormente contiene los elementos que agregamos y no los nuevos:

@Test public void givenACircularLinkedList_WhenAddingElements_ThenListContainsThoseElements() { CircularLinkedList cll = createCircularLinkedList(); assertTrue(cll.containsNode(8)); assertTrue(cll.containsNode(37)); } @Test public void givenACircularLinkedList_WhenLookingForNonExistingElement_ThenReturnsFalse() { CircularLinkedList cll = createCircularLinkedList(); assertFalse(cll.containsNode(11)); }

3.3. Eliminar un elemento

A continuación, veremos la operación de eliminación. De manera similar a la inserción, tenemos un par de casos (excluyendo el caso en el que la lista en sí está vacía) que debemos mirar.

  • El elemento a eliminar es la propia cabeza . En este caso, tenemos que actualizar la cabeza como el siguiente nodo de la cabeza actual , y el siguiente nodo de la cola como el nuevo jefe
  • El elemento a eliminar es cualquier elemento que no sea el encabezado . En este caso, solo necesitamos actualizar el siguiente nodo del nodo anterior como el siguiente nodo del nodo que necesita ser eliminado.

Ahora agregaremos un nuevo método deleteNode que toma valueToDelete como parámetro:

public void deleteNode(int valueToDelete) { Node currentNode = head; if (head != null) { if (currentNode.value == valueToDelete) { head = head.nextNode; tail.nextNode = head; } else { do { Node nextNode = currentNode.nextNode; if (nextNode.value == valueToDelete) { currentNode.nextNode = nextNode.nextNode; break; } currentNode = currentNode.nextNode; } while (currentNode != head); } } }

Ahora agreguemos una prueba simple para verificar que la eliminación funciona como se esperaba para todos los casos:

@Test public void givenACircularLinkedList_WhenDeletingElements_ThenListDoesNotContainThoseElements() { CircularLinkedList cll = createCircularLinkedList(); assertTrue(cll.containsNode(13)); cll.deleteNode(13); assertFalse(cll.containsNode(13)); assertTrue(cll.containsNode(1)); cll.deleteNode(1); assertFalse(cll.containsNode(1)); assertTrue(cll.containsNode(46)); cll.deleteNode(46); assertFalse(cll.containsNode(46)); }

3.4. Atravesando la lista

Vamos a echar un vistazo al recorrido de nuestra lista circular enlazada en esta sección final . De manera similar a las operaciones de búsqueda y eliminación, para el recorrido, fijamos el currentNode como encabezado y recorremos toda la lista utilizando el nextNode de este nodo.

Agreguemos un nuevo método traverseList que imprime los elementos que se agregan a la lista:

public void traverseList() { Node currentNode = head; if (head != null) { do { LOGGER.info(currentNode.value + " "); currentNode = currentNode.nextNode; } while (currentNode != head); } } 

Como podemos ver, en el ejemplo anterior, durante el recorrido, simplemente imprimimos el valor de cada uno de los nodos, hasta que regresemos al nodo principal.

4. Conclusión

En este tutorial, hemos visto cómo implementar una lista enlazada circular en Java y exploramos algunas de las operaciones más comunes.

Primero, aprendimos qué es exactamente una lista enlazada circular que incluye algunas de las características y diferencias más comunes con una lista enlazada convencional. Luego, vimos cómo insertar, buscar, eliminar y recorrer elementos en nuestra implementación de lista enlazada circular.

Como de costumbre, todos los ejemplos utilizados en este artículo están disponibles en GitHub.