Java es un lenguaje que posee una extensa variedad de clases, entre ellas podemos encontrar las famosas colecciones de estructuras, mismas que están compuestas por listas enlazadas, pilas entre otras; lo cual si bien es cierto cumplen con todo lo que necesitamos a la hora de programar, no son validas para realizar las asignaturas en cursos universitarios o de técnicos en programación, en los cuales se prioriza el entendimiento sobre como funcionan estás estructuras de datos. Por todo lo anterior, hoy les traigo un tutorial sobre listas enlazadas, en el cual cubriré los conceptos básicos, como se construyen (a «mano») y por supuesto, como usarlas en una aplicación.
¿Qué es una lista enlazada?
Podemos decir que una lista enlazada no es otra cosa que una cadena, en la cual cada uno de sus elementos está enlazado al siguiente mediante una conexión, en nuestra caso una dirección de memoria.
Pero vamos un poco más despacio, pensemos en una cadena común, de esas que se utilizan para asegurar portones, vemos en ella un conjunto de elementos conectados llamados eslabones, dichos eslabones son los que conforman la cadena y si uno de ellos pierde su conexión con el siguiente, entonces la cadena se rompe; de igual forma en una lista enlazada, cada eslabón (llamado nodo, tradicionalmente) está conectado al siguiente y es este conjunto de nodos son los que conforman la lista, si uno de ellos pierde su conexión con el siguiente, entonces jamás podremos acceder a los nodos posteriores.
¿Qué elementos conforman una lista enlazada?
Como mencioné recién, una lista enlazada está compuesta por eslabones llamados nodos, estos nodos están conectados mediante referencias a direcciones de memoria, pero debemos hablar sobre un eslabón muy importante, el primero que conforma la lista, hace poco dije que si un nodo pierde su conexión con el siguiente entonces sería imposible acceder a los nodos posteriores, por lo tanto y por sentido común, notamos que si se pierde la dirección del primer elemento, la lista completa quedará inaccesible, así que el nodo más importante en nuestra lista es sin lugar a dudas el primero que la conforma.
A su vez, cada nodo está conformado por dos partes, la primera llamada parte de datos es la que permite almacenar lo que el programador desea guardar, por ejemplo un String, un Int, e inclusive una clase, y la segunda la dirección de memoria de la que tanto he hablado.
Ahora bien, para crear un nodo necesitamos crear una clase que contenga estos dos elementos y luego naturalmente un objeto para manipular la lista.
¿Qué operaciones se pueden realizar sobre una lista enlazada?
Las operaciones básicas en una lista son 4:
- Insertar un elemento
- Mostrar la lista completa
- Buscar y (mostrar o modificar) un elemento
- Eliminar un elemento
Manos a la obra:
En este tutorial veremos las dos primeras operaciones, Insertar un elemento y Mostrar el contenido de la lista, pero antes de pasar al código necesitamos entender el fundamento de cada operación.
Insertar un elemento en una lista enlazada:
Para insertar un elemento dentro de una lista enlaza, primero debemos entender que sucede con la lista, es decir, requerimos conocer el estado de la lista (si está vacía o por el contrario si posee elementos).
En caso de que la lista esté vacía procederemos de la siguiente manera:
- ElementoaInsertar.siguiente = nada
- PrimerElemento = ElementoaInsertar
Como notamos en la imagen, el primer elemento en realidad es una referencia y no un nodo como tal, en otras palabras, no contiene una parte de datos, pues su propósito como mencioné antes, es el de mantener la referencia de memoria para acceder a los nodos posteriores. Si se quiere puede tomarse al primer elemento como un nodo sin su parte de datos.
En caso de que la lista sí contenga elementos, entonces se procede como sigue:
Necesitamos establecer si vamos a insertar al inicio de la lista o al final, la diferencia radica en el orden que se apilan los nodos, de modo que si escogemos insertar al inicio, el último nodo insertado será el primero en ser recorrido (mostrado) mientras que si insertamos al final de la lista, mantendríamos cierto orden lógico.
Insertar al inicio de la lista:
- ElementoaInsertar.siguiente = primerElemento
- primerElemento = ElementoaInsertar
La imagen nos dice lo siguiente: Toma el nodo a insertar y haz que su parte de dirección apunte hacía donde apunta el primer elemento, esto con el propósito de enganchar el nuevo elemento a la lista. Segundo, toma el primer elemento y colócalo apuntando a la dirección de nuevo elemento, con esto logramos actualizar el valor de dirección del primer elemento que se colocaría en apuntando al nodo recién insertado.
Ahora que entendemos los conceptos de inserción procedemos a ver un poco del código en Java.
Primero necesitamos crear una clase Nodo, en la cual procedemos a declarar dos atributos, uno del mismo tipo de la clase, que será en el que guardemos la dirección de memoria, y el otro del tipo de dato deseado, ya sea un tipo primitivo o una clase.
public class Nodo{
int numero;
Nodo siguiente;
public Nodo (int nuevoNumero){
this.numero = nuevoNumero;
this.siguiente = null;
}
}
Posteriormente creamos una clase con los métodos de la lista, primeramente el de insertar, luego el de mostrar; es importante aclarar que estas dos clases deben ir en el mismo paquete de Java, por lógica y por comodidad.
public class Lista{
Nodo primerElemento;
public Lista(){
this.primerElemento = null;
}
public void insertar(int nuevoNumero){
Nodo nuevoElemento = new Nodo(nuevoNumero);
if (primerElemento == null){
nuevoElemento.siguiente = null;
primerElemento = nuevoElemento;
}
else{
nuevoElemento.siguiente = primerElemento;
primerElemento = nuevoElemento;
}
}
}
Repasando de nuevo los elementos de esta clase:
El constructor de la clase Lista es llamado cuando se crea el objeto en cualquier otra parte del código para el usuario, dicho constructor es usado una vez para crear una instancia de la lista, por lo tanto en ese momento el primer elemento se inicializa en null, luego cuando el dato es obtenido del usuario y se desea insertar en la lista, se llama al método insertar, seguidamente se verifica si la lista está vacía, si lo está, entonces ejecuta el código del IF, en caso contrario, ejecuta el código del Else, ambos códigos ya fueron explicados conceptualmente por lo que no debería ser nada complicado entenderlos.
Bien, ahora vamos a implementar nuestro código para ver que todo funcione correctamente, para ello escribimos una clase main en la cual instanciaremos un objeto de tipo Lista, que utilice el método insertar de dicha clase:
import javax.swing.JOptionPane;
public class Main {
public static void main (String args[]) {
Lista nuevaLista = new Lista();
String opcion = "";
while(!opcion.equals("3")){
nuevaLista.insertar(Integer.parseInt(JOptionPane.showInputDialog(null,"Escriba un número")));
opcion = JOptionPane.showInputDialog(null, "Escriba 3 para salir, o cualquiera para continuar");
}
}
}
Esta clase Main es bastante sencilla, su finalidad es la de crear un objeto para poder utilizar el método insertar de la clase Lista, para lo cual se vale de un while que ejecuta el código dentro de el mientras se cumpla la condición establecida, opción distinta de 3.
Note como no necesitamos importar la clase Lista, más arriba mencioné que por comodidad nos convenía colocar todo en el mismo paquete Java, pues bien, esta es una de las razones; en caso contrario si lo hubiéramos colocado en un paquete distinto, entonces por obligación tendríamos que declarar el import.
Mostrar los elementos de la lista:
Bien el procedimiento para mostrar los datos almacenados en una lista enlazada es muy simple, basta con recorrer cada uno de sus elementos mientras no sea igual a Null, es decir, vacío.
A su vez para cada elemento recorrido mostraremos su valor y lo concatenaremos con el resto.
Definamos el método mostrar en la clase Lista:
public String mostrar(){
Nodo auxiliar = primerElemento;
String numeros = "";
while(auxiliar != null){
numeros += auxiliar.numero;
auxiliar = auxiliar.siguiente;
}
return numeros;
}
Lo que hace este método es concatenar cada elemento de la lista en un String llamado números, para posteriormente ser retornado al objeto que lo invoca dentro de la clase main.
Vemos que, Auxiliar nos permite iniciar desde la posición uno e ir efectuando el recorrido mientras no se haya llegado al final de la lista, mismo que está indicado por NULL; como ven es muy simple.
Para utilizarlo basta con crear un objeto JOptionPane dentro de main y mandarle los valores de retorno del método:
JOptionPane.showMessageDialog(null,nuevaLista.mostrar());
Esta última porción de código la debemos colocar fuera del While presente en la clase Main, puesto que así se ejecutará cuando se haya terminado de definir la lista.
Este ha sido el primer tutorial sobre listas enlazadas espero les sea de ayuda; ante cualquier duda o inconveniente no duden en comentar. Saludos y un abrazo.
Diariodebian 