Un type de données de collecte simple trouvé dans certaines langues / plates-formes (telles que Java ou .NET). La liste de tableaux implémente une liste à l'aide d'un tableau, bénéficiant des deux points forts des DS.

ArrayList désigne souvent un type de données abstrait (ADT) trouvé dans certains langages / plateformes de programmation courants qui représente un tableau "évolutif" (de taille dynamique).

En Java:

java.util.ArrayListest une classe de la bibliothèque standard Java SE qui implémente l'interface List. La classe ArrayListreprésente le contenu de la liste à l'aide d'un tableau Object, qu'elle réalloue au besoin pour s'adapter à la croissance de la liste.

La complexité des opérations List courantes sur les tableaux est la suivante:

  • List.add(Object) - O(1) amorti (voir ci-dessous).
  • List.get(int) - O(1)
  • List.remove(int) - O(N) dans le cas général
  • List.contains(Object) - O(N) dans le cas général

Le coût amorti de add est basé sur l'argument suivant. Supposons que vous commencez avec une liste de tableaux vide et ajoutez des éléments N un par un. Chaque fois que vous ajoutez un élément, la méthode add vérifie si le tableau de sauvegarde de la liste est plein. Si tel est le cas, il alloue un nouveau tableau de sauvegarde de deux fois la taille de l'actuel, puis copie les éléments existants de l'ancien tableau vers le nouveau. Si vous comptez le nombre de copies d'éléments qui se produisent dans ce processus, vous constaterez que lorsque la taille du tableau s'étend à N == initial * 2^P, un total de initial *2^P - 1 copies aura eu lieu, ce qui est inférieur à N copies. Ajoutez ensuite N affectations de nouveaux éléments et vérifications des limites, et le coût total est clairement proportionnel à N, lorsqu'il est cumulé sur N appels à add. Fait alors du coût moyen d'un seul appel une constante; c'est-à-dire O(1).

Dans .NET:

System.Collections.ArrayListdans la bibliothèque de classes .NET Framework, comme son homologue en Java, représente également un tableau de taille dynamique. Il est devenu en grande partie obsolète avec l'introduction du System.Collections.Generic.List<T>générique saisissez .NET 2, qui a l'avantage (dans la plupart des cas) d'être fortement typé, et d'éviter la mise en boîte inutile des types de valeur.

Tags associés

arrayslist