Diferencias de rendimiento entre ArrayList y LinkedList

Sí, este es un tema antiguo, pero aún tengo algunas confusiones.

En Java, la gente dice:

  1. ArrayList es más rápido que LinkedList si tengo acceso aleatorio a sus elementos. Creo que el acceso aleatorio significa “dame el enésimo elemento”. ¿Por qué ArrayList es más rápido?

  2. LinkedList es más rápido que ArrayList para su eliminación. Yo entiendo este. ArrayList es más lento ya que la matriz de respaldo interna necesita ser reasignada. Una explicación de código:

    List list = new ArrayList(); list.add("a"); list.add("b"); list.add("c"); list.remove("b"); System.out.println(list.get(1)); //output "c" 
  3. LinkedList es más rápido que ArrayList para la inserción. ¿Qué significa inserción aquí? Si esto significa mover algunos elementos hacia atrás y luego poner el elemento en el lugar vacío medio, ArrayList debería ser más lento que LinkedList. Si la inserción solo significa una operación de agregar (Objeto), ¿cómo podría ser lenta?

ArrayList es más rápido que LinkedList si tengo acceso aleatorio a sus elementos. Creo que el acceso aleatorio significa “dame el enésimo elemento”. ¿Por qué ArrayList es más rápido?

ArrayList tiene referencias directas a cada elemento de la lista, por lo que puede obtener el n-ésimo elemento en tiempo constante. LinkedList tiene que atravesar la lista desde el principio para llegar al n-ésimo elemento.

LinkedList es más rápido que ArrayList para su eliminación. Yo entiendo este. ArrayList es más lento ya que la matriz de respaldo interna necesita ser reasignada.

ArrayList es más lento porque necesita copiar parte de la matriz para eliminar la ranura que se ha liberado. Si la eliminación se realiza utilizando la API ListIterator.remove() , LinkedList solo tiene que manipular un par de referencias; Si la eliminación se hace por valor o por índice, LinkedList tiene que potencialmente escanear toda la lista primero para encontrar los elementos que se eliminarán.

Si esto significa mover algunos elementos hacia atrás y luego poner el elemento en el lugar vacío medio, ArrayList debería ser más lento.

Sí, esto es lo que significa. ArrayList es de hecho más lento que LinkedList porque tiene que liberar una ranura en el medio de la matriz. Esto implica mover algunas referencias y, en el peor de los casos, reasignar toda la matriz. LinkedList solo tiene que manipular algunas referencias.

Ignora esta respuesta por ahora. Las otras respuestas, particularmente la de aix , son en su mayoría correctas. A largo plazo, son la forma de apostar. Y si tiene suficientes datos (en un punto de referencia en una máquina, parecía haber alrededor de un millón de entradas) ArrayList y LinkedList funcionan actualmente como se anuncia. Sin embargo, hay algunos puntos finos que se aplican a principios del siglo XXI.

La tecnología informática moderna parece, según mis pruebas, dar una ventaja enorme a las matrices. Los elementos de una matriz pueden desplazarse y copiarse a velocidades insanas. Como resultado, las matrices y ArrayList, en la mayoría de las situaciones prácticas, superan a LinkedList en inserciones y eliminaciones, a menudo de manera espectacular. En otras palabras, ArrayList vencerá a LinkedList en su propio juego.

La desventaja de ArrayList es que tiende a quedarse en el espacio de la memoria después de las eliminaciones, donde LinkedList deja espacio ya que renuncia a las entradas.

La desventaja más grande de las matrices y ArrayList es que fragmentan la memoria libre y sobrecargan al recolector de basura. A medida que ArrayList se expande, crea nuevas matrices más grandes, copia la matriz anterior a la nueva y libera la anterior. La memoria se llena con grandes trozos contiguos de memoria libre que no son lo suficientemente grandes para la siguiente asignación. Finalmente, no hay espacio adecuado para esa asignación. Aunque el 90% de la memoria es gratuita, ninguna pieza individual es lo suficientemente grande como para hacer el trabajo. El GC trabajará frenéticamente para cambiar las cosas, pero si tarda demasiado en reorganizar el espacio, arrojará una OutOfMemoryException. Si no se da por vencido, puede ralentizar aún más el progtwig.

Lo peor es que este problema puede ser difícil de predecir. Su progtwig funcionará bien una vez. Luego, con un poco menos de memoria disponible, sin advertencia, se ralentiza o se detiene.

LinkedList usa pequeños y delicados pedacitos de memoria y los GC lo aman. Todavía funciona bien cuando estás usando el 99% de tu memoria disponible.

