ListaEnlazada
¿Y si los objetos estuvieran vinculados entre sí?
Pasemos a la siguiente estructura de datos, bastante interesante: LinkedList.
Veamos la sintaxis y el esquema de funcionamiento de LinkedList:
Como puedes ver, la sintaxis es absolutamente idéntica a la de declarar un ArrayList. En general, cualquier lista puede declararse de esta forma.
Pero lo interesante empieza cuando intentamos entender cómo funciona LinkedList.
¿Cómo se estructura LinkedList?
Por dentro, LinkedList funciona con Nodos. Un Nodo es un objeto que se almacena dentro de LinkedList. Se implementa dentro de LinkedList así:
main.java
1234567891011class 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; } }
Desglosemos en qué consiste esta clase.
Primero, tenemos que responder a la pregunta principal que se plantea: ¿Qué significa <E>? Se trata de un genérico.
En términos sencillos, aquí dejamos un marcador de posición para el tipo de datos que se especificará durante la inicialización. Utilizamos este marcador de posición en el código, que el tipo de datos especificado por el usuario reemplazará más tarde.
Esto puede compararse con la sobrecarga.
Veamos cómo funciona:
Así, en lugar de sobrecargar este método para cada tipo de dato, utilizamos un genérico en el que insertamos el tipo de dato con el que funcionará el método.
La letra E será simplemente reemplazada por el tipo de dato requerido. En nuestro caso, es Integer.
A continuación, prestemos atención al campo E item. Es el valor del objeto que se almacenará en este Nodo. Así, 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.
A continuación, vemos referencias a otros objetos Node: Node<E> next y Node<E> prev.
Esta es la principal característica de una lista enlazada. En un Nodo, hay una referencia al siguiente Nodo y al anterior. Así es como iteramos a través de la lista. Echemos un vistazo más de cerca a la iteración a través de una LinkedList.
Viendo tal esquema, podemos concluir que iterar a través de tal lista funcionará un poco diferente.
En ArrayList<>(), bajo el capó, el programa utiliza un array que duplica su tamaño cuando el número de elementos ocupa 3/4 del tamaño del array.
En una LinkedList<>(), no necesitamos recrear un array porque no hay array en una LinkedList. En su lugar, se creará un nuevo objeto Node cuando se añada un nuevo elemento, enlazado por referencias al último elemento anterior.
Entiendo que parece y suena un poco complicado, pero no tendrás que configurar todo esto como programador. Los métodos de LinkedList son **los mismos que los de ArrayList porque ambos heredan de la interfaz List, que define los métodos que deben implementar todos sus descendientes.
Entonces, ¿por qué necesitamos conocer diferentes tipos de listas?
La respuesta es:
Complejidad algorítmica
En el marco Collection, hay muchas estructuras de datos diferentes, y cada una de ellas tiene su complejidad algorítmica.
La complejidad algorítmica se denota mediante la notación big O (por ejemplo, O(n), O(n^2)), donde "O" significa "big O" y indica un límite superior en el crecimiento del tiempo de ejecución en función del tamaño de la entrada. Estos son 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 de una matriz 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 una matriz ordenada.
-
O(n) (tiempo lineal):** La complejidad temporal crece linealmente con el tamaño de los datos de entrada. Ejemplo: iteración a través de todos los elementos de un ArrayList.
-
O(n^2) (tiempo cuadrático):** La complejidad temporal es proporcional al cuadrado del tamaño de los datos de entrada. Ejemplo: ordenación 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!), y otras, que caracterizan algoritmos más complejos. Elegir un algoritmo eficiente, teniendo en cuenta 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 de tiempo algorítmica dependiendo de la operación que se necesite realizar. Echemos un vistazo a la tabla:
Nota
Como puedes ver en esta tabla, exploraremos muchas otras estructuras de datos más adelante. Por ahora, deberías echar un vistazo a
ArrayListyLinkedList.
Puedes ver que buscar un elemento por índice en ArrayList tiene complejidad constante ya que simplemente accedemos al índice en el array.
Mientras tanto, en LinkedList, buscar por índice lleva mucho más tiempo porque tenemos que recorrer todos los nodos y encontrar el objeto que necesitamos por índice.
Por otro lado, si nos fijamos en 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, basta con cambiar los enlaces de los nodos por otros nuevos, insertando el elemento entre ellos. Para ArrayList, necesitamos recrear el array con el nuevo elemento, lo que implica copiar el array antiguo e insertar el elemento, tomando mucho más tiempo.
Veamos un ejemplo:
main.java
1234567891011121314151617181920212223242526272829package 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 una ArrayList, y la otra es una LinkedList. Luego, las poblamos 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 se tarda en añadir un elemento en el índice milésimo con el valor 50. Para medir el tiempo utilizamos el método System.nanoTime(), que muestra el tiempo actual en nanosegundos. Luego, para cada lista, restamos el tiempo inicial del tiempo final, determinando así cuánto tiempo se empleó en añadir un elemento a la mitad de la lista.
Como se puede ver en la tabla, LinkedList fue significativamente más rápida. La complejidad algorítmica de "ListaEnlazada" es constante, mientras que la de "ListaMatriz" es lineal.
Por eso necesitamos distintos tipos de listas. Si tu proyecto trata con una gran cantidad de datos donde la optimización es crucial, reconsiderar qué tipo de lista hará que el programa funcione más rápido en ciertos casos merece la pena. Pero te contaré un secreto: yo 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 sólo una dirección. Mientras que la clase LinkedList Node tiene campos: item, next, y prev, la clase SinglyLinkedList Node sólo tiene 2 campos: item y next.
main.java
123456789class 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 en una sola dirección. Aprenderemos sobre mapas, especialmente sobre HashMap, en futuras secciones. En el próximo capítulo, escribiremos una implementación de SinglyLinkedList para entender mejor cómo funciona esta interesante estructura de datos.
1. ¿Qué estructura de datos será más rápida si queremos encontrar un elemento por índice?
2. ¿Qué estructura de datos funcionará más rápido al realizar una operación de borrado?
3. ¿Cómo participa la clase Node en el funcionamiento de LinkedList?
¡Gracias por tus comentarios!
Pregunte a AI
Pregunte a AI
Pregunte lo que quiera o pruebe una de las preguntas sugeridas para comenzar nuestra charla
Awesome!
Completion rate improved to 4ListaEnlazada
Desliza para mostrar el menú
¿Y si los objetos estuvieran vinculados entre sí?
Pasemos a la siguiente estructura de datos, bastante interesante: LinkedList.
Veamos la sintaxis y el esquema de funcionamiento de LinkedList:
Como puedes ver, la sintaxis es absolutamente idéntica a la de declarar un ArrayList. En general, cualquier lista puede declararse de esta forma.
Pero lo interesante empieza cuando intentamos entender cómo funciona LinkedList.
¿Cómo se estructura LinkedList?
Por dentro, LinkedList funciona con Nodos. Un Nodo es un objeto que se almacena dentro de LinkedList. Se implementa dentro de LinkedList así:
main.java
1234567891011class 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; } }
Desglosemos en qué consiste esta clase.
Primero, tenemos que responder a la pregunta principal que se plantea: ¿Qué significa <E>? Se trata de un genérico.
En términos sencillos, aquí dejamos un marcador de posición para el tipo de datos que se especificará durante la inicialización. Utilizamos este marcador de posición en el código, que el tipo de datos especificado por el usuario reemplazará más tarde.
Esto puede compararse con la sobrecarga.
Veamos cómo funciona:
Así, en lugar de sobrecargar este método para cada tipo de dato, utilizamos un genérico en el que insertamos el tipo de dato con el que funcionará el método.
La letra E será simplemente reemplazada por el tipo de dato requerido. En nuestro caso, es Integer.
A continuación, prestemos atención al campo E item. Es el valor del objeto que se almacenará en este Nodo. Así, 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.
A continuación, vemos referencias a otros objetos Node: Node<E> next y Node<E> prev.
Esta es la principal característica de una lista enlazada. En un Nodo, hay una referencia al siguiente Nodo y al anterior. Así es como iteramos a través de la lista. Echemos un vistazo más de cerca a la iteración a través de una LinkedList.
Viendo tal esquema, podemos concluir que iterar a través de tal lista funcionará un poco diferente.
En ArrayList<>(), bajo el capó, el programa utiliza un array que duplica su tamaño cuando el número de elementos ocupa 3/4 del tamaño del array.
En una LinkedList<>(), no necesitamos recrear un array porque no hay array en una LinkedList. En su lugar, se creará un nuevo objeto Node cuando se añada un nuevo elemento, enlazado por referencias al último elemento anterior.
Entiendo que parece y suena un poco complicado, pero no tendrás que configurar todo esto como programador. Los métodos de LinkedList son **los mismos que los de ArrayList porque ambos heredan de la interfaz List, que define los métodos que deben implementar todos sus descendientes.
Entonces, ¿por qué necesitamos conocer diferentes tipos de listas?
La respuesta es:
Complejidad algorítmica
En el marco Collection, hay muchas estructuras de datos diferentes, y cada una de ellas tiene su complejidad algorítmica.
La complejidad algorítmica se denota mediante la notación big O (por ejemplo, O(n), O(n^2)), donde "O" significa "big O" y indica un límite superior en el crecimiento del tiempo de ejecución en función del tamaño de la entrada. Estos son 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 de una matriz 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 una matriz ordenada.
-
O(n) (tiempo lineal):** La complejidad temporal crece linealmente con el tamaño de los datos de entrada. Ejemplo: iteración a través de todos los elementos de un ArrayList.
-
O(n^2) (tiempo cuadrático):** La complejidad temporal es proporcional al cuadrado del tamaño de los datos de entrada. Ejemplo: ordenación 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!), y otras, que caracterizan algoritmos más complejos. Elegir un algoritmo eficiente, teniendo en cuenta 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 de tiempo algorítmica dependiendo de la operación que se necesite realizar. Echemos un vistazo a la tabla:
Nota
Como puedes ver en esta tabla, exploraremos muchas otras estructuras de datos más adelante. Por ahora, deberías echar un vistazo a
ArrayListyLinkedList.
Puedes ver que buscar un elemento por índice en ArrayList tiene complejidad constante ya que simplemente accedemos al índice en el array.
Mientras tanto, en LinkedList, buscar por índice lleva mucho más tiempo porque tenemos que recorrer todos los nodos y encontrar el objeto que necesitamos por índice.
Por otro lado, si nos fijamos en 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, basta con cambiar los enlaces de los nodos por otros nuevos, insertando el elemento entre ellos. Para ArrayList, necesitamos recrear el array con el nuevo elemento, lo que implica copiar el array antiguo e insertar el elemento, tomando mucho más tiempo.
Veamos un ejemplo:
main.java
1234567891011121314151617181920212223242526272829package 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 una ArrayList, y la otra es una LinkedList. Luego, las poblamos 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 se tarda en añadir un elemento en el índice milésimo con el valor 50. Para medir el tiempo utilizamos el método System.nanoTime(), que muestra el tiempo actual en nanosegundos. Luego, para cada lista, restamos el tiempo inicial del tiempo final, determinando así cuánto tiempo se empleó en añadir un elemento a la mitad de la lista.
Como se puede ver en la tabla, LinkedList fue significativamente más rápida. La complejidad algorítmica de "ListaEnlazada" es constante, mientras que la de "ListaMatriz" es lineal.
Por eso necesitamos distintos tipos de listas. Si tu proyecto trata con una gran cantidad de datos donde la optimización es crucial, reconsiderar qué tipo de lista hará que el programa funcione más rápido en ciertos casos merece la pena. Pero te contaré un secreto: yo 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 sólo una dirección. Mientras que la clase LinkedList Node tiene campos: item, next, y prev, la clase SinglyLinkedList Node sólo tiene 2 campos: item y next.
main.java
123456789class 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 en una sola dirección. Aprenderemos sobre mapas, especialmente sobre HashMap, en futuras secciones. En el próximo capítulo, escribiremos una implementación de SinglyLinkedList para entender mejor cómo funciona esta interesante estructura de datos.
1. ¿Qué estructura de datos será más rápida si queremos encontrar un elemento por índice?
2. ¿Qué estructura de datos funcionará más rápido al realizar una operación de borrado?
3. ¿Cómo participa la clase Node en el funcionamiento de LinkedList?
¡Gracias por tus comentarios!
