0Pricing
Java Academy · Lección

Aspectos internos de LinkedList

Explore la estructura de nodos doblemente enlazados de LinkedList y sus características de complejidad temporal.

Aspectos internos de LinkedList es una lección gratuita de Java Academy en CoddyKit. Esta es la lección 1 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Java Academy, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Java Academy incluye 4 lecciones en total.

Aspectos internos de LinkedList

La LinkedList de Java es una lista doblemente enlazada: cada nodo contiene una referencia al nodo anterior y al siguiente, además del valor del elemento. A diferencia de ArrayList, no existe un array subyacente; la memoria se asigna por nodo.

class Node<T> {
    T data;
    Node<T> prev;
    Node<T> next;
    Node(T data) { this.data = data; }
}

Perfil de complejidad temporal

Las características de rendimiento de LinkedList difieren considerablemente de las de ArrayList:

  • addFirst / addLast: O(1)
  • get(index): O(n): debe recorrer la lista desde el principio o el final
  • remove(index): O(n) para encontrar el elemento y después O(1) para desvincularlo
  • Recorrido con Iterator: O(n)

Utilice LinkedList cuando necesite inserciones frecuentes al principio o al final, no acceso aleatorio.

Crear y recorrer una LinkedList

Crear una LinkedList e iterar sobre ella sigue la misma interfaz List que ya conoce. La diferencia está en la estructura interna.

import java.util.LinkedList;

LinkedList<String> list = new LinkedList<>();
list.add("Alice");
list.add("Bob");
list.add("Carol");

for (String name : list) {
    System.out.println(name);
}

System.out.println("First: " + list.getFirst()); // Alice
System.out.println("Last: "  + list.getLast());  // Carol

addFirst, addLast, removeFirst, removeLast

LinkedList ofrece operaciones sobre el principio y el final que ArrayList no proporciona de forma eficiente:

LinkedList<Integer> nums = new LinkedList<>();
nums.addLast(10);   // [10]
nums.addLast(20);   // [10, 20]
nums.addFirst(5);   // [5, 10, 20]

System.out.println(nums.removeFirst()); // 5  → [10, 20]
System.out.println(nums.removeLast());  // 20 → [10]

Desvinculación de nodos: eliminación O(1) tras encontrar el nodo

Una vez que tiene una referencia a un nodo (mediante un iterador), eliminarlo cuesta O(1), porque solo es necesario actualizar los punteros next/prev; no hay desplazamiento de elementos como en ArrayList.

import java.util.*;

LinkedList<String> tasks = new LinkedList<>(List.of("A","B","C","D"));
Iterator<String> it = tasks.iterator();
while (it.hasNext()) {
    String t = it.next();
    if (t.equals("B") || t.equals("D")) {
        it.remove(); // O(1) unlink
    }
}
System.out.println(tasks); // [A, C]

Sobrecarga de memoria frente a ArrayList

Cada nodo de LinkedList contiene dos referencias adicionales (prev, next), además de la referencia al elemento: aproximadamente 48 bytes por entrada en una JVM de 64 bits. ArrayList solo almacena la referencia al elemento (8 bytes) en un array contiguo.

Para conjuntos de datos grandes con muchas lecturas, ArrayList suele aprovechar mejor la caché y utilizar menos memoria.

Operaciones de Deque: pila y cola

LinkedList implementa la interfaz Deque, por lo que puede utilizarse tanto como pila como como cola.

import java.util.LinkedList;
import java.util.Deque;

// As a Queue (FIFO)
Deque<String> queue = new LinkedList<>();
queue.offer("first");
queue.offer("second");
System.out.println(queue.poll()); // first

// As a Stack (LIFO)
Deque<String> stack = new LinkedList<>();
stack.push("bottom");
stack.push("top");
System.out.println(stack.pop()); // top

Descripción general de PriorityQueue

PriorityQueue es una cola basada en un heap en la que el elemento menor, según el orden natural o un comparator, siempre se extrae primero. NO está respaldada por una lista enlazada: utiliza un array que representa un heap binario.

import java.util.PriorityQueue;

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(40);
pq.offer(10);
pq.offer(25);

System.out.println(pq.poll()); // 10 (smallest)
System.out.println(pq.poll()); // 25
System.out.println(pq.poll()); // 40

PriorityQueue con Comparator personalizado

Pase un Comparator para invertir el orden o para ordenar según un campo personalizado:

import java.util.*;

record Task(String name, int priority) {}

PriorityQueue<Task> tasks = new PriorityQueue<>(
    Comparator.comparingInt(Task::priority).reversed() // highest first
);
tasks.offer(new Task("Low", 1));
tasks.offer(new Task("High", 10));
tasks.offer(new Task("Med", 5));

while (!tasks.isEmpty()) {
    System.out.println(tasks.poll().name());
}
// High, Med, Low

Elegir entre LinkedList y ArrayList

Regla general:

  • Utilice ArrayList para el acceso aleatorio, la iteración y la mayoría de las situaciones.
  • Utilice LinkedList cuando necesite inserciones o eliminaciones frecuentes O(1) en ambos extremos y no necesite acceso por índice.
  • Utilice PriorityQueue cuando necesite un procesamiento ordenado, como en la programación de tareas o el algoritmo de Dijkstra.

Errores frecuentes

Evite llamar a get(i) dentro de un bucle sobre una LinkedList: el coste total es O(n²):

LinkedList<Integer> list = new LinkedList<>();
for (int i = 0; i < 10000; i++) list.add(i);

// BAD: O(n^2) — each get(i) traverses from head
for (int i = 0; i < list.size(); i++) {
    int val = list.get(i); // slow!
}

// GOOD: O(n) — use iterator
for (int val : list) {
    // process val
}

Comprobación rápida

¿Qué operación de LinkedList cuesta O(1) independientemente del tamaño de la lista?

Recapitulación: LinkedList y Deque

Aspectos clave:

  • LinkedList es una lista doblemente enlazada con operaciones O(1) en el principio y el final
  • El acceso aleatorio (get/set por índice) cuesta O(n)
  • Implementa Deque, por lo que puede utilizarse como pila o cola
  • PriorityQueue proporciona procesamiento ordenado mediante un heap
  • Prefiera ArrayList para la mayoría de los casos de uso; LinkedList destaca cuando se realizan modificaciones frecuentes en el principio o el final

Preguntas frecuentes

¿La lección «Aspectos internos de LinkedList» es gratis?

Sí — el texto completo de «Aspectos internos de LinkedList» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Java Academy, actualiza a CoddyKit PRO. El curso de Java Academy incluye 4 lecciones en total.

¿Qué aprenderé en «Aspectos internos de LinkedList»?

Explore la estructura de nodos doblemente enlazados de LinkedList y sus características de complejidad temporal. Practicas Java Academy con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.

¿Necesito experiencia previa para empezar Java Academy?

No se requiere experiencia previa. Java Academy en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 1 de 4.

¿Cuánto tiempo toma la lección «Aspectos internos de LinkedList»?

La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.

¿Puedo escribir y ejecutar código en esta lección de Java Academy?

Sí. Cada lección de Java Academy incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.

Todas las lecciones de este curso

  1. Aspectos internos de LinkedList
  2. Operaciones de Deque: pila y cola
  3. LinkedList frente a ArrayList: ventajas y desventajas
  4. PriorityQueue para el procesamiento ordenado
← Volver a Java Academy