Différence entre LinkedList et ArrayList ?

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

Citation:

---

Envoyé par van der zahir

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 :

Code:

---

return array[i];

---

Immédiat. Temps constant. O(1)

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

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;

---

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:

---

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:

---

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.