Lista enlazada en Java

Problema

La cola que frena el envío

El servidor envía correos desde una cola. Los nuevos entran por detrás, los urgentes (un restablecimiento de contraseña) por delante, y el proceso de envío toma siempre el primero. El código usa la lista normal:

List<String> emails = new ArrayList<>();
emails.add("factura");
emails.add("boletín");
emails.add("informe");
emails.add(0, "contraseña");
String next = emails.remove(0);
System.out.println("Enviando: " + next);
System.out.println("Quedan: " + emails);

Enviando: contraseña
Quedan: [factura, boletín, informe]

El lunes por la mañana, el boletín para todos los clientes llena la cola con 100 000 correos. El proceso envía más despacio que de costumbre, luego casi se detiene, y los correos de restablecimiento de contraseña llegan con minutos de retraso.

La causa: la lista es un arreglo dinámico. Sacar el primero mueve todos los demás un lugar hacia delante, y uno urgente al principio los mueve todos hacia atrás. Enviar 100 000 correos uno tras otro son 99 999 + 99 998 + … + 1 = 4 999 950 000 movimientos, solo para sacar el primero.

La idea

Nodos, head y tail

El nodo y la inserción al principio ya los viste en la lección «Pila, cola y lista enlazada»: cada elemento es un objeto aparte con un valor y una flecha next al siguiente. Aquí escribes la clase entera y calculas cuánto cuesta cada operación.

La lista guarda tres cosas:

head: el primer nodo. Todo recorrido empieza ahí.
tail: el último nodo. Con él, añadir al final no recorre toda la lista.
el tamaño, para no contarlo cada vez.

Los dos extremos tienen que ser correctos después de cada operación. La lista vacía tiene head y tail iguales a null. Una lista con un nodo tiene head y tail apuntando al mismo nodo. Casi todo error en una lista enlazada es un extremo olvidado: quitas el último, y tail sigue apuntando a él.

Míralo

Tu propia lista enlazada

Aquí está la clase entera. Los nodos no se mueven nunca: cada operación cambia solo flechas.

class Node {
    String value;
    Node next;

    Node(String value) {
        this.value = value;
    }
}

class SimpleLinkedList {
    private Node head;
    private Node tail;
    private int size;

    int size() {
        return size;
    }

    void addFirst(String value) {
        Node node = new Node(value);
        node.next = head;
        head = node;
        if (tail == null) {
            tail = node;
        }
        size++;
    }

    void addLast(String value) {
        Node node = new Node(value);
        if (tail == null) {
            head = node;
        } else {
            tail.next = node;
        }
        tail = node;
        size++;
    }

    String removeFirst() {
        if (head == null) {
            throw new NoSuchElementException("la lista está vacía");
        }
        String value = head.value;
        head = head.next;
        if (head == null) {
            tail = null;
        }
        size--;
        return value;
    }

    boolean remove(String value) {
        Node prev = null;
        Node n = head;
        while (n != null && !n.value.equals(value)) {
            prev = n;
            n = n.next;
        }
        if (n == null) {
            return false;
        }
        if (prev == null) {
            head = n.next;
        } else {
            prev.next = n.next;
        }
        if (n == tail) {
            tail = prev;
        }
        size--;
        return true;
    }

    int find(String value) {
        int index = 0;
        for (Node n = head; n != null; n = n.next) {
            if (n.value.equals(value)) {
                return index;
            }
            index++;
        }
        return -1;
    }

    String get(int index) {
        Objects.checkIndex(index, size);
        Node n = head;
        for (int i = 0; i < index; i++) {
            n = n.next;
        }
        return n.value;
    }

    @Override
    public String toString() {
        List<String> values = new ArrayList<>();
        for (Node n = head; n != null; n = n.next) {
            values.add(n.value);
        }
        return String.join(" → ", values);
    }
}

Mira qué flechas cambian en cada operación:

class Node {
    String value;
    Node next;

    Node(String value) {
        this.value = value;
    }
}

private Node head;
private Node tail;
private int size;

String removeFirst() {
    if (head == null) {
        throw new NoSuchElementException("la lista está vacía");
    }
    String value = head.value;
    head = head.next;
    if (head == null) {
        tail = null;
    }
    size--;
    return value;
}

