Conceptos de Almacenamiento Enlazado

Dentro de las estructuras de datos lineales, el almacenamiento puede gestionarse de forma secuencial o mediante enlaces. Las listas enlazadas pertenecen a la segunda categoría, donde los elementos (nodos) no requieren posiciones de memoria contiguas. Cada nodo actúa como una unidad que contiene información y una referencia al siguiente elemento de la secuencia.

Imagina una búsqueda de tesoro donde cada pista te indica la ubicación de la siguiente. En términos técnicos, un nodo se compone de:

• Campo de datos: Almacena el valor o la información del elemento.
• Campo de puntero: Almacena la dirección de memoria del nodo consecutivo.

Estructura de una Lista Simplemente Enlazada

En una lista simplemente enlazada, cada nodo tiene un único enlace que apunta al sucesor. Es fundamental distinguir tres componentes clave:

• Puntero de cabeecra: El punto de entrada a la lista.
• Nodo de cabecera: Un nodo opcional al inicio que no suele contener datos relevantes, utilizado para simplificar operaciones.
• Nodo inicial: El primer nodo que contiene datos reales de la lista.

Construcción de la Lista en Java

Para implementar esta estructura, primero definimos la clase base para el nodo:

public class NodoLista {
    public int contenido;
    public NodoLista siguiente;

    public NodoLista(int contenido) {
        this.contenido = contenido;
        this.siguiente = null;
    }
}

Inserción por la Cabecera (Head Insertion)

Este método añade elementos al inicio de la lista. Cada nuevo elemento se convierte en el primer nodo real, desplazando a los existentes hacia atrás. La lógica central consiste en asignar el puntero actual de la cabecera al nuevo nodo y luego actualizar la cabecera.

public static NodoLista construirAlInicio(NodoLista referenciaBase, int cantidad) {
    for (int i = 1; i <= cantidad; i++) {
        NodoLista nuevoElem = new NodoLista(i);
        // El nuevo nodo apunta a lo que antes era el primero
        nuevoElem.siguiente = referenciaBase.siguiente;
        // La cabecera ahora apunta al nuevo nodo
        referenciaBase.siguiente = nuevoElem;
    }
    return referenciaBase;
}

Inserción por el Final (Tail Insertion)

En este enfoque, los elementos se añaden al término de la lista, manteniendo el orden de inserción original. Para optimizar el proceso, se suele utilizar un puntero auxilair que rastree siempre el último nodo.

public static NodoLista construirAlFinal(NodoLista cabecera, int limite) {
    NodoLista punteroUltimo = cabecera;
    for (int i = 1; i <= limite; i++) {
        NodoLista temporal = new NodoLista(i);
        // Conectar el último actual con el nuevo
        punteroUltimo.siguiente = temporal;
        // Mover el rastreador al nuevo final
        punteroUltimo = temporal;
    }
    return cabecera;
}

Operaciones de Eliminación

Borrar un nodo implica reestructurar los enlaces para "saltar" el elemento que se desea descartar.

Eliminar por Índice

Para eliminar el nodo en la posición n, debemos localizar el nodo en la posición n-1. Una vez situado allí, cambiamos su puntero para que apunte al nodo n+1.

public static void removerPorPosicion(NodoLista inicio, int posicion) {
    NodoLista cursor = inicio;
    int contador = 0;

    // Localizar el nodo previo al que queremos borrar
    while (cursor.siguiente != null && contador < posicion - 1) {
        cursor = cursor.siguiente;
        contador++;
    }

    if (cursor.siguiente != null) {
        // Bypass del nodo objetivo
        cursor.siguiente = cursor.siguiente.siguiente;
    }
}

Eliminar por Valor Específico

Si conocemos el valor pero no la posición, recorremos la lista buscando la coincidencia. Una técnica avanzada para borrar un nodo intermedio (si tenemos acceso directo a él) es copiar el valor del siguiente nodo al actual y luego eliminar el siguiente.

public void borrarNodoDirecto(NodoLista objetivo) {
    if (objetivo == null || objetivo.siguiente == null) return;
    // Sobrescribir datos y saltar el siguiente
    objetivo.contenido = objetivo.siguiente.contenido;
    objetivo.siguiente = objetivo.siguiente.siguiente;
}

Búsqueda y Recorrido

A diferencia de los arreglos, el acceso no es aleatorio sino secuencial. Para encontrar un elemento, debemos iterar desde la cabecera hasta hallar el índice o valor deseado.

public static NodoLista buscarElemento(NodoLista inicio, int indice) {
    NodoLista actual = inicio.siguiente;
    int posActual = 1;

    while (actual != null) {
        if (posActual == indice) {
            return actual;
        }
        actual = actual.siguiente;
        posActual++;
    }
    return null;
}

public static int calcularLongitud(NodoLista cabecera) {
    int total = 0;
    NodoLista temp = cabecera.siguiente;
    while (temp != null) {
        total++;
        temp = temp.siguiente;
    }
    return total;
}

Consideraciones Técnicas

Las listas simplemente enlazadas ofrecen una eficiencia superior en operaciones de inserción y eliminación (O(1) si se tiene el puntero al nodo previo) en comparación con las estructuras secuenciales que requieren desplazar elementos. Sin embargo, su principal desventaja es el tiempo de búsqueda (O(n)) y el uso adicional de memoria por cada puntero almacenado.