Introducción al uso de listas vinculadas en Java

Aranzulla de Los Pobres

Una estructura de datos utiliza diferentes métodos predefinidos para almacenar, recuperar y eliminar datos que culminan en la creación de programas eficientes. Una lista vinculada es una estructura de datos popular, que consiste en una lista de nodos que están conectados (o vinculados).

Pero, ¿cómo se crea una lista vinculada en Java? Vamos a ver.

¿Cómo funciona una lista vinculada?

Cada lista vinculada comienza con un nodo especial que a menudo se denomina "cabeza", que tiene la responsabilidad de señalar el inicio de la lista en todo momento. La cabeza es importante porque cada nodo en una lista vinculada no necesita seguir físicamente a su sucesor (lo que significa que un predecesor y un sucesor no tienen que estar físicamente adyacentes).

Como toda estructura de datos, la lista enlazada facilita la creación, recuperación, inserción y destrucción a través de un conjunto de funciones predefinidas que pueden ser utilizadas por cualquier desarrollador.

Crear una lista vinculada en Java

Un programa Java diseñado para crear y manipular listas enlazadas tendrá tres secciones distintivas; la clase de nodo, la clase de lista vinculada y el controlador. Aunque estas tres secciones se pueden combinar en un archivo, existe un principio de diseño en ciencias de la computación conocido como "separación de preocupaciones" que todo desarrollador debería conocer.

El principio de separación de preocupaciones dicta que cada sección del código que aborde una preocupación específica debe estar separada. Este principio le ayudará a crear un código más limpio (más legible) y es ideal para crear estructuras de datos.

El primer paso para crear una lista vinculada en Java es crear una clase de nodo. Una clase de nodo debe tener dos atributos; uno de los atributos representará la parte de datos del nodo, mientras que el otro atributo representará la parte vinculada. Una clase de nodo también debe tener un constructor, captadores y definidores.

Relacionado: Aprenda a crear clases en Java

Los captadores y definidores permitirán que otras clases (como la clase de lista vinculada) accedan a los distintos nodos dentro de la lista vinculada.

Ejemplo de clase de nodo

A continuación se muestra un ejemplo de clase de nodo para que se haga una idea de lo que queremos decir:

 
public class Node {
 private int Data;
 private Node NextNode;
 //constructor
 public Node() {
 Data = 0;
 NextNode = null;
 }
 //getters and setters
 public int getData() {
 return Data;
 }
 public void setData(int data) {
 Data = data;
 }
 public Node getNextNode() {
 return NextNode;
 }
 public void setNextNode(Node nextNode) {
 NextNode = nextNode;
 }
 }

En este ejemplo, el atributo de datos almacenará valores enteros. Ahora que tiene la clase de nodo, es hora de pasar a la lista vinculada.

Ejemplo de lista vinculada

A continuación se muestra un ejemplo de una lista vinculada en Java.

 public class LinkedList {
 private Node Head;
 //constructor
 public LinkedList() {
 Head = null;
 }
 }

El código anterior creará una clase de lista vinculada, sin embargo, sin sus diversas operaciones, la clase puede verse como el equivalente de un shell vacío. La estructura de datos de la lista vinculada tiene varias operaciones que se pueden utilizar para completarla:

  • Insertar en la parte delantera.
  • Insertar en el medio.
  • Insertar en la espalda.

Relacionado: Cómo construir estructuras de datos con clases de JavaScript ES6

La colección de listas vinculadas de métodos de inserción es una de las razones por las que un desarrollador puede optar por usar esta estructura de datos sobre otra estructura de datos, como pilas (que solo permite la inserción y eliminación desde la parte superior).

Uso del método Insertar en el frente

El método de inserción en el frente, como sugiere el nombre, inserta nuevos datos (o nuevos nodos) al comienzo de la lista vinculada.

Ejemplo de método Insertar en el frente

A continuación se muestra un ejemplo de cómo insertaría datos nuevos al principio de su lista.

 //insert node at front method
 public void insertAtFront(int key) {
 //create a new node using the node class
 Node Temp = new Node();
 //check if the Temp node was successfully created
 //assign the data that was provides by the user to it
 if(Temp != null) {
 Temp.setData(key);
 Temp.setNextNode(null);

 //check if the head of the linked list is empty
 //assign the node that was just created to the head position
 if(Head == null) {
 Head = Temp;
 }
 //if a node is already at the head position
 //add the new node to it and set it as the head
 else {
 Temp.setNextNode(Head);
 Head = Temp;
 }
 }
 }

El método insertAtFront en el ejemplo anterior permite a un usuario agregar nuevos nodos a una lista vinculada determinada.

Aplicación del inserto en el ejemplo frontal

A continuación se muestra un ejemplo de cómo aplicaría el inserto en la parte delantera.

 public class Driver {
 //executes the program
 public static void main(String[] args) {
 //create a new linked list called List
 LinkedList List = new LinkedList();
 //add each value to the front of the linked list as a new node
 List.insertAtFront(10);
 List.insertAtFront(8);
 List.insertAtFront(6);
 List.insertAtFront(4);
 List.insertAtFront(2);
 }
 }

La clase Driver (que es el nombre que a menudo se asigna a la clase ejecutable en Java) utiliza la clase LinkedList para crear una lista vinculada de cinco números pares. Al mirar el código anterior, debería ser fácil ver que el número "2" está en la posición principal en la lista vinculada. Pero, ¿cómo puedes confirmar esto?