boolean remove(String value) {
    Node prev = null;
    Node n = head;
    while (n != null && !n.value.equals(value)) {
        prev = n;
        n = n.next;
    }
    if (n == null) {
        return false;
    }
    if (prev == null) {
        head = n.next;
    } else {
        prev.next = n.next;
    }
    if (n == tail) {
        tail = prev;
    }
    size--;
    return true;
}

Paso a paso, en palabras

Tres correos, cada uno en su propio nodo: el valor y next, la flecha al siguiente. head apunta al primero, tail al último.
addFirst(«contraseña»): un nodo nuevo, su next apunta al antiguo primero, y head pasa a él. Dos flechas, nada se mueve: O(1).
addLast(«invitación»): tail ya conoce al último, así que no se recorre nada. Su next apunta al nodo nuevo, y tail se mueve: O(1).
removeFirst(): head pasa al nodo siguiente. Ya nada apunta a «contraseña», y su memoria se libera sola.
remove(«boletín»): los nodos no tienen índice. n parte de head y avanza hasta encontrarlo; prev se queda un nodo atrás. Eso es O(n).
prev.next = n.next: una flecha rodea «boletín». «informe» y «invitación» no se mueven.
En los extremos: dos flechas, O(1). En el medio: una flecha, pero a ese lugar se llega paso a paso, O(n).

SimpleLinkedList emails = new SimpleLinkedList();
emails.addLast("factura");
emails.addLast("boletín");
emails.addLast("informe");
emails.addFirst("contraseña");
emails.addLast("invitación");
System.out.println(emails);
System.out.println("Enviando: " + emails.removeFirst());
emails.remove("boletín");
System.out.println(emails);
System.out.println("Posición del informe: " + emails.find("informe"));
System.out.println("Correos: " + emails.size());

contraseña → factura → boletín → informe → invitación
Enviando: contraseña
factura → informe → invitación
Posición del informe: 1
Correos: 3

removeFirst en una lista vacía lanza NoSuchElementException, como LinkedList.removeFirst. El método toString con @Override es lo que imprime System.out.println(emails).

Pruébalo

Predice la salida

Siete operaciones seguidas. Fíjate cuál es el último después de quitar:

class Node {
    String value;
    Node next;

    Node(String value) {
        this.value = value;
    }
}

class SimpleLinkedList {
    private Node head;
    private Node tail;
    private int size;

    int size() {
        return size;
    }

    void addFirst(String value) {
        Node node = new Node(value);
        node.next = head;
        head = node;
        if (tail == null) {
            tail = node;
        }
        size++;
    }

    void addLast(String value) {
        Node node = new Node(value);
        if (tail == null) {
            head = node;
        } else {
            tail.next = node;
        }
        tail = node;
        size++;
    }

    String removeFirst() {
        if (head == null) {
            throw new NoSuchElementException("la lista está vacía");
        }
        String value = head.value;
        head = head.next;
        if (head == null) {
            tail = null;
        }
        size--;
        return value;
    }

    boolean remove(String value) {
        Node prev = null;
        Node n = head;
        while (n != null && !n.value.equals(value)) {
            prev = n;
            n = n.next;
        }
        if (n == null) {
            return false;
        }
        if (prev == null) {
            head = n.next;
        } else {
            prev.next = n.next;
        }
        if (n == tail) {
            tail = prev;
        }
        size--;
        return true;
    }

    int find(String value) {
        int index = 0;
        for (Node n = head; n != null; n = n.next) {
            if (n.value.equals(value)) {
                return index;
            }
            index++;
        }
        return -1;
    }

    String get(int index) {
        Objects.checkIndex(index, size);
        Node n = head;
        for (int i = 0; i < index; i++) {
            n = n.next;
        }
        return n.value;
    }

    @Override
    public String toString() {
        List<String> values = new ArrayList<>();
        for (Node n = head; n != null; n = n.next) {
            values.add(n.value);
        }
        return String.join(" → ", values);
    }
}

