1.ArrayList implementa una estructura de datos basada en matrices dinámicas y LinkedList implementa una estructura de datos basada en listas vinculadas.
2. Para el acceso aleatorio para obtener y configurar, ArrayList es mejor que LinkedList porque ArrayList se puede colocar aleatoriamente, mientras que LinkedList necesita mover el puntero al nodo paso a paso. (Piense en referencia a matrices y listas vinculadas)
3. Para las operaciones nuevas y de eliminación de agregar y eliminar, LinedList es más ventajoso. Solo necesita modificar el puntero, mientras que ArrayList necesita mover datos para llenar el espacio del objeto eliminado.
ArrayList y LinkedList son dos clases de colección que se utilizan para almacenar una serie de referencias de objetos. Por ejemplo, podemos usar ArrayList para almacenar una serie de String o Integer. Entonces, ¿cuál es la diferencia de rendimiento entre ArrayList y LinkedList? ¿Cuándo debería utilizar ArrayList y cuándo debería utilizar LinkedList?
uno. complejidad del tiempo
El primer punto clave es que la implementación interna de ArrayList se basa en una matriz de objetos básica. Por lo tanto, cuando utiliza el método get para acceder a cualquier elemento de la lista (acceso aleatorio), es más rápido que LinkedList. El método get en LinkedList verifica desde un extremo de la lista hasta el otro extremo en orden. Para LinkedList, no existe una forma más rápida de acceder a un elemento específico de la lista.
Supongamos que tenemos una lista grande y los elementos que contiene están ordenados. Esta lista puede ser del tipo ArrayList o LinkedList. Ahora realizamos una búsqueda binaria en esta lista. Para la velocidad de consulta de ArrayList y LinkedList, ver el siguiente programa:
Tiempo consumido en LinkedList: 2596
Este resultado no es fijo, pero básicamente el tiempo de ArrayList es significativamente menor que el de LinkedList. Por lo tanto, LinkedList no debería utilizarse en este caso. El método de búsqueda binaria utiliza una estrategia de acceso aleatorio (acceso aleatorio) y LinkedList no admite el acceso aleatorio rápido. El tiempo consumido por el acceso aleatorio a una LinkedList es proporcional al tamaño de la lista. En consecuencia, el tiempo consumido por el acceso aleatorio en ArrayList es fijo.
¿Significa esto que ArrayList siempre funciona mejor que LinkedList? Esto no es necesariamente cierto; en algunos casos, LinkedList funciona mejor que ArrayList y algunos algoritmos son más eficientes cuando se implementan en LinkedList. Por ejemplo, el rendimiento es mejor cuando se utiliza el método Collections.reverse para invertir una lista.
Mire un ejemplo de este tipo, si tenemos una lista y queremos realizar una gran cantidad de operaciones de inserción y eliminación en ella, en este caso LinkedList es una mejor opción. Considere el siguiente ejemplo extremo, donde insertamos repetidamente un elemento al principio de una lista:
En este momento, mi salida es: ArrayList toma: 2463
LinkedList toma: 15
Esto es completamente opuesto al resultado del ejemplo anterior. Cuando se agrega un elemento al comienzo de ArrayList, todos los elementos existentes se moverán hacia atrás, lo que significa la sobrecarga de movimiento y copia de datos. Por el contrario, agregar un elemento al comienzo de una LinkedList simplemente asigna un registro al elemento y luego ajusta los dos enlaces. El costo de agregar un elemento al comienzo de una LinkedList es fijo, mientras que el costo de agregar un elemento al comienzo de una ArrayList es proporcional al tamaño de ArrayList.
dos. complejidad espacial
Hay una clase interna privada en LinkedList, definida de la siguiente manera:
Entrada de clase estática privada {
Elemento objeto;
Entrada siguiente;
Entrada anterior;
}
Cada objeto Entry hace referencia a un elemento de la lista, así como a su elemento anterior y siguiente en LinkedList. Un objeto LinkedList con 1000 elementos tendrá 1000 objetos Entry vinculados entre sí, cada objeto correspondiente a un elemento de la lista. En este caso, habrá una gran sobrecarga de espacio en una estructura LinkedList, porque necesita almacenar la información relevante de estos 1000 objetos de entidad.
ArrayList utiliza una matriz incorporada para almacenar elementos. La capacidad inicial de esta matriz es 10. Cuando la matriz necesita crecer, la nueva capacidad se obtiene de acuerdo con la siguiente fórmula: nueva capacidad = (capacidad anterior*3)/2+. 1, es decir, la capacidad aumentará aproximadamente un 50% cada vez. Esto significa que si tiene un objeto ArrayList con una gran cantidad de elementos, terminará con una gran cantidad de espacio desperdiciado. Este desperdicio se debe a la forma en que funciona ArrayList. Si no hay suficiente espacio para almacenar el nuevo elemento, será necesario reasignar la matriz para que se pueda agregar el nuevo elemento. La reasignación de la matriz provocará una caída drástica en el rendimiento. Si sabemos cuántos elementos tendrá un ArrayList, podemos especificar la capacidad a través del constructor. También podemos usar el método trimToSize para eliminar el espacio desperdiciado después de asignar ArrayList.
tres. Resumir
ArrayList y LinkedList tienen sus propias ventajas y desventajas en términos de rendimiento y cada uno tiene su propia aplicación. En términos generales, se puede describir de la siguiente manera:
Resumen de rendimiento:
| - | operación agregar () | operación eliminar() | operación de inserción | operación de valor de índice | operación de valor del iterador |
|---|---|---|---|---|---|
| Lista de matrices/Vector/Pila | bien | Diferencia | Diferencia | Excelente | Excelente |
| Lista enlazada | bien | bien | bien | Diferencia | Excelente |
1. Tanto para ArrayList como para LinkedList, el costo de agregar un elemento al final de la lista es fijo. Para ArrayList, principalmente agrega un elemento a la matriz interna, apuntando al elemento agregado, lo que ocasionalmente puede causar que la matriz se reasigne. Para LinkedList, esta sobrecarga es uniforme y asigna un objeto de entrada interno;
2. Insertar o eliminar un elemento en medio de una ArrayList significa que los elementos restantes de la lista se moverán, mientras que insertar o eliminar un elemento en medio de una LinkedList tiene un costo fijo.
3． LinkedList no admite el acceso eficiente a elementos aleatorios.
4． El desperdicio de espacio de ArrayList se refleja principalmente en reservar una cierta cantidad de espacio al final de la lista, mientras que el consumo de espacio de LinkedList se refleja en que cada elemento necesita consumir una cantidad considerable de espacio.
Se puede decir así: cuando la operación es agregar datos después de una columna de datos en lugar de al frente o en el medio, y necesita acceder aleatoriamente a los elementos, usar ArrayList proporcionará un mejor rendimiento cuando su operación esté al frente; una columna de datos Cuando agrega o elimina datos en el medio y accede a los elementos en orden, debe usar LinkedList.
La diferencia entre ArrayList y List en Java
colección de listas
La lista hereda de la interfaz de Colección. La lista es una colección ordenada. Los elementos de la Lista se pueden obtener/eliminar/insertar según el índice (número de secuencia: la información de posición del elemento en la colección).
A diferencia de la colección Set, List permite elementos duplicados. Para los elementos de objeto e1 y e2 que cumplen las condiciones de e1.equals(e2), pueden existir en la colección List al mismo tiempo. Por supuesto, también existen clases de implementación de Lista que no permiten elementos duplicados.
Al mismo tiempo, List también proporciona un método listIterator (), que devuelve un objeto de interfaz ListIterator. En comparación con la interfaz Iterator, ListIterator agrega métodos para agregar, eliminar y configurar elementos, y también puede avanzar o retroceder.
La relación entre Lista y Colección:
java.util.Colección[I]
+--java.util.Lista[I]
+--java.util.ArrayList [C]
+--java.util.ListaEnlazada [C]
+--java.util.Vector [C]
+--java.util.Pila [C]
Las clases de implementación de la interfaz List incluyen principalmente ArrayList, LinkedList, Vector, Stack, etc.
Relación padre-hijo.
List es una interfaz y ArrayList hereda esta interfaz y la implementa.
Cuando lo uso, normalmente uso ArrayList. Nunca he usado List. Puedes usarlo así: List list = new ArrayList();
Interfaz de colección
Colección es la interfaz de colección más básica. Una Colección representa un conjunto de Objetos, es decir, los elementos de la Colección. Algunas Colecciones permiten elementos idénticos y otras no. Algunos tipos y otros no. El SDK de Java no proporciona clases que heredan directamente de la Colección. Las clases proporcionadas por el SDK de Java son todas "subinterfaces" que heredan de la Colección, como List y Set.
Todas las clases que implementan la interfaz Colección deben proporcionar dos constructores estándar: un constructor sin parámetros para crear una Colección vacía y un constructor con parámetros de Colección para crear una nueva Colección. La Colección de entrada tiene los mismos elementos. El último constructor permite al usuario copiar una Colección.
¿Cómo iterar a través de cada elemento de la Colección? Independientemente del tipo real de Colección, admite un método iterador (), que devuelve un iterador que se puede utilizar para acceder a cada elemento de la Colección uno por uno. El uso típico es el siguiente:
Iterador it = collection.iterator(); // Obtener un iterador
mientras(es.tieneNext()) {
Objeto obj = it.next(); // Obtener el siguiente elemento
}
Las dos interfaces derivadas de la interfaz Colección son Lista y Conjunto.
Interfaz de lista:
La lista es una colección ordenada. Con esta interfaz, puede controlar con precisión la posición de inserción de cada elemento. Los usuarios pueden acceder a los elementos de la Lista utilizando el índice (la posición del elemento en la Lista, similar a un subíndice de matriz), que es similar a una matriz de Java.
A diferencia del Conjunto que se menciona a continuación, List permite los mismos elementos.
Además del método iterator() necesario para la interfaz Collection, List también proporciona un método listIterator(), que devuelve una interfaz ListIterator. En comparación con la interfaz Iterator estándar, ListIterator tiene más métodos add() y otros, lo que permite adiciones. Eliminar, establecer elementos y recorrer hacia adelante o hacia atrás.
Las clases comunes que implementan la interfaz List son LinkedList, ArrayList, Vector y Stack.
Clase de lista enlazada
LinkedList implementa la interfaz List y permite elementos nulos. Además, LinkedList proporciona métodos adicionales de obtención, eliminación e inserción al principio o al final de LinkedList. Estas operaciones permiten que LinkedList se utilice como pila, cola o deque.
Tenga en cuenta que LinkedList no tiene métodos sincronizados. Si varios subprocesos acceden a una Lista al mismo tiempo, deben implementar la sincronización de acceso ellos mismos. Una solución alternativa es construir una Lista sincronizada al crear la Lista:
Lista lista = Collections.synchronizedList(new LinkedList(...));
clase ArrayList
ArrayList implementa matrices de tamaño variable. Permite todos los elementos, incluido nulo. ArrayList no está sincronizado.
El tiempo de ejecución de los métodos size, isEmpty, get y set es constante. Sin embargo, el costo del método de suma es una constante amortizada y agregar n elementos requiere O(n) tiempo. Otros métodos tienen un tiempo de ejecución lineal.
Cada instancia de ArrayList tiene una capacidad (Capacidad), que es el tamaño de la matriz utilizada para almacenar elementos. Esta capacidad aumenta automáticamente a medida que se agregan nuevos elementos, pero el algoritmo de crecimiento no está definido. Cuando es necesario insertar una gran cantidad de elementos, se puede llamar al método sureCapacity para aumentar la capacidad de ArrayList antes de insertarlo para mejorar la eficiencia de la inserción.
Al igual que LinkedList, ArrayList tampoco está sincronizado.
Resumen: si se trata de operaciones como pilas y colas, debería considerar usar List. Si necesita insertar y eliminar elementos rápidamente, debe usar LinkedList. Si necesita un acceso aleatorio rápido a los elementos, debe usar ArrayList.
Intente devolver la interfaz en lugar del tipo real, como devolver List en lugar de ArrayList, de modo que si necesita reemplazar ArrayList con LinkedList en el futuro, no sea necesario cambiar el código del cliente. Esto es programación para la abstracción.