Java Language Liste d'implémentation des classes - Avantages et inconvénients


Exemple

L'interface List est implémentée par différentes classes. Chacun d'entre eux a sa propre façon de le mettre en œuvre avec différentes stratégies et de fournir des avantages et des inconvénients différents.


Classes implémentant la liste

Ce sont toutes les classes public de Java SE 8 qui implémentent l'interface java.util.List :

  1. Classes abstraites:
    • AbstractList
    • AbstractSequentialList
  2. Classes de béton:
    • ArrayList
    • AttributeList
    • CopyOnWriteArrayList
    • LinkedList
    • Liste de rôles
    • RoleUnresolvedList
    • Empiler
    • Vecteur

Avantages et inconvénients de chaque mise en œuvre en termes de complexité temporelle

ArrayList

public class ArrayList<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, Serializable

ArrayList est une implémentation de tableau redimensionnable de l'interface List. En stockant la liste dans un tableau, ArrayList fournit des méthodes (en plus des méthodes implémentant l'interface List ) pour manipuler la taille du tableau.

Initialiser ArrayList d'Integer avec la taille 100

List<Integer> myList = new ArrayList<Integer>(100); // Constructs an empty list with the specified initial capacity.

- AVANTAGES:

Les opérations size, isEmpty, get , set , iterator et listIterator s'exécutent en temps constant. Ainsi, obtenir et définir chaque élément de la liste a le même coût :

int e1 = myList.get(0);  //   \
int e2 = myList.get(10); //    | => All the same constant cost => O(1)
myList.set(2,10);        //   /

- LES INCONVÉNIENTS:

Étant implémenté avec un tableau (structure statique), l'ajout d'éléments sur la taille du tableau a un coût important, car une nouvelle allocation doit être effectuée pour tout le tableau. Cependant, à partir de la documentation :

L'opération d'ajout s'exécute dans un temps constant amorti, c'est-à-dire que l'ajout de n éléments nécessite l'heure O (n)

Supprimer un élément nécessite O (n) temps.


AttributeList

En venant


CopyOnWriteArrayList

En venant


LinkedList

public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, Serializable

LinkedList est implémentée par une liste à double liaison, une structure de données liée qui consiste en un ensemble d’enregistrements liés de manière séquentielle appelés nœuds.

Iitialize LinkedList d'Integer

List<Integer> myList = new LinkedList<Integer>(); // Constructs an empty list.

- AVANTAGES:

L'ajout ou la suppression d'un élément au début de la liste ou à la fin a un temps constant.

myList.add(10);  // \
myList.add(0,2); //  | => constant time => O(1)
myList.remove(); // /

- CONS: De la documentation :

Les opérations indexées dans la liste traverseront la liste depuis le début ou la fin, selon ce qui est le plus proche de l'index spécifié.

Opérations telles que:

myList.get(10);    // \
myList.add(11,25); //  | => worst case done in O(n/2)
myList.set(15,35); // /

Liste de rôles

En venant


RoleUnresolvedList

En venant


Empiler

En venant


Vecteur

En venant