SimpleLinkedList emails = new SimpleLinkedList();
emails.addFirst("informe");
emails.addFirst("factura");
emails.addLast("invitación");
emails.removeFirst();
emails.addFirst("contraseña");
emails.remove("invitación");
emails.addLast("boletín");
System.out.println(emails);
System.out.println("Correos: " + emails.size());

Respuesta

contraseña → informe → boletín
Correos: 3

contraseña → informe
Correos: 3

contraseña → informe → invitación → boletín
Correos: 4

La idea

Qué cuesta qué: arreglo contra lista enlazada

Operación	Arreglo dinámico	Lista enlazada
leer por índice	O(1)	O(n)
añadir al principio	O(n)	O(1)
añadir al final	O(1) amortizado	O(1) con tail
quitar el primero	O(n)	O(1)
quitar el último	O(1)	O(n), doblemente enlazada: O(1)
en el medio	O(n): mover	O(n): caminar hasta el lugar

La última fila es la trampa. Reenlazar en el medio es O(1) por sí solo, pero al lugar llegas desde head, paso a paso. La lista enlazada gana en el medio solo si ya tienes el nodo, por ejemplo porque acabas de encontrarlo con una tabla hash.

También hay un coste en memoria. El arreglo guarda los valores (o las referencias) uno junto a otro. Cada nodo es un objeto aparte: el valor, la flecha y la cabecera que el entorno de ejecución guarda para cada objeto. Con valores pequeños, un nodo ocupa varias veces más memoria que un lugar del arreglo.

Míralo

Mídelo

Insertar al principio: el arreglo dinámico de la lección anterior contra la lista enlazada. Contamos las escrituras de elementos: en el arreglo el nuevo y cada movimiento, en la lista solo el nuevo nodo. Las flechas que cambian son dos por cada inserción y no crecen con n.

Insertar al principio O(n²)
Lista enlazada: al principio O(n)

Algoritmo	n = 10	n = 1000	n = 10.000	n = 100.000
Insertar al principio	63	501.516	50.021.376	≈ 5.002.137.600
Lista enlazada: al principio	10	1000	10.000	100.000

El código se ejecuta en tu navegador, en JavaScript. La cantidad de operaciones es la misma en todos los lenguajes, porque el algoritmo es el mismo. El tiempo depende de la máquina, así que solo sirve para comparar. «≈» es una estimación a partir de la curva: un n tan grande no lo ejecutamos, para que la página no se congele.

class Node {
    String value;
    Node next;

    Node(String value) {
        this.value = value;
    }
}

class SimpleLinkedList {
    private Node head;
    private Node tail;
    private int size;

    int size() {
        return size;
    }

    void addFirst(String value) {
        Node node = new Node(value);
        node.next = head;
        head = node;
        if (tail == null) {
            tail = node;
        }
        size++;
    }

    void addLast(String value) {
        Node node = new Node(value);
        if (tail == null) {
            head = node;
        } else {
            tail.next = node;
        }
        tail = node;
        size++;
    }

    String removeFirst() {
        if (head == null) {
            throw new NoSuchElementException("la lista está vacía");
        }
        String value = head.value;
        head = head.next;
        if (head == null) {
            tail = null;
        }
        size--;
        return value;
    }

    boolean remove(String value) {
        Node prev = null;
        Node n = head;
        while (n != null && !n.value.equals(value)) {
            prev = n;
            n = n.next;
        }
        if (n == null) {
            return false;
        }
        if (prev == null) {
            head = n.next;
        } else {
            prev.next = n.next;
        }
        if (n == tail) {
            tail = prev;
        }
        size--;
        return true;
    }

    int find(String value) {
        int index = 0;
        for (Node n = head; n != null; n = n.next) {
            if (n.value.equals(value)) {
                return index;
            }
            index++;
        }
        return -1;
    }

    String get(int index) {
        Objects.checkIndex(index, size);
        Node n = head;
        for (int i = 0; i < index; i++) {
            n = n.next;
        }
        return n.value;
    }

    @Override
    public String toString() {
        List<String> values = new ArrayList<>();
        for (Node n = head; n != null; n = n.next) {
            values.add(n.value);
        }
        return String.join(" → ", values);
    }
}

