Estructuras de datos y algoritmos en Java, Parte 5: Listas doblemente enlazadas

Si bien las listas de enlaces individuales tienen muchos usos, también presentan algunas restricciones. Por un lado, las listas enlazadas individualmente restringen el recorrido de los nodos a una sola dirección: no puede atravesar una lista enlazada individualmente hacia atrás a menos que primero invierta sus enlaces de nodo, lo que lleva tiempo. Si realiza un recorrido inverso y necesita restaurar el recorrido del nodo a la dirección original, tendrá que repetir la inversión, lo que lleva más tiempo. Las listas de enlaces individuales también restringen la eliminación de nodos. En este tipo de lista, no puede eliminar un nodo arbitrario sin acceso al predecesor del nodo.

Afortunadamente, Java ofrece varios tipos de listas que puede utilizar para buscar y ordenar los datos almacenados en sus programas Java. Este tutorial final de la serie Estructuras de datos y algoritmos presenta la búsqueda y clasificación con listas doblemente enlazadas y listas enlazadas circulares. Como verá, estas dos categorías de estructura de datos se basan en listas vinculadas individualmente para ofrecer una gama más amplia de comportamiento de búsqueda y clasificación en sus programas Java.

Listas doblemente enlazadas

Una lista doblemente enlazada es una lista enlazada de nodos donde cada nodo tiene un par de campos de enlace. Un campo de vínculo le permite recorrer la lista en una dirección hacia adelante, mientras que el otro nodo le permite recorrer la lista en una dirección hacia atrás. Para la dirección de avance, una variable de referencia contiene una referencia al primer nodo. Cada nodo enlaza con el siguiente nodo a través del campo de enlace "siguiente", excepto el último nodo, cuyo campo de enlace "siguiente" contiene la referencia nula para indicar el final de la lista (en la dirección de avance). La dirección hacia atrás funciona de manera similar. Una variable de referencia contiene una referencia al último nodo de la dirección de avance, que se interpreta como el primer nodo. Cada nodo se enlaza con el nodo anterior a través del campo de enlace "anterior". El "anterior" del primer nodoEl campo de enlace contiene un valor nulo para indicar el final de la lista.

Intente pensar en una lista doblemente enlazada como un par de listas enlazadas individualmente, cada una interconectando los mismos nodos. El diagrama de la Figura 1 muestra topForward-referenced y topBackward-referenced listas enlazadas por enlaces sencillos.

Operaciones CRUD en listas doblemente enlazadas

La creación, inserción y eliminación de nodos son operaciones comunes en una lista doblemente vinculada. Son similares a las operaciones que aprendió para las listas de enlaces individuales. (Recuerde que una lista doblemente enlazada es solo un par de listas enlazadas individualmente que interconectan los mismos nodos). El siguiente pseudocódigo demuestra la creación e inserción de nodos en la lista doblemente enlazada que se muestra en la Figura 1. El pseudocódigo también demuestra el nodo supresión:

 DECLARE CLASS Node DECLARE STRING name DECLARE Node next DECLARE Node prev END DECLARE DECLARE Node topForward DECLARE Node temp DECLARE Node topBackward topForward = NEW Node topForward.name = "A" temp = NEW Node temp.name = "B" topBackward = NEW Node topBackward.name = "C" // Create forward singly-linked list topForward.next = temp temp.next = topBackward topBackward.next = NULL // Create backward singly-linked list topBackward.prev = temp temp.prev = topForward topForward.prev = NULL // Delete Node B. temp.prev.next = temp.next; // Bypass Node B in the forward singly-linked list. temp.next.prev = temp.prev; // Bypass Node B in the backward singly-linked list. END 

Aplicación de ejemplo: CRUD en una lista doblemente enlazada

La aplicación Java de ejemplo DLLDemodemuestra cómo crear, insertar y eliminar nodos en una lista doblemente vinculada. El código fuente de la aplicación se muestra en el Listado 1.

