Introducción al uso de listas vinculadas en Java

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.

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.

Un programa Java que está 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.

Relacionada: 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:

Nodo de clase pública {
datos privados int;
Próximo nodo de nodo privado;
//constructor
nodo público () {
Datos = 0;
NextNode = null;
}
// getters y setters
public int getData () {
devolver datos;
}
public void setData (int data) {
Datos = datos;
}
public Node getNextNode () {
return NextNode;
}
public void setNextNode (Nodo 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.

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

public class LinkedList {
jefe de nodo privado;
//constructor
public LinkedList () {
Cabeza = nulo;
}
}

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.

Relacionada: 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 utilizar estos datos. estructura 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 de inserción en el frente

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

 // insertar nodo en el método frontal
public void insertAtFront (clave int) {
// crea un nuevo nodo usando la clase de nodo
Node Temp = new Node ();
// verifica si el nodo Temp se creó correctamente
// asignarle los datos que le proporcionó el usuario
if (Temp! = null) {
Temp.setData (clave);
Temp.setNextNode (nulo);
// comprobar si el encabezado de la lista enlazada está vacío
// asigna el nodo que se acaba de crear a la posición de la cabeza
if (Head == null) {
Cabeza = Temp;
}
// si un nodo ya está en la posición de la cabeza
// agregue el nuevo nodo y configúrelo como el encabezado
demás {
Temp.setNextNode (Head);
Cabeza = Temp;
}
}
}

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

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.

Conductor de clase pública {
// ejecuta el programa
public static void main (String [] args) {
// crea una nueva lista vinculada llamada Lista
LinkedList List = new LinkedList ();
// agrega cada valor al frente de la lista vinculada como un nuevo nodo
List.insertAtFront (10);
List.insertAtFront (8);
List.insertAtFront (6);
List.insertAtFront (4);
List.insertAtFront (2);
}
}

El Conductor class (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.

// muestra el método de todos los nodos
public void displayAllNodes () {
// crea un nuevo nodo llamado Temp y lo asigna al encabezado de la lista enlazada
// si el encabezado tiene un valor nulo, entonces la lista vinculada está vacía
Temp del nodo = Cabeza;
if (Head == null) {
System.out.println ("La lista está vacía.");
regresar;
}
System.out.println ("La Lista:");
while (Temp! = null) {
// imprime los datos de cada nodo en la consola (empezando por la cabeza)
System.out.print (Temp.getData () + "");
Temp = Temp.getNextNode ();
} 
}

Ahora que el displayAllNodes se ha agregado al método Lista enlazada class, 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.

// imprime los nodos en una lista vinculada
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 utilizar el displayAllNodes método, un método más eficiente es encontrar el único nodo 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.

// busca un solo nodo usando una clave
findNode booleano público (clave int) {
// crea un nuevo nodo y colócalo al principio de la lista enlazada
Temp del nodo = Cabeza;
// mientras el nodo actual no esté vacío
// verifica si sus datos coinciden con la clave proporcionada por el usuario
while (Temp! = null) {
if (Temp.getData () == clave) {
System.out.println ("El nodo está en la lista"); 
devuelve verdadero;
}
// pasar al siguiente nodo
Temp = Temp.getNextNode ();
}
// si la clave no se encontró en la lista vinculada
System.out.println ("El nodo no está en la lista"); 
falso retorno;
}

Con el displayAllNodes método, confirmó que el Lista enlazada contiene 5 números pares del 2 al 10. El findNode El ejemplo 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 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.

// verifica si un nodo está en la lista vinculada
List.findNode (4);

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

El nodo está en la lista

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) { 
Temp del nodo = Cabeza; 
Nodo prev = null; 
// verifica si el nodo principal contiene los datos 
// y bórralo 
if (Temp! = null && Temp.getData () == key) { 
Head = Temp.getNextNode (); 
regresar; 
} 
// busca los otros nodos en la lista 
// y bórralo 
while (Temp! = null) { 
if (Temp.getNextNode (). getData () == clave) { 
prev = Temp.getNextNode (). getNextNode (); 
Temp.setNextNode (anterior); 
regresar; 
} 
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.

// elimina el nodo que contiene los datos 4
List.findAndDelete (4);
// imprime todos los nodos en la lista vinculada
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:

La lista:
2 6 8 10

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?

Cómo crear y realizar operaciones en matrices en Java

¿Aprendiendo Java? Deje que las matrices manejen sus datos con facilidad.

Leer siguiente

Sobre el Autor