Por lo tanto, en general, use ArrayList para conjuntos más pequeños de datos que probablemente no eliminen la mayor parte de sus contenidos, o cuando tenga un control estricto sobre la creación y el crecimiento. (Por ejemplo, crear una ArrayList que use el 90% de la memoria y usarla sin llenarla mientras dure el progtwig está bien. Crear y liberar continuamente instancias de ArrayList que usen el 10% de memoria lo matará). De lo contrario, vaya con LinkedList (o un mapa de algún tipo si necesita acceso aleatorio). Si tiene colecciones muy grandes (por ejemplo, más de 100.000 elementos), no le preocupa el GC, planifica muchas inserciones y eliminaciones y no tiene acceso aleatorio, ejecute algunos puntos de referencia para ver cuál es el más rápido.

La clase ArrayList es una clase contenedora para una matriz. Contiene una matriz interna.

 public ArrayList { private Object[] array; private int size; } 

Una LinkedList es una clase contenedora para una lista vinculada, con un nodo interno para administrar los datos.

 public LinkedList { class Node { T data; Node next; Node prev; } private Node first; private Node last; private int size; } 

Tenga en cuenta que el código actual se usa para mostrar cómo puede ser la clase, no la implementación real. Sabiendo cómo puede ser la implementación, podemos hacer un análisis más detallado:

ArrayList es más rápido que LinkedList si tengo acceso aleatorio a sus elementos. Creo que el acceso aleatorio significa “dame el enésimo elemento”. ¿Por qué ArrayList es más rápido?

Tiempo de acceso para ArrayList: O (1). Tiempo de acceso para LinkedList: O (n).

En una matriz, puede acceder a cualquier elemento usando array[index] , mientras que en una lista enlazada debe navegar por toda la lista comenzando desde la first hasta obtener el elemento que necesita.

LinkedList es más rápido que ArrayList para su eliminación. Yo entiendo este. ArrayList es más lento ya que la matriz de respaldo interna necesita ser reasignada.

Tiempo de eliminación para ArrayList: tiempo de acceso + O (n). Tiempo de eliminación para LinkedList: tiempo de acceso + O (1).

ArrayList debe mover todos los elementos de la array[index] a la array[index-1] empezando por el elemento para eliminar el índice. LinkedList debe navegar hasta ese elemento y luego borrar ese nodo desacoplándolo de la lista.

LinkedList es más rápido que ArrayList para su eliminación. Yo entiendo este. ArrayList es más lento ya que la matriz de respaldo interna necesita ser reasignada.

Tiempo de inserción para ArrayList: O (n). Tiempo de inserción para LinkedList: O (1).

¿Por qué ArrayList puede tomar O (n)? Porque cuando insertas un nuevo elemento y la matriz está llena, necesitas crear una nueva matriz con más tamaño (puedes calcular el nuevo tamaño con una fórmula como 2 * size o 3 * size / 2). LinkedList solo agrega un nuevo nodo al lado del último.

Este análisis no es solo en Java, sino en otros lenguajes de progtwigción como C, C ++ y C #.

Más información aquí:

Tanto remove () como insert () tienen una eficacia de tiempo de ejecución de O (n) para ArrayLists y LinkedLists. Sin embargo, la razón detrás del tiempo de procesamiento lineal proviene de dos razones muy diferentes:

En una ArrayList se llega al elemento en O (1), pero en realidad al eliminar o insertar algo se convierte en O (n) porque se deben cambiar todos los elementos siguientes.

En LinkedList, se necesita O (n) para llegar realmente al elemento deseado, porque tenemos que comenzar desde el principio hasta que scopemos el índice deseado. La eliminación o inserción es constante una vez que llegamos allí, porque solo tenemos que cambiar 1 referencia para eliminar () y 2 referencias para insertar ().

Cuál de los dos es más rápido para insertar y eliminar depende de dónde ocurre. Si estamos más cerca del comienzo, LinkedList será más rápido, porque tenemos que pasar por relativamente pocos elementos. Si estamos más cerca del final, ArrayList será más rápido, porque llegamos allí en un tiempo constante y solo tenemos que cambiar los pocos elementos restantes que lo siguen.

Bono: Si bien no hay forma de hacer estos dos métodos O (1) para una ArrayList, en realidad hay una manera de hacerlo en LinkedLists. Digamos que queremos pasar por toda la lista eliminando e insertando elementos en nuestro camino. Por lo general, usted comenzaría desde el principio por cada elemento utilizando LinkedList, también podríamos “guardar” el elemento actual en el que estamos trabajando con un iterador. Con la ayuda del Iterador, obtenemos una eficacia O (1) para eliminar () e insertar () cuando trabajamos en una Lista Vinculada. Haciéndolo el único beneficio de rendimiento que conozco, donde una Lista Vinculada siempre es mejor que una Lista de Arrays.