Con 10 000 correos, el arreglo hace 50 021 376 escrituras y la lista enlazada 10 000.

Ahora al revés: leer cada elemento por índice, get(0), get(1) y así hasta el final. Contamos los lugares a los que llegas: en el arreglo get(i) es un salto, y en la lista pasa por i + 1 nodos.

Arreglo: get(i) para cada i O(n)
Lista enlazada: get(i) para cada i O(n²)

Algoritmo	n = 10	n = 1000	n = 10.000	n = 100.000
Arreglo: get(i) para cada i	10	1000	10.000	100.000
Lista enlazada: get(i) para cada i	55	500.500	50.005.000	≈ 5.000.500.000

El código se ejecuta en tu navegador, en JavaScript. La cantidad de operaciones es la misma en todos los lenguajes, porque el algoritmo es el mismo. El tiempo depende de la máquina, así que solo sirve para comparar. «≈» es una estimación a partir de la curva: un n tan grande no lo ejecutamos, para que la página no se congele.

class Node {
    String value;
    Node next;

    Node(String value) {
        this.value = value;
    }
}

class SimpleLinkedList {
    private Node head;
    private Node tail;
    private int size;

    int size() {
        return size;
    }

    void addFirst(String value) {
        Node node = new Node(value);
        node.next = head;
        head = node;
        if (tail == null) {
            tail = node;
        }
        size++;
    }

    void addLast(String value) {
        Node node = new Node(value);
        if (tail == null) {
            head = node;
        } else {
            tail.next = node;
        }
        tail = node;
        size++;
    }

    String removeFirst() {
        if (head == null) {
            throw new NoSuchElementException("la lista está vacía");
        }
        String value = head.value;
        head = head.next;
        if (head == null) {
            tail = null;
        }
        size--;
        return value;
    }

    boolean remove(String value) {
        Node prev = null;
        Node n = head;
        while (n != null && !n.value.equals(value)) {
            prev = n;
            n = n.next;
        }
        if (n == null) {
            return false;
        }
        if (prev == null) {
            head = n.next;
        } else {
            prev.next = n.next;
        }
        if (n == tail) {
            tail = prev;
        }
        size--;
        return true;
    }

    int find(String value) {
        int index = 0;
        for (Node n = head; n != null; n = n.next) {
            if (n.value.equals(value)) {
                return index;
            }
            index++;
        }
        return -1;
    }

    String get(int index) {
        Objects.checkIndex(index, size);
        Node n = head;
        for (int i = 0; i < index; i++) {
            n = n.next;
        }
        return n.value;
    }

    @Override
    public String toString() {
        List<String> values = new ArrayList<>();
        for (Node n = head; n != null; n = n.next) {
            values.add(n.value);
        }
        return String.join(" → ", values);
    }
}

Con 10 000 elementos, el arreglo hace 10 000 saltos y la lista enlazada 50 005 000 pasos. Un bucle por índice sobre una lista enlazada es O(n²). Recórrela con el bucle por las flechas (o con for-each), como hace toString: eso es O(n).

Más precisamente, para curiosos

Los mismos números en tu lenguaje, con contadores en la clase:

class Node {
    String value;
    Node next;

    Node(String value) {
        this.value = value;
    }
}

class SimpleLinkedList {
    private Node head;
    private Node tail;
    private int size;
    long writes = 0;
    long steps = 0;

    int size() {
        return size;
    }

    void addFirst(String value) {
        Node node = new Node(value);
        writes++;
        node.next = head;
        head = node;
        if (tail == null) {
            tail = node;
        }
        size++;
    }

    void addLast(String value) {
        Node node = new Node(value);
        if (tail == null) {
            head = node;
        } else {
            tail.next = node;
        }
        tail = node;
        size++;
    }

    String removeFirst() {
        if (head == null) {
            throw new NoSuchElementException("la lista está vacía");
        }
        String value = head.value;
        head = head.next;
        if (head == null) {
            tail = null;
        }
        size--;
        return value;
    }

    boolean remove(String value) {
        Node prev = null;
        Node n = head;
        while (n != null && !n.value.equals(value)) {
            prev = n;
            n = n.next;
        }
        if (n == null) {
            return false;
        }
        if (prev == null) {
            head = n.next;
        } else {
            prev.next = n.next;
        }
        if (n == tail) {
            tail = prev;
        }
        size--;
        return true;
    }

