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

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

Observemos la sintaxis y el esquema de funcionamiento de LinkedList:

Como se puede ver, 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, debemos 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 especificado por 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 el método funcionará. La letra E simplemente será reemplazada por el tipo de dato requerido. En nuestro caso, es Integer.

A continuación, se debe prestar atención al campo item E. Este es el valor del objeto que se almacenará en este Node. Por ejemplo, si se crea 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. A continuación, se analiza con más detalle 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 vincula por referencias al anterior último elemento.

Puede parecer y sonar un poco complicado, pero como programador, no será necesario 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

En el framework Collection, existen diferentes estructuras de datos, y cada una de ellas tiene su propia complejidad algorítmica.

La complejidad algorítmica se denota utilizando la notación big O (por ejemplo, O(n), O(n^2)), donde "O" representa "big O" e indica un límite superior en el crecimiento del tiempo de ejecución como función del tamaño de la entrada.

A continuación se presentan los principales tipos de complejidad algorítmica:

O(1) (tiempo constante): la complejidad temporal no depende del tamaño de los datos de entrada. Por ejemplo, acceder a un elemento en un arreglo por índice;
O(log n) (tiempo logarítmico): la complejidad temporal crece logarítmicamente con el tamaño de los datos de entrada. Ejemplo: búsqueda binaria en un arreglo ordenado;
O(n) (tiempo lineal): la complejidad temporal crece linealmente con el tamaño de los datos de entrada. Ejemplo: iterar a través de todos los elementos en un ArrayList;
O(n^2) (tiempo cuadrático): la complejidad temporal es proporcional al cuadrado del tamaño de los datos de entrada. Ejemplo: ordenamiento burbuja.

Estas son categorías básicas, y existen muchos otros tipos de complejidad algorítmica, como O(n log n), O(2^n), O(n!), entre otros, que caracterizan algoritmos más complejos. Elegir un algoritmo eficiente, considerando su complejidad, es un aspecto crucial del desarrollo de software.

Ahora, volvamos a las estructuras de datos en Java. Cada estructura de datos tiene su complejidad temporal algorítmica dependiendo de la operación que se deba realizar. Observemos la tabla:

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

Mientras tanto, en LinkedList, la búsqueda por índice toma mucho más tiempo porque debemos recorrer todos los nodos y encontrar el objeto necesario por índice.

Por otro lado, si se observa la inserción de un elemento, LinkedList tiene complejidad constante, mientras que ArrayList tiene complejidad lineal. Esto ocurre porque para insertar un elemento en una LinkedList, solo es necesario cambiar los enlaces en 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 antiguo e insertar el elemento, tomando 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");
    }
}

Creamos dos listas: una es un ArrayList y la otra es un LinkedList. Luego, las llenamos 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, medimos el tiempo que toma agregar un elemento en el índice mil con el valor 50. Utilizamos el método System.nanoTime() para medir el tiempo, que muestra la hora actual en nanosegundos. Luego, para cada lista, restamos el tiempo de inicio al tiempo final, determinando así cuánto tiempo se gastó agregando un elemento en el medio de la lista.

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

Por esto necesitamos diferentes tipos de listas. Si tu proyecto maneja grandes cantidades de datos donde la optimización es crucial, vale la pena reconsiderar en qué tipo de lista el programa funcionará más rápido en ciertos casos. Pero te contaré un secreto: casi siempre uso 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 los mapas, donde la iteración es necesaria en una sola dirección. Aprenderemos sobre los mapas, 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 5

Pregunte a AI

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

Suggested prompts:

What are the main differences between ArrayList and LinkedList?

Can you explain how generics work in Java with more examples?

Why would I choose LinkedList over ArrayList in a real project?

Awesome!

Completion rate improved to 4

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.

Observemos la sintaxis y el esquema de funcionamiento de LinkedList:

Como se puede ver, 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, debemos responder la pregunta principal que surge: ¿Qué significa <E>? Esto es un genérico.

Esto se puede comparar con la sobrecarga.

Veamos cómo funciona:

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.

Puede parecer y sonar un poco complicado, pero como programador, no será necesario configurar todo esto.

Complejidad Algorítmica

En el framework Collection, existen diferentes estructuras de datos, y cada una de ellas tiene su propia complejidad algorítmica.

A continuación se presentan los principales tipos de complejidad algorítmica:

O(1) (tiempo constante): la complejidad temporal no depende del tamaño de los datos de entrada. Por ejemplo, acceder a un elemento en un arreglo por índice;
O(log n) (tiempo logarítmico): la complejidad temporal crece logarítmicamente con el tamaño de los datos de entrada. Ejemplo: búsqueda binaria en un arreglo ordenado;
O(n) (tiempo lineal): la complejidad temporal crece linealmente con el tamaño de los datos de entrada. Ejemplo: iterar a través de todos los elementos en un ArrayList;
O(n^2) (tiempo cuadrático): la complejidad temporal es proporcional al cuadrado del tamaño de los datos de entrada. Ejemplo: ordenamiento burbuja.

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

Mientras tanto, en LinkedList, la búsqueda por índice toma mucho más tiempo porque debemos recorrer todos los nodos y encontrar el objeto necesario por índice.

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");
    }
}

SinglyLinkedList

Main.java


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

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

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 5

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`?

Awesome!

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`?

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?

Awesome!

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`?

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