Solución:
ArrayList es más rápido que LinkedList si accedo aleatoriamente 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 todos los elementos de la lista, por lo que puede obtener el n-ésimo elemento en tiempo constante. LinkedList tiene que recorrer la lista desde el principio para llegar al n-ésimo elemento.
LinkedList es más rápido que ArrayList para la eliminación. Entiendo este. ArrayList es más lento ya que la matriz de respaldo interna debe reasignarse.
ArrayList es más lento porque necesita copiar parte de la matriz para eliminar la ranura que se ha quedado libre. Si la eliminación se realiza con el ListIterator.remove() API, LinkedList solo hay que manipular un par de referencias; si la eliminación se realiza por valor o por índice, LinkedList potencialmente tiene que escanear la lista completa primero para encontrar los elementos que se van a eliminar.
Si eso significa mover algunos elementos hacia atrás y luego colocar el elemento en el espacio vacío del medio, ArrayList debería ser más lento.
Sí, eso 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 hay que manipular algunas referencias.
Ignore 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, parece ser alrededor de un millón de entradas) ArrayList y LinkedList funcionan actualmente como se anuncia. Sin embargo, hay algunos puntos sutiles que se aplican a principios del siglo XXI.
Según mis pruebas, la tecnología informática moderna parece dar una enorme ventaja a las matrices. Los elementos de una matriz se pueden cambiar y copiar a velocidades increíbles. Como resultado, las matrices y ArrayList, en la mayoría de las situaciones prácticas, superarán 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 cede espacio a medida que cede las entradas.
los más grande La desventaja de las matrices y ArrayList es que fragmentan la memoria libre y sobrecargan al recolector de basura. A medida que un ArrayList se expande, crea arreglos nuevos y más grandes, copia el arreglo antiguo en el nuevo y libera el anterior. La memoria se llena con grandes trozos contiguos de memoria libre que no son lo suficientemente grandes para la siguiente asignación. Eventualmente no hay espacio adecuado para esa asignación. Aunque el 90% de la memoria está libre, ninguna pieza individual es lo suficientemente grande para hacer el trabajo. El GC trabajará frenéticamente para mover las cosas, pero si se tarda demasiado en reorganizar el espacio, arrojará una OutOfMemoryException. Si no se rinde, aún puede ralentizar su programa.
Lo peor es que este problema puede ser difícil de predecir. Su programa funcionará bien una vez. Luego, con un poco menos de memoria disponible, sin previo aviso, se ralentiza o se detiene.
LinkedList utiliza pequeños y delicados bits de memoria y a los GC les encanta. Todavía funciona bien cuando está usando el 99% de su memoria disponible.
Por lo tanto, en general, use ArrayList para conjuntos de datos más pequeños que probablemente no eliminen la mayor parte de su contenido, 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 programa está bien. Crear y liberar continuamente instancias de ArrayList que usan el 10% de la memoria lo matará). De lo contrario, elija LinkedList (o un mapa de algún tipo si necesita acceso aleatorio). Si tiene colecciones muy grandes (digamos más de 100,000 elementos), no le preocupa el GC y planea muchas inserciones y eliminaciones y no tiene acceso aleatorio, ejecute algunos puntos de referencia para ver qué es más rápido.
los ArrayList class es una clase contenedora para una matriz. Contiene una matriz interna.
public ArrayList<T> {
private Object[] array;
private int size;
}
A LinkedList es una clase contenedora para una lista vinculada, con un nodo interno para administrar los datos.
public LinkedList<T> {
class Node<T> {
T data;
Node next;
Node prev;
}
private Node<T> first;
private Node<T> last;
private int size;
}
Tenga en cuenta que el código actual se utiliza para mostrar cómo puede ser la clase, no la implementación real. Sabiendo cómo puede ser la implementación, podemos hacer el análisis más detallado:
ArrayList es más rápido que LinkedList si accedo aleatoriamente 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 a ArrayList: O (1). Tiempo de acceso a LinkedList: O (n).
En una matriz, puede acceder a cualquier elemento utilizando array[index], mientras que en una lista vinculada debe navegar a través de toda la lista comenzando desde first hasta que obtenga el elemento que necesita.
LinkedList es más rápido que ArrayList para la eliminación. Entiendo este. ArrayList es más lento ya que la matriz de respaldo interna debe reasignarse.
Tiempo de eliminación para ArrayList: tiempo de acceso + O (n). Tiempo de eliminación de LinkedList: tiempo de acceso + O (1).
ArrayList debe mover todos los elementos de array[index] para array[index-1] comenzando por el elemento para eliminar el índice. La LinkedList debe navegar hasta ese elemento y luego borrar ese nodo desacoplandolo de la lista.
LinkedList es más rápido que ArrayList para la eliminación. Entiendo este. ArrayList es más lento ya que la matriz de respaldo interna debe reasignarse.
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 inserta un nuevo elemento y la matriz está llena, necesita crear una nueva matriz con más tamaño (puede calcular el nuevo tamaño con una fórmula como 2 * tamaño o 3 * tamaño / 2). LinkedList simplemente agrega un nuevo nodo al lado del último.
Este análisis no es solo en Java sino en otros lenguajes de programación como C, C ++ y C #.
Más info aquí:
- http://en.wikipedia.org/wiki/Array_data_structure
- http://en.wikipedia.org/wiki/Linked_list