Implementación de Lista Doblemente Enlazada en Java
El objetivo es modificar una lista enlazada simple para convertirla en una lista doblemente enlazada. Esta nueva estructura incluirá una referencia tanto a la cabeza (primer elemento) como a la cola (último elemento). Se implementarán las operaciones básicas como añadir, recorrer, buscar, insertar y borrar elementos.
Clase Nodo
Representa cada elemento individual dentro de la lista doblemente enlazada.
// Clase Nodo que representa cada elemento de la lista doblemente enlazada
class Nodo {
int dato; // Almacena el dato del nodo
Nodo siguiente; // Referencia al siguiente nodo de la lista
Nodo anterior; // Referencia al nodo anterior en la lista
// Constructor del nodo que inicializa el dato y las referencias a siguiente y anterior como null
public Nodo(int dato) {
this.dato = dato;
this.siguiente = null;
this.anterior = null;
}
}Clase MainListaDobleEnlazadaEnteros
Clase principal que gestiona la lógica y las operaciones de la lista doblemente enlazada.
public class MainListaDobleEnlazadaEnteros {
private Nodo cabeza; // Referencia al primer nodo de la lista (cabeza)
private Nodo cola; // Referencia al último nodo de la lista (cola)
// Constructor de la lista que inicializa la cabeza y la cola como null
public MainListaDobleEnlazadaEnteros() {
this.cabeza = null;
this.cola = null;
}
Método: Añadir al Final (aniadirAlFinal)
Añade un nuevo nodo con el dato especificado al final de la lista.
// Método para añadir un nodo al final de la lista
public void aniadirAlFinal(int dato) {
Nodo nuevoNodo = new Nodo(dato); // Creamos un nuevo nodo con el dato proporcionado
if (cabeza == null) {
// Si la lista está vacía, el nuevo nodo será tanto la cabeza como la cola
cabeza = nuevoNodo;
cola = nuevoNodo;
} else {
cola.siguiente = nuevoNodo; // El siguiente de la cola actual será el nuevo nodo
nuevoNodo.anterior = cola; // El anterior del nuevo nodo será la cola actual
cola = nuevoNodo; // La cola ahora será el nuevo nodo
}
}
Método: Añadir al Principio (aniadirAlPrincipio)
Añade un nuevo nodo con el dato especificado al inicio de la lista.
// Método para añadir un nodo al inicio de la lista
public void aniadirAlPrincipio(int dato) {
Nodo nuevoNodo = new Nodo(dato); // Creamos un nuevo nodo con el dato proporcionado
if (cabeza == null) {
// Si la lista está vacía, el nuevo nodo será tanto la cabeza como la cola
cabeza = nuevoNodo;
cola = nuevoNodo;
} else {
nuevoNodo.siguiente = cabeza; // El siguiente del nuevo nodo será la cabeza actual
cabeza.anterior = nuevoNodo; // El anterior de la cabeza será el nuevo nodo
cabeza = nuevoNodo; // La cabeza ahora será el nuevo nodo
}
}
Método: Recorrer Lista (recorrerLista)
Recorre la lista desde la cabeza hasta la cola e imprime los datos de cada nodo.
// Método para recorrer la lista e imprimir los datos de los nodos
public void recorrerLista() {
Nodo actual = cabeza; // Empezamos desde la cabeza
while (actual != null) { // Mientras no lleguemos al final de la lista
System.out.print(actual.dato + " "); // Imprimimos el dato del nodo actual
actual = actual.siguiente; // Nos movemos al siguiente nodo
}
System.out.println(); // Nueva línea después de imprimir toda la lista
}
Método: Verificar Existencia (existeElemento)
Comprueba si un elemento con el dato especificado existe en la lista.
// Método para verificar si un dato existe en la lista
public boolean existeElemento(int dato) {
Nodo actual = cabeza; // Empezamos desde la cabeza
while (actual != null) { // Recorremos toda la lista
if (actual.dato == dato) { // Si encontramos el dato
return true; // Retornamos true
}
actual = actual.siguiente; // Continuamos al siguiente nodo
}
return false; // Si no encontramos el dato, retornamos false
}
Método: Insertar Después De (insertaElementoDespuesDe)
Inserta un nuevo nodo con datoAInsertar inmediatamente después del primer nodo que contenga datoABuscar.
// Método para insertar un elemento después de un dato específico
public boolean insertaElementoDespuesDe(int datoABuscar, int datoAInsertar) {
Nodo actual = cabeza; // Empezamos desde la cabeza
while (actual != null) { // Recorremos la lista
if (actual.dato == datoABuscar) { // Si encontramos el dato que buscamos
Nodo nuevoNodo = new Nodo(datoAInsertar); // Creamos un nuevo nodo con el dato a insertar
nuevoNodo.siguiente = actual.siguiente; // El siguiente nodo del nuevo nodo será el que sigue al actual
if (actual.siguiente != null) {
actual.siguiente.anterior = nuevoNodo; // Si el nodo actual no es el último, el anterior del siguiente nodo será el nuevo nodo
} else {
cola = nuevoNodo; // Si el nodo actual es el último, el nuevo nodo será la cola
}
actual.siguiente = nuevoNodo; // Insertamos el nuevo nodo después del nodo actual
nuevoNodo.anterior = actual; // El anterior del nuevo nodo será el nodo actual
return true; // Retornamos true porque la inserción fue exitosa
}
actual = actual.siguiente; // Continuamos al siguiente nodo
}
return false; // Si no encontramos el datoABuscar, retornamos false
}
Método: Borrar Elemento (borraElemento)
Elimina el primer nodo que contenga el dato especificado.
// Método para borrar el primer elemento con el dato dado
public boolean borraElemento(int dato) {
if (cabeza == null) { // Si la lista está vacía, no se puede borrar nada
return false;
}
// Caso 1: El elemento a borrar está en la cabeza
if (cabeza.dato == dato) {
if (cabeza.siguiente != null) {
cabeza = cabeza.siguiente; // La cabeza ahora será el siguiente nodo
cabeza.anterior = null; // El anterior de la nueva cabeza será null
} else {
// Si solo hay un nodo, la lista quedará vacía
cabeza = null;
cola = null; // La cola también será null
}
return true;
}
// Caso 2: El elemento está en otro lugar (o no está)
Nodo actual = cabeza; // Empezamos desde la cabeza (ya sabemos que no es el primer nodo)
while (actual != null) { // Recorremos la lista
if (actual.dato == dato) { // Si encontramos el dato en el nodo actual
// Actualizar el enlace 'siguiente' del nodo anterior
if (actual.anterior != null) { // No debería ser null porque ya comprobamos la cabeza
actual.anterior.siguiente = actual.siguiente;
}
// Actualizar el enlace 'anterior' del nodo siguiente y la cola si es necesario
if (actual.siguiente != null) {
actual.siguiente.anterior = actual.anterior;
} else {
// Si el nodo actual es la cola, actualizamos la cola
cola = actual.anterior;
}
// No es necesario actualizar la cabeza aquí porque ya se manejó el caso 1
return true; // Retornamos true porque la eliminación fue exitosa
}
actual = actual.siguiente; // Continuamos al siguiente nodo
}
return false; // Si no encontramos el dato, retornamos false
}
Ejemplo de Uso (Método main)
Demostración de cómo utilizar la clase MainListaDobleEnlazadaEnteros y sus métodos.
// Método principal para probar la lista doblemente enlazada
public static void main(String[] args) {
MainListaDobleEnlazadaEnteros lista = new MainListaDobleEnlazadaEnteros(); // Creamos una nueva lista doblemente enlazada
lista.aniadirAlFinal(10); // Añadimos un nodo con valor 10 al final
lista.aniadirAlFinal(20); // Añadimos un nodo con valor 20 al final
lista.aniadirAlPrincipio(5); // Añadimos un nodo con valor 5 al principio
System.out.print("Lista actual: ");
lista.recorrerLista(); // Imprime: 5 10 20
System.out.println("¿Existe el 10? " + lista.existeElemento(10)); // Imprime: true
System.out.println("¿Existe el 15? " + lista.existeElemento(15)); // Imprime: false
System.out.println("Insertando 15 después del 10...");
lista.insertaElementoDespuesDe(10, 15); // Inserta 15 después del 10
System.out.print("Lista después de insertar: ");
lista.recorrerLista(); // Imprime: 5 10 15 20
System.out.println("Borrando el 10...");
lista.borraElemento(10); // Borra el nodo con valor 10
System.out.print("Lista después de borrar: ");
lista.recorrerLista(); // Imprime: 5 15 20
}
} // Fin de la clase MainListaDobleEnlazadaEnteros