La clase LinkedList en Java representa una implementación de lista doblemente enlazada. A diferencia de ArrayList, no utiliza un array interno para almacenar elementos, lo que le otorga características únicas en términos de rendimiento para operaciones de inserción y eliminación.

Esta estructura implementa múltiples interfaces, lo que define su versatilidad:

• List: Permite el manejo de secuencias ordenadas de elementos.
• Deque: Proporciona capacidades de cola de doble extremo, permitiendo su uso como pila (stack) o cola (queue).
• Cloneable y Serializable: Soporta clonación superficial y persistencia de datos.

### Componentes Básicos y Atributos

Internamente, LinkedList gestiona tres campos principales que definen el estado de la lista:

// Número de elementos en la lista
transient int totalElements = 0;

// Referencia al primer nodo
transient Nodo<E> head;

// Referencia al último nodo
transient Nodo<E> tail;

Cada elemento se encapsula en una clase estática interna llamada Node. Cada nodo conoce tanto al elemento siguiente como al anterior, facilitando la navegación bidireccional.

private static class Nodo<E> {
   E valor;
   Nodo<E> siguiente;
   Nodo<E> anterior;

   Nodo(Nodo<E> anterior, E elemento, Nodo<E> siguiente) {
       this.valor = elemento;
       this.siguiente = siguiente;
       this.anterior = anterior;
   }
}

Búsqueda Optimizada por Índice

Aunque el acceso aleatorio no es el fuerte de las listas enlazadas (O(n)), Java optimiza la búsqueda verificando si el índice solicitado está más cerca del inicio o del final de la lista.

Nodo<E> buscarNodo(int indice) {
   // Si el índice está en la primera mitad, recorremos desde el inicio
   if (indice < (totalElements >> 1)) {
       Nodo<E> puntero = head;
       for (int i = 0; i < indice; i++)
           puntero = puntero.siguiente;
       return puntero;
   } else {
       // Si está en la segunda mitad, recorremos hacia atrás desde el final
       Nodo<E> puntero = tail;
       for (int i = totalElements - 1; i > indice; i--)
           puntero = puntero.anterior;
       return puntero;
   }
}

Operaciones de Inserción (Link)

La inserción consiste en reconfigurar los punteros de los nodos adyacentes. El método linkLast es el más común, utilizado por el método add() estándar.

void enlazarAlFinal(E dato) {
   final Nodo<E> ultimo = tail;
   final Nodo<E> nuevoNodo = new Nodo<>(ultimo, dato, null);
   tail = nuevoNodo;
   
   if (ultimo == null)
       head = nuevoNodo;
   else
       ultimo.siguiente = nuevoNodo;
   
   totalElements++;
   modCount++;
}

Operaciones de Eliminación (Unlink)

Para eliminar un nodo, LinkedList desconecta el nodo del flujo de la lista y ajusta las referencias de sus vecinos. Es crucial anular las referencias internas del nodo eliminado para facilitar el trabajo del Recolector de Basura (GC).

E desenlazarNodo(Nodo<E> objetivo) {
   final E elemento = objetivo.valor;
   final Nodo<E> prox = objetivo.siguiente;
   final Nodo<E> prev = objetivo.anterior;

   if (prev == null) {
       head = prox;
   } else {
       prev.siguiente = prox;
       objetivo.anterior = null;
   }

   if (prox == null) {
       tail = prev;
   } else {
       prox.anterior = prev;
       objetivo.siguiente = null;
   }

   objetivo.valor = null; // Ayuda al GC
   totalElements--;
   modCount++;
   return elemento;
}

Funcionalidad de Pila y Cola

Gracias a la interfaz Deque, podemos realizar operaciones eficientes en los extremos sin necesidad de recorrer la lista completa.

• push(E e): Inserta al principio (comportamiento de pila).
• pop(): Elimina y retorna el primer elemento.
• peek(): Observa el primer elemento sin eliminarlo.

Consideraciones de Rendimiento y Uso

Al analizar la estructura de LinkedList, podemos extraer las siguientes conclusiones técnicas:

1. Eficiencia en Modificaciones: Las operaciones de añadir o quitar elementos en los extremos tienen una complejidad de O(1). Insertar en una posición específica requiere O(n) para localizar el nodo, pero la inserción física es O(1).
2. Consumo de Memoria: Es mayor que en ArrayList, ya que cada elemento requiere un objeto Node adicional que almacena dos referencias (siguiente y anterior).
3. Sincronización: Esta implemantación no es segura para hilos (not thread-safe). En entornos concurrentes, debe externalizarse la sincronización o usar Collections.synchronizedList.
4. Acceso: No soporta acceso aleatorio rápido. Si la aplicación requiere consultas frecuentes por índice, ArrayList es una mejor opción.