ArrayList frente a LinkedList frente a vector

1. Descripción general de la lista

List, como su nombre lo indica, es una secuencia ordenada de elementos. Cuando hablamos de List, es una buena idea compararlo con Set, que es un conjunto de elementos únicos y desordenados. El siguiente es el diagrama de jerarquía de clases de Collection. Desde el diagrama de jerarquía puede obtener una idea general de las colecciones de Java.

2. ArrayList vs. LinkedList vs. Vector

Desde el diagrama de jerarquía, todos implementan Lista interfaz. Son muy similares de usar. Su principal diferencia es su implementación, lo que provoca un rendimiento diferente para diferentes operaciones.

Lista de arreglo se implementa como una matriz de tamaño variable. A medida que se agregan más elementos a ArrayList, su tamaño aumenta dinámicamente. Se puede acceder a sus elementos directamente mediante los métodos get y set, ya que ArrayList es esencialmente una matriz.

Lista enlazada se implementa como una lista de doble enlace. Su rendimiento al agregar y quitar es mejor que Arraylist, pero peor en los métodos get y set.

Vector es similar con ArrayList, pero está sincronizado.

ArrayList es una mejor opción si su programa es seguro para subprocesos. Vector y ArrayList requieren más espacio a medida que se agregan más elementos. Vector cada vez duplica su tamaño de matriz, mientras que ArrayList crece un 50% de su tamaño cada vez. LinkedList, sin embargo, también implementa Cola interfaz que agrega más métodos que ArrayList y Vector, como offer (), peek (), poll (), etc.

Nota: La capacidad inicial predeterminada de una ArrayList es bastante pequeña. Es un buen hábito construir ArrayList con una capacidad inicial más alta. Esto puede evitar el costo de cambio de tamaño.

3. Ejemplo de ArrayList

ArrayList<Integer> al = new ArrayList<Integer>();
al.add(3);
al.add(2);		
al.add(1);
al.add(4);
al.add(5);
al.add(6);
al.add(6);
 
Iterator<Integer> iter1 = al.iterator();
while(iter1.hasNext()){
	System.out.println(iter1.next());
}

4. Ejemplo de LinkedList

LinkedList<Integer> ll = new LinkedList<Integer>();
ll.add(3);
ll.add(2);		
ll.add(1);
ll.add(4);
ll.add(5);
ll.add(6);
ll.add(6);
 
Iterator<Integer> iter2 = ll.iterator();
while(iter2.hasNext()){
	System.out.println(iter2.next());
}

Como se muestra en los ejemplos anteriores, su uso es similar. La verdadera diferencia es su implementación subyacente y su complejidad operativa.

5. Vector

Vector es casi idéntico a ArrayList, y la diferencia es que Vector está sincronizado. Debido a esto, tiene una sobrecarga que ArrayList. Normalmente, la mayoría de los programadores de Java utilizan ArrayList en lugar de Vector porque pueden sincronizar explícitamente por sí mismos.

6. Rendimiento de ArrayList frente a LinkedList

La comparación de la complejidad del tiempo es la siguiente:

* add () en la tabla se refiere a add (E e), y remove () se refiere a remove (int index)

• ArrayList tiene una complejidad de tiempo O (n) para índices arbitrarios de agregar / quitar, pero O (1) para la operación al final de la lista.
• LinkedList tiene O (n) complejidad de tiempo para índices arbitrarios de agregar / quitar, pero O (1) para operaciones al final / comienzo de la Lista.

Utilizo el siguiente código para probar su rendimiento:

ArrayList<Integer> arrayList = new ArrayList<Integer>();
LinkedList<Integer> linkedList = new LinkedList<Integer>();
 
// ArrayList add
long startTime = System.nanoTime();
 
for (int i = 0; i < 100000; i++) {
	arrayList.add(i);
}
long endTime = System.nanoTime();
long duration = endTime - startTime;
System.out.println("ArrayList add:  " + duration);
 
// LinkedList add
startTime = System.nanoTime();
 
for (int i = 0; i < 100000; i++) {
	linkedList.add(i);
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("LinkedList add: " + duration);
 
// ArrayList get
startTime = System.nanoTime();
 
for (int i = 0; i < 10000; i++) {
	arrayList.get(i);
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("ArrayList get:  " + duration);
 
// LinkedList get
startTime = System.nanoTime();
 
for (int i = 0; i < 10000; i++) {
	linkedList.get(i);
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("LinkedList get: " + duration);
 
 
 
// ArrayList remove
startTime = System.nanoTime();
 
for (int i = 9999; i >=0; i--) {
	arrayList.remove(i);
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("ArrayList remove:  " + duration);
 
 
 
// LinkedList remove
startTime = System.nanoTime();
 
for (int i = 9999; i >=0; i--) {
	linkedList.remove(i);
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("LinkedList remove: " + duration);

Y la salida es:

ArrayList add:  13265642
LinkedList add: 9550057
ArrayList get:  1543352
LinkedList get: 85085551
ArrayList remove:  199961301
LinkedList remove: 85768810

La diferencia de su desempeño es obvia. LinkedList es más rápido en agregar y quitar, pero más lento en obtener. Según la tabla de complejidad y los resultados de las pruebas, podemos averiguar cuándo usar ArrayList o LinkedList. En resumen, debe preferirse LinkedList si:

• no hay una gran cantidad de acceso aleatorio de elemento
• hay una gran cantidad de operaciones de agregar / quitar