Praktycznie rzecz biorąc, LinkedList#removeFirst
jest bardziej efektywny, ponieważ działa na podwójnie połączonej liście, a usunięcie pierwszego elementu polega w zasadzie tylko na odłączeniu go od nagłówka listy i zaktualizowaniu następnego elementu jako pierwszego:
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
ArrayList#remove
pracuje na wewnętrznej matrycy wymagającej shiftting wszystkie subsequents elementów jednej pozycji w lewo o kopiowaniu przez subarray:
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
z drugiej ręcznie, operacja LinkedList#get
wymaga przewinięcia połowy całej listy w celu pobrania elementu z określonego indeksu - w najgorszym przypadku. ArrayList#get
ma bezpośredni dostęp do elementu o określonym indeksie, ponieważ działa on w tablicy.
Moja zasada rekomendacji dotyczących efektywności tutaj byłoby:
- Zastosowanie
LinkedList
jeśli dużo add
/remove
zrobić w porównaniu z pobierania operacji (np .: get
);
- Użyj
ArrayList
, jeśli wykonasz wiele operacji pobierania w porównaniu z add
/remove
.
a) określić wydajność. Istnieje wiele zmiennych, które można zmierzyć, takich jak czas, wydajność, wykorzystanie pamięci itp. B) Napisz kod testowy, używając stoperów (klasy, nie fizycznych) i rzeczy tego rodzaju, aby je porównać i dowiedzieć się. –
"Jaki jest najskuteczniejszy sposób na zrobienie tego?" Zależy od twojego scenariusza. Zobacz http://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist – Shar1er80