Desliza para mostrar el menú

¿Qué pasaría si los objetos estuvieran enlazados entre sí?

Pasemos a la siguiente estructura de datos, bastante interesante: LinkedList.

Analicemos la sintaxis y el esquema de funcionamiento de LinkedList:

Como se puede observar, la sintaxis es absolutamente idéntica a la declaración de un ArrayList. En general, cualquier lista puede declararse de esta manera.

Pero la parte interesante comienza cuando intentamos comprender cómo funciona LinkedList.

¿Cómo está estructurado LinkedList?

Internamente, LinkedList funciona con Nodes. Un Node es un objeto que se almacena dentro de LinkedList. Se implementa dentro de LinkedList de la siguiente manera:

Main.java


              1234567891011
            
class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

Analicemos de qué consta esta clase. Primero, es necesario responder la pregunta principal que surge: ¿Qué significa <E>? Esto es un genérico.

En términos simples, aquí se deja un marcador de posición para el tipo de dato que se especificará durante la inicialización. Se utiliza este marcador en el código, que luego será reemplazado por el tipo de dato que indique el usuario.

Esto se puede comparar con la sobrecarga.

Veamos cómo funciona:

Entonces, en lugar de sobrecargar este método para cada tipo de dato, se utiliza un genérico en el que se inserta el tipo de dato con el que funcionará el método. La letra E simplemente será reemplazada por el tipo de dato requerido. En nuestro caso, es Integer.

A continuación, prestemos atención al campo item E. Este es el valor del objeto que se almacenará en este Node. Por ejemplo, si creamos una lista como {0, 1, 2, 3}, el primer nodo almacenará el elemento 0, el segundo nodo almacenará el elemento 1, y así sucesivamente.

Luego, se observan referencias a otros objetos Node: Node<E> next y Node<E> prev. Esta es la característica principal de una lista enlazada. En un Node, existe una referencia al siguiente Node y al anterior. Así es como se recorre la lista. Analicemos más de cerca la iteración a través de un LinkedList.

Al observar este tipo de esquema, se puede concluir que la iteración a través de esta lista funciona de manera diferente.

En ArrayList<>(), internamente, el programa utiliza un arreglo que duplica su tamaño cuando el número de elementos alcanza las 3/4 partes de su capacidad.

En un LinkedList<>(), no es necesario recrear un arreglo porque no existe un arreglo en un LinkedList. En su lugar, al agregar un nuevo elemento, se crea un nuevo objeto Node y se enlaza mediante referencias al anterior último elemento.

Puede parecer y sonar un poco complicado, pero como programador, no tendrás que configurar todo esto.

Los métodos de LinkedList son los mismos que los de ArrayList porque ambos heredan de la interfaz List, la cual define los métodos que todos sus descendientes deben implementar.

Complejidad Algorítmica

Se puede observar que buscar un elemento por índice en ArrayList tiene complejidad constante ya que simplemente se accede al índice en el arreglo.

Por otro lado, en LinkedList, la búsqueda por índice toma mucho más tiempo porque es necesario recorrer todos los nodos y encontrar el objeto requerido por su índice.

En cambio, si se analiza la inserción de un elemento, LinkedList presenta complejidad constante, mientras que ArrayList tiene complejidad lineal. Esto se debe a que para insertar un elemento en una LinkedList, solo es necesario cambiar los enlaces de los nodos por los nuevos, insertando el elemento entre ellos. Para ArrayList, es necesario recrear el arreglo con el nuevo elemento, lo que implica copiar el arreglo anterior e insertar el elemento, lo que requiere mucho más tiempo.

Veamos un ejemplo:

Main.java


              1234567891011121314151617181920212223242526272829
            
package com.example;

import java.util.*;

