Estructuras de datos y algoritmos en Java, Parte 4: Listas enlazadas individualmente

Al igual que las matrices, que se presentaron en la Parte 3 de esta serie de tutoriales, las listas vinculadas son una categoría de estructura de datos fundamental en la que se pueden basar estructuras de datos más complejas. Sin embargo, a diferencia de una secuencia de elementos, una lista vinculada es una secuencia de nodos, donde cada nodo está vinculado al nodo anterior y al siguiente de la secuencia. Recuerde que un nodo es un objeto creado a partir de una clase autorreferencial, y una clase autorreferencial tiene al menos un campo cuyo tipo de referencia es el nombre de la clase. Los nodos de una lista vinculada están vinculados mediante una referencia de nodo. He aquí un ejemplo:

 class Employee { private int empno; private String name; private double salary; public Employee next; // Other members. }

En este ejemplo, Employeees una clase autorreferencial porque su nextcampo tiene tipo Employee. Este campo es un ejemplo de un campo de vínculo porque puede almacenar una referencia a otro objeto de su clase, en este caso otro Employeeobjeto.

Este tutorial presenta los entresijos de las listas enlazadas individualmente en la programación Java. Aprenderá operaciones para crear una lista enlazada individualmente, insertando nodos en una lista enlazada individualmente, eliminando nodos de una lista enlazada individualmente, concatenando una lista enlazada individualmente a otra lista enlazada individualmente e invirtiendo una lista enlazada individualmente. También exploraremos los algoritmos más utilizados para ordenar listas enlazadas individualmente y concluiremos con un ejemplo que demuestra el algoritmo de ordenación por inserción.

descargar Obtener el código Descargue las tres aplicaciones de ejemplo para este artículo. Creado por Jeff Friesen para JavaWorld.

¿Qué es una lista enlazada individualmente?

Una lista enlazada es una lista enlazada de nodos donde cada nodo tiene un campo de enlace único. En esta estructura de datos, una variable de referencia contiene una referencia al primer nodo (o superior); cada nodo (excepto el último o el inferior) enlaza con el siguiente; y el campo de enlace del último nodo contiene la referencia nula para indicar el final de la lista. Aunque la variable de referencia se denomina comúnmente top, puede elegir el nombre que desee.

La Figura 1 presenta una lista enlazada individualmente con tres nodos.

A continuación se muestra el pseudocódigo para una lista enlazada individualmente.

 DECLARE CLASS Node DECLARE STRING name DECLARE Node next END DECLARE DECLARE Node top = NULL 

Nodees una clase autorreferencial con un namecampo de datos y un nextcampo de enlace. topes una variable de referencia de tipo Nodeque contiene una referencia al primer Nodeobjeto en una lista enlazada individualmente. Debido a que la lista aún no existe, topel valor inicial es NULL.

Crear una lista enlazada individualmente en Java

Crea una lista enlazada individualmente adjuntando un solo Nodeobjeto. El siguiente pseudocódigo crea un Nodeobjeto, asigna su referencia top, inicializa su campo de datos y lo asigna NULLa su campo de enlace:

 top = NEW Node top.name = "A" top.next = NULL 

La Figura 2 muestra la lista inicial enlazada individualmente que emerge de este pseudocódigo.

Esta operación tiene una complejidad de tiempo de O (1) - constante. Recuerde que O (1) se pronuncia "Big Oh of 1." (Consulte la Parte 1 para obtener un recordatorio de cómo se utilizan las medidas de complejidad de tiempo y espacio para evaluar las estructuras de datos).

Insertar nodos en una lista enlazada individualmente

Insertar un nodo en una lista enlazada individualmente es algo más complicado que crear una lista enlazada individualmente porque hay tres casos a considerar:

  • Inserción antes del primer nodo.
  • Inserción después del último nodo.
  • Inserción entre dos nodos.

Inserción antes del primer nodo

Se inserta un nuevo nodo antes del primer nodo asignando la referencia del nodo superior al campo de enlace del nuevo nodo y asignando la referencia del nuevo nodo a la topvariable. Esta operación se demuestra mediante el siguiente pseudocódigo:

 DECLARE Node temp temp = NEW Node temp.name = "B" temp.next = top top = temp 

La Nodelista de dos resultante aparece en la Figura 3.

Esta operación tiene una complejidad temporal de O (1).

Inserción después del último nodo

Un nuevo nodo se inserta después del último nodo asignando un valor nulo al campo de enlace del nuevo nodo, atravesando la lista enlazada individualmente para encontrar el último nodo y asignando la referencia del nuevo nodo al campo de enlace del último nodo, como lo demuestra el siguiente pseudocódigo:

 temp = NEW Node temp.name = "C" temp.next = NULL DECLARE Node temp2 temp2 = top // We assume top (and temp2) are not NULL // because of the previous pseudocode. WHILE temp2.next NE NULL temp2 = temp2.next END WHILE // temp2 now references the last node. temp2.next = temp 

La figura 4 revela la lista que sigue a la inserción de NodeC después de NodeA.

Esta operación tiene una complejidad temporal de O ( n ) - lineal. Su complejidad de tiempo se podría mejorar a O (1) manteniendo una referencia al último nodo. En ese caso, no sería necesario buscar el último nodo.

Inserción entre dos nodos

Insertar un nodo entre dos nodos es el caso más complejo. Para insertar un nuevo nodo entre dos nodos, recorre la lista para encontrar el nodo que viene antes del nuevo nodo, asigna la referencia en el campo de enlace del nodo encontrado al campo de enlace del nuevo nodo y asigna la referencia del nuevo nodo al enlace del nodo encontrado. campo. El siguiente pseudocódigo demuestra estas tareas:

 temp = NEW Node temp.name = "D" temp2 = top // We assume that the newly created Node inserts after Node // A and that Node A exists. In the real world, there is no // guarantee that any Node exists, so we would need to check // for temp2 containing NULL in both the WHILE loop's header // and after the WHILE loop completes. WHILE temp2.name NE "A" temp2 = temp2.next END WHILE // temp2 now references Node A. temp.next = temp2.next temp2.next = temp 

La Figura 5 presenta la lista que sigue a la inserción de NodeD entre Nodes A y C.

Esta operación tiene una complejidad temporal de O ( n ).

Eliminar nodos de una lista vinculada individualmente

Eliminar un nodo de una lista enlazada individualmente también es algo más complicado que crear una lista enlazada individualmente. Sin embargo, solo hay dos casos a considerar:

  • Eliminación del primer nodo.
  • Eliminación de cualquier nodo excepto el primero.

Deletion of the first node

Deleting the first node involves assigning the link in the first node's link field to the variable that references the first node, but only when there is a first node:

 IF top NE NULL THEN top = top.next; // Reference the second Node (or NULL when there's only one Node). END IF 

Figure 6 presents before and after views of a list where the first Node has been deleted. Node B disappears and Node A becomes the first Node.

This operation has a time complexity of O(1).

Deletion of any node but the first node

Deleting any node but the first node involves locating the node that precedes the node to be deleted and assigning the reference in the node-to-be-deleted's link field to the preceding node's link field. Consider the following pseudocode:

 IF top NE NULL THEN temp = top WHILE temp.name NE "A" temp = temp.next END WHILE // We assume that temp references Node A. temp.next = temp.next.next // Node D no longer exists. END IF 

Figure 7 presents before and after views of a list where an intermediate Node is deleted. Node D disappears.

This operation has a time complexity of O(n).

Example #1: Create, insert, and delete in a singly linked list

I've created a Java application named SLLDemo that demonstrates how to create, insert, and delete nodes in a singly linked list. Listing 1 presents this application's source code.

Listing 1. Java application demo for singly linked lists (SSLDemo.java, version 1)

 public final class SLLDemo { private static class Node { String name; Node next; } public static void main(String[] args) { Node top = null; // 1. The singly linked list does not exist. top = new Node(); top.name = "A"; top.next = null; dump("Case 1", top); // 2. The singly linked list exists and the node must be inserted // before the first node. Node temp; temp = new Node(); temp.name = "B"; temp.next = top; top = temp; dump("Case 2", top); // 3. The singly linked list exists and the node must be inserted // after the last node. temp = new Node(); temp.name = "C"; temp.next = null; Node temp2; temp2 = top; while (temp2.next != null) temp2 = temp2.next; temp2.next = temp; dump("Case 3", top); // 4. The singly linked list exists and the node must be inserted // between two nodes. temp = new Node(); temp.name = "D"; temp2 = top; while (temp2.name.equals("A") == false) temp2 = temp2.next; temp.next = temp2.next; temp2.next = temp; dump("Case 4", top); // 5. Delete the first node. top = top.next; dump("After first node deletion", top); // 5.1 Restore node B. temp = new Node(); temp.name = "B"; temp.next = top; top = temp; // 6. Delete any node but the first node. temp = top; while (temp.name.equals("A") == false) temp = temp.next; temp.next = temp.next.next; dump("After D node deletion", top); } private static void dump(String msg, Node topNode) { System.out.print(msg + " "); while (topNode != null) { System.out.print(topNode.name + " "); topNode = topNode.next; } System.out.println(); } } 

Compile Listing 1 as follows:

 javac SLLDemo.java 

Run the resulting application as follows:

 java SLLDemo 

You should observe the following output:

 Case 1 A Case 2 B A Case 3 B A C Case 4 B A D C After first node deletion A D C After D node deletion B A C 

Concatenating singly linked lists

You might occasionally need to concatenate a singly linked list to another singly linked list. For example, suppose you have a list of words that start with letters A through M and another list of words starting with letters N through Z, and you want to combine these lists into a single list. The following pseudocode describes an algorithm for concatenating one singly linked list to another:

 DECLARE Node top1 = NULL DECLARE Node top2 = NULL // Assume code that creates top1-referenced singly linked list. // Assume code that creates top2-referenced singly linked list. // Concatenate top2-referenced list to top1-referenced list. IF top1 EQ NULL top1 = top2 END END IF // Locate final Node in top1-referenced list. DECLARE Node temp = top1 WHILE temp.next NE NULL temp = temp.next END WHILE // Concatenate top2 to top1. temp.next = top2 END 

In the trivial case, there is no top1-referenced list, and so top1 is assigned top2's value, which would be NULL if there was no top2-referenced list.

This operation has a time complexity of O(1) in the trivial case and a time complexity of O(n) otherwise. However, if you maintain a reference to the last node, there's no need to search the list for this node; the time complexity changes to O(1).

Inverting a singly linked list

Another useful operation on a singly linked list is inversion, which reverses the list's links to let you traverse its nodes in the opposite direction. The following pseudocode reverses the top1-referenced list's links:

 DECLARE Node p = top1 // Top of original singly linked list. DECLARE Node q = NULL // Top of reversed singly linked list. DECLARE Node r // Temporary Node reference variable. WHILE p NE NULL // For each Node in original singly linked list ... r = q // Save future successor Node's reference. q = p // Reference future predecessor Node. p = p.next // Reference next Node in original singly linked list. q.next = r // Link future predecessor Node to future successor Node. END WHILE top1 = q // Make top1 reference first Node in reversed singly linked list. END 

This operation has a time complexity of O(n).

Example #2: Concatenating and inverting a singly linked list

Creé una segunda versión de la SLLDemoaplicación Java que demuestra la concatenación y la inversión. El Listado 2 presenta el código fuente de esta aplicación.