Complexité Spacio-temporelle des listes

Pour un projet d'étude, j'aurais besoin d'utiliser les listes. Le but est de modéliser un réseau de transport d'une grande ville et donner le plus court chemin. On pourra modifier le réseau (ajouter, supprimer une station). J'hésite entre les ArrayList, les LinkedList et les Vector. Existe-t-il d'autres listes dans l'API de Java ?

Ma question est : quelle est là meilleure classe à utiliser ? Je pense que la différence se fait au niveau des compléxités spaciales et temporelles de ces listes ? Pouvez-vous me rappeler les compléxités pour les ajout/suppression d'élements et les parcours ?

D'avance, merci

Salut,

Alors pour faire très simple (et surtout parceque je n'en sais pas plus :lol: ), les ArrayList sont plus performantes lorsque tu les parcours grâce à un entier :

Code:

---

1 2 3 4

for (int i = 0 ; i < taListe.size () ; ++i) { taListe.get (i); }

---

Et tu peux atteindre un objet de la liste en connaissant sa position dans la liste.

Et inversement les LinkedList sont plus efficaces avec un iterateur.
Les vectors ne sont plus a utiliser.

voila a+

Salut,
j'avais fais un projet du meme genre que le tient. Le truc donnait les plus court chemin par dijkstra enfin je ne me rapelle plus tres bien et j'arrive plus a retrouver ce truc. Je peux te dire j'avai utiliser des ArrayList<Noeud>.
Noeud contenait elle meme 2 arraylist(preecesseurs et sucesseurs). Si je trouve des infos la dessus je te les file.

Il existe trois structures de données clés pour ce cas :

Les tableaux : accès en O(1) , ajout et suppression n'impote où en O(n)

Les listes chainées ( java.util.LinkedList<E> ): accès et ajout dans la liste en O(n/2), ajout et supression et début et fin de liste en O(1).

Les ArrayList (qui sont en fait des listes chainnées de tableaux) et qui sont un bon compromis entre les deux.

Il fauit analyser ton problème et savoir quelle opération va être fortement utilisée, et choisir la structure de donnée en fonction de cela.

J'ai oublié de dire : les listes ont une complexité mémoire en 3n (3 références par élément), les tableaux en 1 (une référence par taleau quel que soit sa taille) et les ArrayList c'est intermédiaire, cela dépend de la taille des tableaux.

:ccool:

Sinon tu as aussi la FAQ sur les listes qui résume un peu le truc :
Listes
Il serait pas mal d'ajouter tes précisions à celle-ci Razgriz ;)