Uso del método Mostrar todos los nodos

El método de mostrar todos los nodos es un método de lista enlazada esencial. Sin él, un desarrollador no podrá ver los nodos en una lista vinculada. Viaja a través de la lista enlazada (empezando por la cabecera) imprimiendo los datos almacenados en cada nodo que forma la lista.

Ejemplo del método Mostrar todos los nodos

A continuación se muestra un ejemplo del uso del método de mostrar todas las notas en Java.

 //display all nodes method
 public void displayAllNodes() {
 //create a new node call Temp and assign it to the head of the linked list
 //if the head has a null value then the linked list is empty
 Node Temp = Head;
 if (Head == null){
 System.out.println("The list is empty.");
 return;
 }
 System.out.println("The List:");

 while(Temp != null) {
 //print the data in each node to the console(starting from the head)
 System.out.print(Temp.getData() + " ");
 Temp = Temp.getNextNode();
 }
 }

Ahora que se ha agregado el método displayAllNodes a la clase LinkedList , puede ver la lista vinculada agregando una sola línea de código a la clase del controlador.

Uso del ejemplo del método Mostrar todos los nodos

A continuación, verá cómo usaría el método de mostrar todos los nodos.

 //print the nodes in a linked list
 List.displayAllNodes();

La ejecución de la línea de código anterior producirá el siguiente resultado en la consola:

La lista:

 2 4 6 8 10

Uso del método de búsqueda de nodo

Habrá casos en los que un usuario querrá encontrar un nodo específico en una lista vinculada.

Por ejemplo, no sería práctico para un banco que tiene millones de clientes imprimir todos los clientes en su base de datos cuando solo necesitan ver los detalles de un cliente específico.

Por lo tanto, en lugar de usar el método displayAllNodes , un método más eficiente es encontrar el nodo único que contiene los datos requeridos. Esta es la razón por la que la búsqueda de un método de nodo único es importante en la estructura de datos de la lista vinculada.

Ejemplo de método de búsqueda de nodo

A continuación se muestra un ejemplo del uso del método de búsqueda de nodo.

 //search for a single node using a key
 public boolean findNode(int key) {
 //create a new node and place it at the head of the linked list
 Node Temp = Head;
 //while the current node is not empty
 //check if its data matches the key provided by the user
 while (Temp != null) {
 if (Temp.getData() == key) {
 System.out.println("The node is in the list");
 return true;
 }
 //move to the next node
 Temp = Temp.getNextNode();
 }
 //if the key was not found in the linked list
 System.out.println("The node is not in the list");
 return false;
 }

Con el método displayAllNodes , confirmó que LinkedList contiene 5 números pares del 2 al 10. El ejemplo de findNode anterior puede confirmar si uno de esos números pares es el número 4 simplemente llamando al método en la clase del controlador y proporcionando el número como un parámetro.

Uso del ejemplo del método Find Node

A continuación se muestra un ejemplo de cómo usaría el método de búsqueda de nodo en la práctica.

 //check if a node is in the linked list
 List.findNode(4);

El código anterior producirá el siguiente resultado en la consola:

 The node is in the list

Uso del método Eliminar un nodo

Utilizando el mismo ejemplo bancario anterior, un cliente de la base de datos del banco podría querer cerrar su cuenta. Aquí es donde resultará útil el método de eliminación de un nodo. Es el método de lista enlazada más complejo.

El método Delete a Node busca un nodo determinado, elimina ese nodo y vincula el nodo anterior al que sigue al nodo que se ha eliminado.

Ejemplo de eliminación de un método de nodo

A continuación se muestra un ejemplo del método de eliminación de un nodo.

 public void findAndDelete(int key) {
 Node Temp = Head;
 Node prev = null;
 //check if the head node holds the data
 //and delete it
 if (Temp != null && Temp.getData() == key) {
 Head = Temp.getNextNode();
 return;
 }
 //search the other nodes in the list
 //and delete it
 while (Temp != null) {
 if (Temp.getNextNode().getData() == key ) {
 prev = Temp.getNextNode().getNextNode();
 Temp.setNextNode(prev);
 return;
 }
 Temp = Temp.getNextNode();
 }
 }

Uso del ejemplo del método Eliminar un nodo

A continuación se muestra un ejemplo del uso del método de eliminación de un nodo en la práctica.

 //delete the node that holds the data 4
 List.findAndDelete(4);
 //print all nodes in the linked list
 List.displayAllNodes();

El uso de las dos líneas de código anteriores en la clase Driver preexistente producirá el siguiente resultado en la consola:

 The List:
 2 6 8 10

Ahora puede crear listas vinculadas en Java

Si llegó al final de este artículo del tutorial, habrá aprendido:

  • Cómo crear una clase de nodo.
  • Cómo crear una clase de lista vinculada.
  • Cómo poblar una clase de lista vinculada con sus métodos predefinidos.
  • Cómo crear una clase de controlador y usar los diferentes métodos de listas vinculadas para lograr el resultado deseado.

Una lista vinculada es solo una de las muchas estructuras de datos que puede utilizar para almacenar, recuperar y eliminar datos. Ya que tiene todo lo que necesita para comenzar, ¿por qué no prueba estos ejemplos usted mismo en Java?