Respuesta a 1: ArrayList usa una matriz debajo del capó. El acceso a un miembro de un objeto ArrayList es tan simple como acceder a la matriz en el índice proporcionado, suponiendo que el índice se encuentra dentro de los límites de la matriz de respaldo. Una LinkedList tiene que iterar a través de sus miembros para llegar al enésimo elemento. Eso es O (n) para una Lista Vinculada, frente a O (1) para ArrayList.

En LinkedList los elementos tienen una referencia al elemento antes y después de él. En una ArrayList, la estructura de datos es solo una matriz.

  1. Una LinkedList necesita iterar sobre N elementos para obtener el elemento Nth. Una ArrayList solo necesita devolver el elemento N de la matriz de respaldo.

  2. La matriz de respaldo necesita ser reasignada para el nuevo tamaño y la matriz copiada sobre o cada elemento después de que el elemento eliminado deba moverse hacia arriba para llenar el espacio vacío. Una LinkedList solo necesita establecer la referencia previa en el elemento después de eliminarla antes de la eliminada y la siguiente referencia en el elemento antes del elemento eliminado en el elemento después del elemento eliminado. Más largo para explicar, pero más rápido de hacer.

  3. La misma razón que borrar aquí.

ArrayList : ArrayList tiene una estructura como una matriz, tiene una referencia directa a cada elemento. Entonces, el acceso aleatorio es rápido en ArrayList.

LinkedList : en LinkedList para obtener el elemento n. ° debe recorrer toda la lista, toma tiempo en comparación con ArrayList. Cada elemento tiene un enlace a su elemento previo & nido, por lo que la eliminación es rápida.

ArrayList: la clase ArrayList extiende AbstractList e implementa la interfaz List y RandomAccess (interfaz de marcador). ArrayList admite matrices dinámicas que pueden crecer según sea necesario. Nos da la primera iteración sobre los elementos.

LinkedList: una LinkedList se ordena por posición de índice, como ArrayList, excepto que los elementos están doblemente vinculados entre sí. Este enlace le brinda nuevos métodos (más allá de lo que obtiene de la interfaz de la Lista) para agregar y eliminar desde el principio o el final, lo que lo convierte en una opción fácil para implementar una stack o cola. Tenga en cuenta que una LinkedList puede iterar más lentamente que una ArrayList, pero es una buena opción cuando necesita una inserción y eliminación rápida. A partir de Java 5, la clase LinkedList se ha mejorado para implementar la interfaz java.util.Queue. Como tal, ahora es compatible con los métodos comunes de cola: peek (), poll () y offer ().

Incluso parecen idénticos (la misma lista de interfaz implementada, no segura para subprocesos), ofrecen diferentes resultados en términos de rendimiento en agregar / eliminar y tiempo de búsqueda y consumo de memoria (LinkedList consume más).

LinkedLists se puede usar si usa alta inserción / eliminación con el rendimiento O (1). ArrayLists puede usarse si usa operaciones de acceso directo con rendimiento O (1)

Este código puede dejar en claro estos comentarios y puede intentar comprender los resultados de rendimiento. (Perdón por el código de la placa de la caldera)

 public class Test { private static Random rnd; static { rnd = new Random(); } static List testArrayList; static List testLinkedList; public static final int COUNT_OBJ = 2000000; public static void main(String[] args) { testArrayList = new ArrayList<>(); testLinkedList = new LinkedList<>(); insertSomeDummyData(testLinkedList); insertSomeDummyData(testArrayList); checkInsertionPerformance(testLinkedList); //O(1) checkInsertionPerformance(testArrayList); //O(1) -> O(n) checkPerformanceForFinding(testArrayList); // O(1) checkPerformanceForFinding(testLinkedList); // O(n) } public static void insertSomeDummyData(List list) { for (int i = COUNT_OBJ; i-- > 0; ) { list.add(new String("" + i)); } } public static void checkInsertionPerformance(List list) { long startTime, finishedTime; startTime = System.currentTimeMillis(); int rndIndex; for (int i = 200; i-- > 0; ) { rndIndex = rnd.nextInt(100000); list.add(rndIndex, "test"); } finishedTime = System.currentTimeMillis(); System.out.println(String.format("%s time passed at insertion:%d", list.getClass().getSimpleName(), (finishedTime - startTime))); } public static void checkPerformanceForFinding(List list) { long startTime, finishedTime; startTime = System.currentTimeMillis(); int rndIndex; for (int i = 200; i-- > 0; ) { rndIndex = rnd.nextInt(100000); list.get(rndIndex); } finishedTime = System.currentTimeMillis(); System.out.println(String.format("%s time passed at searching:%d", list.getClass().getSimpleName(), (finishedTime - startTime))); } }