Discussion :

[wafiwafi]

Bonjour à toutes et à tous,

J'ai lu que la structure Arraylist permet d'accéder à un élément avec une complexité en O(1). Ce qui est logique car les accès sont directs.
On a toujours dit que le type liste est caractérisé par un accès séquentiel aux objets.
Est ce que Arraylist peut être considérée dans ce cas comme une liste?
J'espère être clair

[wafiwafi]

Une ArrayList est gérée en interne par un tableau. On peut donc accéder en temps constant à n’importe quel élément par « monArrayList.get(nb); ».

Ceci explique le à O(1).

Avis personnel : Pour moi, arraylist doit être considérée comme un tableau intelligent qui s'ajuste automatiquement, ... sur lequel, on peut appeler des méthodes.
Il me gène de voir Arraylist implémenter l' Interface List ! Qu'est ce qu'elle a de liste ? (Tout en sachant que je dois zapper un truc pour tomber dans cette ambiguïté très gênante pour moi)

Je vous l'accorde des questions qui vous paraissent peu importantes. Mais, que c'est important pour fixer les idées.

[professeur shadoko]

dans l'acceptation java: une liste permet de ranger dynamiquement des éléments les uns derrière les autres (et bien d'autres choses)
Ensuite une LinkedList est effectivement gérée par des liens "suivant" "précédent" et donc la complexité d'accès n'est pas optimum.
Oui une ArrayList est conforme au contrat de l'interface List telle que définie dans la doc ... même si elle est à accès direct (propriété RandomAccess)
L'implantation comme un seul tableau ne doit pas être considérée comme primordiale: on pourrait décider de reimplanter ArrayList comme un tableau de tableau (plus efficace sur des grosses listes du fait des réallocations)

[wafiwafi]

Merci.
C'est clair.