IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Collection et Stream Java Discussion :

Différence entre LinkedList et ArrayList ?


Sujet :

Collection et Stream Java

  1. #1
    Membre averti
    Inscrit en
    Juin 2010
    Messages
    19
    Détails du profil
    Informations forums :
    Inscription : Juin 2010
    Messages : 19
    Par défaut Différence entre LinkedList et ArrayList ?
    On utilise souvent les deux structures LinkedList (liste chainée)et arraylist tableau dynamique.
    c'est quoi la différence ? exemple .

  2. #2
    Modérateur

    Avatar de Robin56
    Homme Profil pro
    Architecte de système d'information
    Inscrit en
    Juin 2009
    Messages
    5 297
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Ille et Vilaine (Bretagne)

    Informations professionnelles :
    Activité : Architecte de système d'information

    Informations forums :
    Inscription : Juin 2009
    Messages : 5 297
    Par défaut
    Citation Envoyé par van der zahir Voir le message
    On utilise souvent les deux structures LinkedList (liste chainée)et arraylist tableau dynamique.
    c'est quoi la différence ? exemple .
    Une recherche dans la FAQ t'aurais orienté : FAQ
    Responsable Java de Developpez.com (Twitter et Facebook)
    Besoin d'un article/tutoriel/cours sur Java, consulter la page cours
    N'hésitez pas à consulter la FAQ Java et à poser vos questions sur les forums d'entraide Java
    --------
    Architecte Solution
    LinkedIn : https://www.linkedin.com/in/nicolascaudard/

  3. #3
    Modérateur

    Profil pro
    Inscrit en
    Septembre 2004
    Messages
    12 582
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2004
    Messages : 12 582
    Par défaut
    Il suffit de lire les JavaDocs. Il y a aussi la FAQ.

    Pour les exemples :

    # ArrayList :

    - Une lecture list.get(i), en interne, fait à peu près ceci :

    Immédiat. Temps constant. O(1)

    - Un ajout list.add(i, item), en interne, fait à peu près ceci :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    if(array.length < newSize) {
      Object[] newArray = new Object[newSize + reserve];
      for(int j = 0; j < array.length; j++) {
        newArray[j] = array[j];
      }
      array = newArray;
    }
    for(int j = lastPosition; j >= i; j--) {
      array[j+1] = array[j];
    }
    array[i] = item;
    Très lourd en écriture, et risque de devoir réallouer un tableau.

    Temps linéaire O(n), avec risque d'un temps linéaire O(n) suppémentaire et occupation mémoire temporairement doublée.

    # LinkedList :

    - Une lecture list.get(i), en interne, fait à peu près ceci :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    ListIterator iterator = listIterator();
    int index = 0;
    while(index < i) {
      iterator.next();
      index++;
    }
    return iterator.next();
    il faut tout parcourir au lieu d'y accéder directement comme avec un tableau.

    Temps linéaire, O(n)

    - Un ajout list.add(i, item), en interne, fait à peu près ceci :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    // placer l'itérateur au bon endroit.
    // ajouter :
    iterator.add(item);
    Une fois qu'on a atteint le maillon impacté, ajouter ou retirer un élément n'est rien.

    Immédiat, temps constant O(1). Sauf si l'itérateur n'était pas au bon endroit, auquel cas, temps linéaire O(n).

    Conclusion :

    Si la liste est grande, et qu'une fois remplie il y a encore beaucoup d'ajouts/suppressions à faire n'importe où dans la liste, mais en un seul parcours, un tableau est catastrophique alors qu'une liste chaînée s'en sort bien. Le reste du temps, une ArrayList devrait aller, mais il est préférable de connaître sa taille max dès le départ.
    N'oubliez pas de consulter les FAQ Java et les cours et tutoriels Java

Discussions similaires

  1. Différence entre 2 arrayList
    Par grunk dans le forum Collection et Stream
    Réponses: 5
    Dernier message: 20/06/2012, 12h29
  2. [Liste] Différence entre LinkedList et ArrayList ?
    Par wafiwafi dans le forum Collection et Stream
    Réponses: 25
    Dernier message: 30/01/2011, 14h16
  3. Différence entre Vector et ArrayList
    Par menzlitsh dans le forum Collection et Stream
    Réponses: 4
    Dernier message: 29/03/2009, 14h32
  4. Différence entre array arraylist ?
    Par sauceaupistou dans le forum Framework .NET
    Réponses: 7
    Dernier message: 28/03/2008, 22h01
  5. Différences entre ArrayList et Vector
    Par lionrouge dans le forum Collection et Stream
    Réponses: 2
    Dernier message: 29/05/2006, 20h12

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo