Discussion :

[van der zahir]

On utilise souvent les deux structures LinkedList (liste chainée)et arraylist tableau dynamique.
c'est quoi la différence ? exemple .

[Robin56]

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

[thelvin]

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 :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

return array[i];

Immédiat. Temps constant. O(1)

- Un ajout list.add(i, item), en interne, fait à peu près ceci :

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;

Très lourd en écriture, et risque de devoir réallouer un tableau.

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 :

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();

il faut tout parcourir au lieu d'y accéder directement comme avec un tableau.

Temps linéaire, O(n)

- Un ajout list.add(i, item), en interne, fait à peu près ceci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
// placer l'itérateur au bon endroit.
// ajouter :
iterator.add(item);

Une fois qu'on a atteint le maillon impacté, ajouter ou retirer un élément n'est rien.

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.