Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > fr.comp.lang.java > #1746

Re: LinkedList ou ArrayList?

Show all headers | View raw

Bonjour

Le Thu, 11 Apr 2019 22:27:01 +0000, jp a écrit :

> J'ai un petit programme qui utilise un Vector et qui effectue beaucoup
> d'opérations sur ce dernier. J'envisage de remplacer ce Vector par une
> structure de données plus rapide. Je n'ai pas besoin qu'elle soit
> Synchronized.
> 
> Est-ce que quelqu'un peut me dire ce qui est le plus rapide entre une
> LinkedList ou une ArrayList?

ArrayList est la structure qui ressemble le plus à Vector (et qu'on 
utilise à la place en général).

Pour faire le choix entre ces deux structures de données, il faut 
comprendre comment elles fonctionnent :

ArrayList/Vector est un tableau extensible : on peut ajouter des données 
dedans puis, quand il est plein, un tableau plus grand est alloué, les 
données qui se trouvaient dans l'ancien sont recopiées dans le nouveau.
    https://fr.wikipedia.org/wiki/Tableau_(structure_de_donn%C3%A9es)

LinkedList est une liste chaînée, composées de cellules liées les unes 
aux autres (chacune contient des références à ses voisines, ce qui permet 
de passer de l'une à l'autre). Quand on veut ajouter une valeur, on 
ajoute une cellule à la liste.
    https://fr.wikipedia.org/wiki/Liste_cha%C3%AEn%C3%A9e
    (en java il s'agit d'une liste doublement chaînée)

Note que s'il y a 10 valeurs dans ta liste, peu importe la représentation 
que tu choisis. S'il est possible qu'il y ait beaucoup de valeurs, mieux 
vaut choisir la structure appropriée à tes traitements, en particulier 
s'il y a beaucoup d'opérations dessus ; ça peut dépendre aussi de si tu 
veux optimiser les modifications ou les consultations :
    * ArrayList
        - Insertions très lentes en début de tableau (il faut décaler
          toutes les valeurs existantes et parfois tout recopier dans un
          plus grand tableau).
        - Insertions lentes en fin de tableau (il faut parfois
          créer un tableau plus grand et tout recopier dedans).
        - Accès très rapide à un élément par son indice (il suffit de
          calculer que la case 33 se trouve à telle position,
          puisqu'elles se trouvent physiquement les unes à la suite des
          autres).
        - Parcours rapide dans l'ordre (avec un itérateur).
    * LinkedList
        - Insertions très rapides en tête et en queue (il suffit
          d'ajouter une cellule).
        - Insertions lentes au milieu (il faut parcourir la liste
          avant de trouver l'endroit où insérer la nouvelle valeur).
        - Accès lent à un élément quelconque par son indice (plus rapide
          près du début ou de la fin, plus long si c'est au milieu) : il
          faut parcourir la liste en suivant les liens de cellule en
          cellule jusqu'à celle recherchée.
        - Parcours rapide dans l'ordre (avec un itérateur).

Quand je parle d'itérateur, ça peut être avec un itérateur explicite :
    Iterator<String> iterateur = chaines.iterator() ;
    for (...)
ou bien implicite :
    for (String chaine : chaines)

Pour formaliser les choses, on utilise la notation O pour caractériser le 
temps de réalisation des opérations sur les structures de données en 
fonction du nombre d'éléments dedans (en fait donner une idée de comment 
croît ce temps quand la structure de données contient de plus en plus de 
valeurs).

Quelques exemples :
    - O(1)         : la durée de l'opération de dépend pas du nombre
                     d'éléments dans la structure (temps constant).
    - O(n)         : durée proportionnelle au nombre d'éléments.
    - O(n²)        : durée proportionnelle au carré du nombre d'éléments.
    - O(n x log n) : un peu plus mauvais que la durée proportionnelle,
                     mais pas aussi dramatique que O(n²).

Appliqué aux deux structures plus haut :
    * ArrayList
        - Insertion en début de tableau : O(n²)
        - Insertion en fin de tableau : O(n) [parfois il faut recopier
          tout le tableau dans un plus grand]
        - Insertion en milieu de tableau : comme l'insertion en début
        - Accès à un élément quelconque par son indice : O(1)
        - Parcours des éléments avec un itérateur : O(n)
    * LinkedList
        - Insertion en début de liste : O(1)
        - Insertion en fin de liste : O(1)
        - Insertion en milieu de liste : O(n) [il faut partir d'un
          bord pour trouver l'endroit où faire l'insertion]
        - Accès à un élément quelconque par son indice : O(n)
        - Parcours des éléments avec un itérateur : O(n)

Je n'ai pas traité le cas des suppressions d'éléments : pour les listes 
c'est pareil, pour les tableaux c'est un peu moins gênant que les 
insertions parce qu'il n'y a jamais besoin d'agrandir le tableau, par 
contre il faut bien décaler tous les éléments suivants d'un rang vers la 
gauche.

J'ai ici négligé les caches et autres considérations de bas niveau.

Back to fr.comp.lang.java | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

LinkedList ou ArrayList? jp <bloiiing@yahoo.invalid> - 2019-04-11 22:27 +0000
  Re: LinkedList ou ArrayList? Yliur <yliur@free.fr> - 2019-04-12 08:49 +0000
  Re: LinkedList ou ArrayList? Elhwen Dico <elhwen.dicote@gmail.com> - 2019-04-13 18:43 +0200
  Re: LinkedList ou ArrayList? jp <bloiiing@yahoo.invalid> - 2019-04-13 20:24 +0000
    Re: LinkedList ou ArrayList? Elhwen Dico <elhwen.dicote@gmail.com> - 2019-04-14 00:03 +0200
      Re: LinkedList ou ArrayList? jp <bloiiing@yahoo.invalid> - 2019-04-13 23:48 +0000
  Re: LinkedList ou ArrayList? areslanoaresso <nospam_zaki0zako@gmail.com.invalid> - 2020-02-06 15:46 -0600

csiph-web