Upozorňujeme, že diskuze pod našimi online kurzy jsou nemoderované a primárně slouží k získávání zpětné vazby pro budoucí vylepšení kurzů. Pro studenty našich rekvalifikačních kurzů nabízíme možnost přímého kontaktu s lektory a studijním referentem pro osobní konzultace a podporu v rámci jejich studia. Toto je exkluzivní služba, která zajišťuje kvalitní a cílenou pomoc v případě jakýchkoli dotazů nebo projektů.
Ahoj, zdání někdy může klamat.
Podíváš-li se do zdrojového kódu, budeš překvapen, že implementace
metody indexOf je v obou případech "stejná".
ArrayList
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}LinkedList
public int indexOf(Object o) {
int index = 0;
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null)
return index;
index++;
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
}
return -1;
}Pokud bys chtěl vyhledávat v kolekci, se kterou už dále nebudeš pracovat, je vhodné si ji převést na pole a použít binární vyhledávání.
Čistě jen na diskuzi. Vytvořil jsem si velmi jednoduchý porovnávač obou
kolekcí. Tak když tak poprosím Peťu Štechmüllera, aby to nějak
okomentoval (třeba tam na něco zapomínám, nebo zátěž není dostatečná),
ale rozdíl mezi vkládáním jednoho prvku mi vychází v průměru okolo 10
milisekund pro ArrayList. Linked list to vkládá skutečně okamžitě.
Ale jak píšeš úplně na konci, že by bylo "hodně" pomalé, tak bych u
jednoho prvku očekával aspoň takových 200 milisekund.
Nebo i těch 10 může být v některých případech problém?
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class DiffList {
private static Long time, arrayTime, linkedTime;
public static void main(String[] args) {
final List<Integer> array = new ArrayList<>();
final LinkedList<Integer> linked = new LinkedList<>();
createNewList(1000, array, linked);
insertIntoList(array, linked, 50);
insertIntoList(array, linked, 654);
System.out.println();
createNewList(10000000, array, linked);
insertIntoList(array, linked, 50);
insertIntoList(array, linked, 654);
insertIntoList(array, linked, 777856);
}
public static void createNewList(int countOfElements, List array, List linked) {
array.clear();
linked.clear();
System.out.println(String.format("Porovnání vytváření obou kolekcí pro %d prvků", countOfElements));
// array time
time = System.currentTimeMillis();
for (int i = 1; i <= countOfElements; i++) {
array.add(i);
}
arrayTime = System.currentTimeMillis() - time;
// linked time
time = System.currentTimeMillis();
for (int i = 1; i <= countOfElements; i++) {
linked.add(i);
}
linkedTime = System.currentTimeMillis() - time;
ouptut(arrayTime, linkedTime);
}
public static void insertIntoList(List array, List linked, int index) {
System.out.println(String.format("Vložení prvku na index č.%d", index));
// array time
time = System.currentTimeMillis();
array.add(index, 100);
arrayTime = System.currentTimeMillis() - time;
// linked time
time = System.currentTimeMillis();
linked.add(index, 100);
linkedTime = System.currentTimeMillis() - time;
ouptut(arrayTime, linkedTime);
}
private static void ouptut(Long arrayTime, Long linkedTime) {
System.out.println(String.format("Array : Linked = %d ms : %d ms", arrayTime, linkedTime));
}
}Ahoj,
je otázka, na jak výkonném stroji jsi tohle měřil. Samozřejmě na něčem hodně výkonném to "poletí".
Primárně bych se asi zaměřil na účelu použití té datové struktury. Výhody a nevýhody pole a spojového seznamu jsou například pěkně popsány zde
Když z toho vytáhnu pro naši diskuzi podstatné věci, tak platí, že:
ArrayList
- přístup k prvku - get(i) = O(1)
- vložení prvku - add(obj) = O(n) - pro nejhorší případ, kdy je potřeba
celé pole překopírovat do většího uceleného celku
LinkedList
- přístup k prvku - O(n)
- vložení prvku - O(1)
Z toho je celkem dobře patrné, že LinkedList budeš používat přimárně tam, kde budeš chtít často vkládat prvky, ale nebudeš k nim chtít náhodně přistupovat.
Naopak ArrayList použiješ v případě, že k prvkům budeš chtít velmi často náhodně přistupovat, ale nebudeš je moc často vkládat.
Obrázek je celý špatně 
To určitě ne, protože pak by ten výstup byl 1, 2, 3, 32, 4, 5
Zobrazeno 10 zpráv z 13.
