On utilise souvent les deux structures LinkedList (liste chainée)et arraylist tableau dynamique.
c'est quoi la différence ? exemple .
Version imprimable
On utilise souvent les deux structures LinkedList (liste chainée)et arraylist tableau dynamique.
c'est quoi la différence ? exemple .
Une recherche dans la FAQ t'aurais orienté : FAQ
Il suffit de lire les JavaDocs. Il y a aussi la FAQ.
Pour les exemples :
# ArrayList :
- Une lecture list.get(i), en interne, fait à peu près ceci :
Immédiat. Temps constant. O(1)Code:return array[i];
- Un ajout list.add(i, item), en interne, fait à peu près ceci :
Très lourd en écriture, et risque de devoir réallouer un tableau.Code:
1
2
3
4
5
6
7
8
9
10
11 if(array.length < newSize) { Object[] newArray = new Object[newSize + reserve]; for(int j = 0; j < array.length; j++) { newArray[j] = array[j]; } array = newArray; } for(int j = lastPosition; j >= i; j--) { array[j+1] = array[j]; } array[i] = item;
Temps linéaire O(n), avec risque d'un temps linéaire O(n) suppémentaire et occupation mémoire temporairement doublée.
# LinkedList :
- Une lecture list.get(i), en interne, fait à peu près ceci :
il faut tout parcourir au lieu d'y accéder directement comme avec un tableau.Code:
1
2
3
4
5
6
7 ListIterator iterator = listIterator(); int index = 0; while(index < i) { iterator.next(); index++; } return iterator.next();
Temps linéaire, O(n)
- Un ajout list.add(i, item), en interne, fait à peu près ceci :
Une fois qu'on a atteint le maillon impacté, ajouter ou retirer un élément n'est rien.Code:
1
2
3 // placer l'itérateur au bon endroit. // ajouter : iterator.add(item);
Immédiat, temps constant O(1). Sauf si l'itérateur n'était pas au bon endroit, auquel cas, temps linéaire O(n).
Conclusion :
Si la liste est grande, et qu'une fois remplie il y a encore beaucoup d'ajouts/suppressions à faire n'importe où dans la liste, mais en un seul parcours, un tableau est catastrophique alors qu'une liste chaînée s'en sort bien. Le reste du temps, une ArrayList devrait aller, mais il est préférable de connaître sa taille max dès le départ.