On utilise souvent les deux structures LinkedList (liste chainée)et arraylist tableau dynamique.
c'est quoi la différence ? exemple .
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
Responsable Java de Developpez.com (Twitter et Facebook)
Besoin d'un article/tutoriel/cours sur Java, consulter la page cours
N'hésitez pas à consulter la FAQ Java et à poser vos questions sur les forums d'entraide Java
--------
Architecte Solution
LinkedIn : https://www.linkedin.com/in/nicolascaudard/
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 : Sélectionner tout - Visualiser dans une fenêtre à part 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 : Sélectionner tout - Visualiser dans une fenêtre à part
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 : Sélectionner tout - Visualiser dans une fenêtre à part
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 : Sélectionner tout - Visualiser dans une fenêtre à part
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.
Partager