    int find(String value) {
        int index = 0;
        for (Node n = head; n != null; n = n.next) {
            if (n.value.equals(value)) {
                return index;
            }
            index++;
        }
        return -1;
    }

    String get(int index) {
        Objects.checkIndex(index, size);
        Node n = head;
        steps++;
        for (int i = 0; i < index; i++) {
            n = n.next;
            steps++;
        }
        return n.value;
    }

    @Override
    public String toString() {
        List<String> values = new ArrayList<>();
        for (Node n = head; n != null; n = n.next) {
            values.add(n.value);
        }
        return String.join(" → ", values);
    }
}

for (int n : new int[] {10, 1000, 100000}) {
    SimpleLinkedList list = new SimpleLinkedList();
    for (int i = 0; i < n; i++) {
        list.addFirst(String.valueOf(1001 + i));
    }
    System.out.println("al principio, n = " + n + ": " + list.writes + " escrituras");
}
for (int n : new int[] {10, 1000}) {
    SimpleLinkedList list = new SimpleLinkedList();
    for (int i = 0; i < n; i++) {
        list.addLast(String.valueOf(1001 + i));
    }
    for (int i = 0; i < n; i++) {
        list.get(i);
    }
    System.out.println("get(i) para cada i, n = " + n + ": " + list.steps + " pasos");
}

al principio, n = 10: 10 escrituras
al principio, n = 1000: 1000 escrituras
al principio, n = 100000: 100000 escrituras
get(i) para cada i, n = 10: 55 pasos
get(i) para cada i, n = 1000: 500500 pasos

Bench cuenta operaciones, no tiempo. En el reloj, la diferencia al recorrer es aún mayor a favor del arreglo por la caché: el arreglo es un bloque, los nodos están dispersos y cada siguiente puede no estar en la caché. Aquí eso no se mide, solo se explica en la lección sobre el arreglo dinámico.

Pruébalo

Encuentra el error

Un compañero ha escrito addLast. Tres correos añadidos al final, y la lista sale así:

SimpleLinkedList emails = new SimpleLinkedList();
emails.addLast("factura");
emails.addLast("boletín");
emails.addLast("informe");
System.out.println(emails);
System.out.println("Correos: " + emails.size());

factura → informe
Correos: 3

El tamaño es 3, y los correos son dos. ¿En qué línea está el error?

Elige la línea con el error.

Pruébalo

Completa

remove ha encontrado el nodo n y el anterior, prev. ¿A dónde tiene que apuntar prev ahora?

boolean remove(String value) {
    Node prev = null;
    Node n = head;
    while (n != null && !n.value.equals(value)) {
        prev = n;
        n = n.next;
    }
    if (n == null) {
        return false;
    }
    if (prev == null) {
        head = n.next;
    } else {
        prev.next = ;
    }
    if (n == tail) {
        tail = prev;
    }
    size--;
    return true;
}

La idea

La lista doblemente enlazada

Una lista simplemente enlazada no puede quitar el último con rapidez: necesita el penúltimo, y hacia él no apunta nada desde atrás. Una lista doblemente enlazada guarda en cada nodo dos flechas, next y prev. Entonces los dos extremos son O(1), y un nodo que ya tienes se quita con cuatro flechas, sin buscar el anterior.

El coste es una flecha más en cada nodo y más reenlaces en cada operación.

LinkedList en Java es doblemente enlazada. Tiene addFirst, addLast, removeFirst, removeLast, y get(i) camina desde el extremo más cercano.

La idea

Dónde la lista enlazada gana de verdad

Para una cola normal, la integrada es mejor. ArrayDeque es un arreglo que mantiene los dos extremos sin mover nada. Cómo funciona está en la lección Pila y cola. La lista enlazada gana cuando ya tienes el nodo y tienes que sacarlo o moverlo:

Una caché LRU. La tienda guarda en memoria los últimos productos abiertos y echa el que se abrió hace más tiempo. Una tabla hash encuentra el nodo del producto en O(1), y una lista doblemente enlazada lo pasa al final. El más antiguo está siempre al principio.
Historial con atrás y adelante. El navegador y el editor guardan los pasos en una lista doblemente enlazada: atrás y adelante son una flecha.
Las listas en el núcleo del sistema operativo. Los procesos y los búferes llevan sus propias flechas y se sacan de la lista en O(1).

Aquí tienes un LRU con las herramientas integradas, los últimos tres productos abiertos:

class Recent {
    private final int limit;
    private final LinkedHashSet<String> items = new LinkedHashSet<>();

    Recent(int limit) {
        this.limit = limit;
    }

    void open(String product) {
        if (items.contains(product)) {
            items.remove(product);
        } else if (items.size() == limit) {
            items.removeFirst();
        }
        items.add(product);
    }

    @Override
    public String toString() {
        return String.join(", ", items);
    }
}

Recent recent = new Recent(3);
for (String product : new String[] {"laptop", "mouse", "monitor", "laptop", "teclado"}) {
    recent.open(product);
    System.out.println(recent);
}

laptop
laptop, mouse
laptop, mouse, monitor
mouse, monitor, laptop
monitor, laptop, teclado

LinkedHashSet es justo una tabla hash más una lista doblemente enlazada a través de los elementos, por eso conserva el orden de inserción. remove y add pasan el producto al final, y removeFirst echa el más antiguo.

Ejercicio

Una lista doblemente enlazada

Resuelve la tarea en tu editor.

Quitar por los dos extremos. Haz una DoublyLinkedList: el nodo tiene también prev. Escribe addFirst, addLast, removeFirst y removeLast, todas en O(1). Mantén correctos los dos extremos: cuando la lista queda vacía, head y tail son ambos null.

Añade los tres correos al final y el de la contraseña al principio. Imprime la lista, quita el último y el primero, imprímela otra vez. Quita dos más por el final, imprime el tamaño y después añade la invitación al final:

contraseña → factura → boletín → informe
Último: informe
Primero: contraseña
factura → boletín
Correos: 0
invitación

Más tareas

El medio con dos punteros. Encuentra el nodo del medio en una sola pasada: un puntero avanza un paso cada vez, el otro dos. Cuando el rápido llega al final, el lento está en el medio.
Un ciclo en la lista. Un error ha colgado el último nodo de uno de los anteriores. Detéctalo con los mismos dos punteros: si hay un ciclo, el rápido alcanza al lento.
Quitar todas las apariciones. removeAll(String value) quita en una pasada cada nodo con ese valor y devuelve cuántos quitó. No olvides tail.
LRU a mano. Haz la caché LRU de la tarjeta de arriba con tu propia lista doblemente enlazada y un HashMap del producto al nodo.

Test

Ponte a prueba

1. Una lista enlazada tiene 1000 nodos y solo guardas head. ¿Cuántos nodos recorres para leer el elemento con índice 999?1000: desde head, siguiendo las flechas hasta él500 de media, sea cual sea el índice1: la dirección se calcula

2. ¿Para qué hace falta tail, si head ya sostiene toda la lista?Sin él no se puede quitar el primeroPara saber el tamañoSin él, añadir al final recorre todos los nodos: O(n) en lugar de O(1)

3. En una lista simplemente enlazada con head y tail, ¿cuánto cuesta quitar el último?O(log n)O(1): tail lo conoceO(n): necesitas el penúltimo, y a él se llega desde head

4. Bench muestra que insertar al principio hace n operaciones en una lista enlazada y unas n²/2 en un arreglo dinámico. ¿Por qué el arreglo suele ser más rápido al recorrer?La lista enlazada hace más comparacionesEl arreglo se compila mejorEl arreglo es un bloque en la memoria y la caché lo lee por líneas; los nodos están dispersos

5. Una caché LRU guarda los últimos 1000 productos abiertos y echa el que se abrió hace más tiempo. ¿Qué hace que cada apertura sea O(1)?Una tabla hash que encuentra el nodo, y una lista doblemente enlazada en la que el nodo pasa al finalUna tabla hash solaUn arreglo ordenado por tiempo

Lista enlazada

Cookies