Listado 1. Una aplicación Java que demuestra CRUD en una lista doblemente enlazada

 public final class DLLDemo { private static class Node { String name; Node next; Node prev; } public static void main(String[] args) { // Build a doubly-linked list. Node topForward = new Node(); topForward.name = "A"; Node temp = new Node(); temp.name = "B"; Node topBackward = new Node(); topBackward.name = "C"; topForward.next = temp; temp.next = topBackward; topBackward.next = null; topBackward.prev = temp; temp.prev = topForward; topForward.prev = null; // Dump forward singly-linked list. System.out.print("Forward singly-linked list: "); temp = topForward; while (temp != null) { System.out.print(temp.name); temp = temp.next; } System.out.println(); // Dump backward singly-linked list. System.out.print("Backward singly-linked list: "); temp = topBackward; while (temp != null) { System.out.print(temp.name); temp = temp.prev; } System.out.println(); // Reference node B. temp = topForward.next; // Delete node B. temp.prev.next = temp.next; temp.next.prev = temp.prev; // Dump forward singly-linked list. System.out.print("Forward singly-linked list (after deletion): "); temp = topForward; while (temp != null) { System.out.print(temp.name); temp = temp.next; } System.out.println(); // Dump backward singly-linked list. System.out.print("Backward singly-linked list (after deletion): "); temp = topBackward; while (temp != null) { System.out.print(temp.name); temp = temp.prev; } System.out.println(); } } 

Compile el Listado 4 de la siguiente manera:

 javac DLLDemo.java 

Ejecute la aplicación resultante de la siguiente manera:

 java DLLDemo 

Debe observar el siguiente resultado:

 Forward singly-linked list: ABC Backward singly-linked list: CBA Forward singly-linked list (after deletion): AC Backward singly-linked list (after deletion): CA 

Barajar en listas doblemente enlazadas

El marco de colecciones de Java incluye una Collectionsclase de métodos de utilidad, que es parte del java.utilpaquete. Esta clase incluye un void shuffle(List list)método que " permuta aleatoriamente la lista especificada usando una fuente predeterminada de aleatoriedad ". Por ejemplo, puede usar este método para barajar una baraja de cartas expresada como una lista doblemente enlazada (la java.util.LinkedListclase es un ejemplo). En el pseudocódigo a continuación, puede ver cómo el algoritmo Shuffle podría mezclar una lista doblemente enlazada:

 DECLARE RANDOM rnd = new RANDOM DECLARE INTEGER i FOR i = 3 DOWNTO 2 swap(topForward, i - 1, rnd.nextInt(i)) END FOR FUNCTION swap(Node top, int i, int j) DECLARE Node nodei, nodej DECLARE INTEGER k // Locate ith node. Node nodei = top FOR k = 0 TO i - 1 nodei = nodei.next END FOR // Locate jth node. Node nodej = top FOR k = 0 TO i - 1 nodej = nodej.next END FOR // Perform the swap. DECLARE STRING namei = nodei.name DECLARE STRING namej = nodej.name nodej.name = namei nodei.name = namej END FUNCTION END 

El algoritmo Shuffle obtiene una fuente de aleatoriedad y luego recorre la lista hacia atrás, desde el último nodo hasta el segundo. Cambia repetidamente un nodo seleccionado al azar (que en realidad es solo el campo de nombre) a la "posición actual". Los nodos se seleccionan aleatoriamente de la parte de la lista que va desde el primer nodo hasta la posición actual, inclusive. Tenga en cuenta que este algoritmo se extrae aproximadamente del void shuffle(List list)código fuente.

El pseudocódigo del algoritmo Shuffle es perezoso porque se centra solo en la lista de enlaces sencillos que recorren hacia adelante. Es una decisión de diseño razonable, pero pagamos un precio por la complejidad del tiempo. La complejidad del tiempo es O ( n 2). Primero, tenemos el bucle O ( n ) que llama swap(). En segundo lugar, en el interior swap(), tenemos los dos bucles O ( n ) secuenciales . Recuerde la siguiente regla de la Parte 1:

 If f1(n) = O(g(n)) and f2(n) = O(h(n)) then (a) f1(n)+f2(n) = max(O(g(n)), O(h(n))) (b) f1(n)*f2(n) = O(g(n)*h(n)). 

La parte (a) trata de los algoritmos secuenciales. Aquí, tenemos dos bucles O ( n ). Según la regla, la complejidad temporal resultante sería O ( n ). La parte (b) trata de los algoritmos anidados. En este caso, tenemos O ( n ) multiplicado por O ( n ), resultando en O ( n 2).

Tenga en cuenta que la complejidad del espacio de Shuffle es O (1), que resulta de las variables auxiliares que se declaran.

Aplicación de ejemplo: barajar en una lista doblemente enlazada

La Shuffleaplicación del Listado 2 es una demostración del algoritmo Shuffle.

Listado 2. El algoritmo Shuffle en Java

 import java.util.Random; public final class Shuffle { private static class Node { String name; Node next; Node prev; } public static void main(String[] args) { // Build a doubly-linked list. Node topForward = new Node(); topForward.name = "A"; Node temp = new Node(); temp.name = "B"; Node topBackward = new Node(); topBackward.name = "C"; topForward.next = temp; temp.next = topBackward; topBackward.next = null; topBackward.prev = temp; temp.prev = topForward; topForward.prev = null; // Dump forward singly-linked list. System.out.print("Forward singly-linked list: "); temp = topForward; while (temp != null) { System.out.print(temp.name); temp = temp.next; } System.out.println(); // Dump backward singly-linked list. System.out.print("Backward singly-linked list: "); temp = topBackward; while (temp != null) { System.out.print(temp.name); temp = temp.prev; } System.out.println(); // Shuffle list. Random rnd = new Random(); for (int i = 3; i > 1; i--) swap(topForward, i - 1, rnd.nextInt(i)); // Dump forward singly-linked list. System.out.print("Forward singly-linked list: "); temp = topForward; while (temp != null) { System.out.print(temp.name); temp = temp.next; } System.out.println(); // Dump backward singly-linked list. System.out.print("Backward singly-linked list: "); temp = topBackward; while (temp != null) { System.out.print(temp.name); temp = temp.prev; } System.out.println(); } public static void swap(Node top, int i, int j) { // Locate ith node. Node nodei = top; for (int k = 0; k < i; k++) nodei = nodei.next; // Locate jth node. Node nodej = top; for (int k = 0; k < j; k++) nodej = nodej.next; String namei = nodei.name; String namej = nodej.name; nodej.name = namei; nodei.name = namej; } } 

Compile el Listado 5 de la siguiente manera:

 javac Shuffle.java 

Ejecute la aplicación resultante de la siguiente manera:

 java Shuffle 

Debería observar el siguiente resultado de una ejecución:

 Forward singly-linked list: ABC Backward singly-linked list: CBA Forward singly-linked list: BAC Backward singly-linked list: CAB 

Listas enlazadas circulares

El campo de enlace en el último nodo de una lista de enlaces individuales contiene un enlace nulo. Esto también es cierto en una lista doblemente enlazada, que contiene los campos de enlace en los últimos nodos de las listas enlazadas hacia adelante y hacia atrás. Supongamos, en cambio, que los últimos nodos contienen enlaces a los primeros nodos. En esta situación, terminaría con una lista enlazada circular , que se muestra en la Figura 2.

Circular-linked lists, also known as circular buffers or circular queues, have many uses. For example, they're used by operating system interrupt handlers to buffer keystrokes. Multimedia applications use circular-linked lists to buffer data (for example, buffering data being written to a sound card). This technique is also used by the LZ77 family of lossless data compression algorithms.

Linked lists versus arrays

Throughout this series on data structures and algorithms, we've considered the strengths and weaknesses of different data structures. Since we've focused on arrays and linked lists, you might have questions about these types specifically. What advantages and disadvantages do linked lists and arrays offer? When do you use a linked list and when do you use an array? Can data structures from both categories be integrated into a useful hybrid data structure? I'll try to answer these questions below.

Linked lists offer the following advantages over arrays:

  • They don't require extra memory to support expansion. In contrast, arrays require extra memory when expansion is necessary. (Once all elements contain data items, no new data items can be appended to an array.)
  • Ofrecen una inserción / eliminación de nodos más rápida que las operaciones equivalentes basadas en matrices. Solo los enlaces deben actualizarse después de identificar la posición de inserción / eliminación. Desde una perspectiva de matriz, la inserción de elementos de datos requiere el movimiento de todos los demás elementos de datos para crear un elemento vacío. De manera similar, la eliminación de un elemento de datos existente requiere el movimiento de todos los demás elementos de datos para eliminar un elemento vacío. Todo el movimiento de elementos de datos lleva tiempo.

Por el contrario, las matrices ofrecen las siguientes ventajas sobre las listas enlazadas:

  • Los elementos de la matriz ocupan menos memoria que los nodos porque los elementos no requieren campos de enlace.
  • Las matrices ofrecen un acceso más rápido a los elementos de datos, a través de índices basados ​​en números enteros.