public class Main {
    public static void main(String[] args) {
        List<Integer> linkedList = new LinkedList<>();
        List<Integer> arrayList = new ArrayList<>();

        Random random = new Random();

        for (int i = 0; i < 1000000; i++) {
            int randomValue = random.nextInt(100);
            arrayList.add(randomValue);
            linkedList.add(randomValue);
        }
        long startTimeArrayList = System.nanoTime();
        arrayList.add(1000, 50);
        long endTimeArrayList = System.nanoTime();
        long elapsedTimeArrayList = endTimeArrayList - startTimeArrayList;
        System.out.println("Time taken to put data in ArrayList: " + elapsedTimeArrayList + " nanoseconds");

        long startTimeLinkedList = System.nanoTime();
        linkedList.add(1000, 50);
        long endTimeLinkedList = System.nanoTime();
        long elapsedTimeLinkedList = endTimeLinkedList - startTimeLinkedList;
        System.out.println("Time taken to put data in LinkedList: " + elapsedTimeLinkedList + " nanoseconds");
    }
}

Se crearon dos listas: una es un ArrayList y la otra es un LinkedList. Luego, se llenaron con 1,000,000 de enteros aleatorios. Las listas tienen el mismo contenido, cada una contiene un millón de números del 1 al 100.

A continuación, se midió el tiempo que toma agregar un elemento en el índice mil con el valor 50. Se utilizó el método System.nanoTime() para medir el tiempo, el cual muestra el tiempo actual en nanosegundos. Luego, para cada lista, se restó el tiempo de inicio al tiempo final, determinando así cuánto tiempo se empleó en agregar un elemento en la mitad de la lista.

Se puede observar que LinkedList fue considerablemente más rápido, como se evidencia en la tabla. LinkedList tiene complejidad algorítmica constante, mientras que ArrayList tiene complejidad lineal.

Por esta razón, se requieren diferentes tipos de listas. Si el proyecto maneja grandes cantidades de datos donde la optimización es crucial, vale la pena reconsiderar qué tipo de lista permitirá que el programa funcione más rápido en ciertos casos. Pero te contaré un secreto: casi siempre utilizo ArrayList.

SinglyLinkedList

Existe otra estructura de datos no revelada llamada SinglyLinkedList. Como su nombre indica, esta estructura de datos utiliza la iteración en una sola dirección. Mientras que la clase LinkedList de Node tiene los campos: item, next y prev, la clase SinglyLinkedList de Node solo tiene 2 campos: item y next.

Main.java


              123456789
            
class Node<E> {
    E item;
    Node<E> next;

    Node(E element, Node<E> next) {
        this.item = element;
        this.next = next;
    }
}

Esta estructura de datos se utiliza en estructuras como maps, donde la iteración es necesaria solo en una dirección. Aprenderemos sobre maps, especialmente HashMap, en secciones futuras.

En el próximo capítulo, escribiremos una implementación de SinglyLinkedList para comprender mejor cómo funciona esta interesante estructura de datos.

1. ¿Qué estructura de datos tendrá un mejor rendimiento si queremos encontrar un elemento por índice?

2. ¿Qué estructura de datos tendrá un mejor rendimiento al realizar una operación de eliminación?

3. ¿Cómo participa la clase `Node` en el funcionamiento de `LinkedList`?

¿Todo estuvo claro?

¡Gracias por tus comentarios!

Sección 1. Capítulo 6

Pregunte a AI

Pregunte lo que quiera o pruebe una de las preguntas sugeridas para comenzar nuestra charla

Sección 1. Capítulo 6

Linkedlist en Java

¿Qué pasaría si los objetos estuvieran enlazados entre sí?

¿Cómo está estructurado LinkedList?

Complejidad Algorítmica

SinglyLinkedList

1. ¿Qué estructura de datos tendrá un mejor rendimiento si queremos encontrar un elemento por índice?

2. ¿Qué estructura de datos tendrá un mejor rendimiento al realizar una operación de eliminación?

3. ¿Cómo participa la clase Node en el funcionamiento de LinkedList?

3. ¿Cómo participa la clase `Node` en el funcionamiento de `LinkedList`?