Dans une liste, chaque élément possède un pointeur vers l'élément suivant:
head -> item1 -> item2 -> item3 -> etc.
Pour accéder item3, vous pouvez voir clairement que vous avez besoin de marcher à partir de la tête par chaque nœud jusqu'à ce que vous atteignez item3, puisque vous ne pouvez pas sauter directement.
Donc, si je voulais imprimer la valeur de chaque élément, si j'écris ceci:
for(int i = 0; i < 4; i++) {
System.out.println(list.get(i));
}
voilà ce qui se passe:
head -> print head
head -> item1 -> print item1
head -> item1 -> item2 -> print item2
head -> item1 -> item2 -> item3 print item3
C'est horriblement inefficace parce que chaque fois que vous êtes à l'indexation, il recommence à partir du début de la liste et passe par chaque élément. Cela signifie que votre complexité est efficacement O(N^2) seulement pour parcourir la liste!
Si, au contraire, j'ai fait ceci:
for(String s: list) {
System.out.println(s);
}
alors voilà ce qui se passe:
head -> print head -> item1 -> print item1 -> item2 -> print item2 etc.
le tout dans une seule traversée, qui est - O(N).
Maintenant, il faut aller à l'autre de la mise en œuvre de l' List qui ArrayList, que l'on est soutenu par un simple tableau. Dans ce cas, les deux traversals sont équivalentes, car un tableau est contiguë, de sorte qu'il permet aléatoire de sauts à l'arbitraire des positions.
