Comment ArrayList travail?

Quelle structure de données une liste de tableaux d'utiliser en interne?

  • Astuce: JDK est open source.
  • Et Grep code a la sources disponibles en ligne
  • Non seulement l'open source, c'est l'été communiqués depuis le 1er jour. (Indice: src.zip à l'intérieur de votre JDK.)
InformationsquelleAutor AutoMEta | 2010-08-12
  1. 60

    En interne un ArrayList utilise un Object[].

    À mesure que vous ajoutez des éléments à une ArrayList, la liste de contrôle pour voir si la sauvegarde de tableau a de la place à gauche. Si il ya de la place, le nouvel élément est ajouté à la prochaine vide de l'espace. Si il n'y a pas de salle de, une nouvelle, plus grande, tableau est créé, et l'ancien tableau est copié dans le nouveau.

    Maintenant, il n'y a plus de place à gauche, et le nouvel élément est ajouté dans le prochain espace vide.

    Puisque les gens aiment vraiment le code source:

    /**
 * The array buffer into which the elements of the ArrayList are stored.
 * The capacity of the ArrayList is the length of this array buffer.
 */
private transient Object[] elementData;

    Tout droit sorti de la JDK.

    • Mais la matrice de valeurs de même type de données où comme un arrayList peut stocker différents types de données
    • il a tout simplement une Object[] comme la sauvegarde de la structure de données. Et un Object[] peut contenir quoi que ce soit.
    • c'est parce que la sauvegarde de tableau est un Object[]
    • ArrayList capacité initiale est de 10. Pour explorer plus en profondeur, visitez le site codenuclear.com/how-arraylist-works-internally-java
    InformationsquelleAutor jjnguy
  2. 19

    Il utilise un Object[], et fait une grande matrice lorsque le tableau est plein.

    Vous pouvez lire les le code source ici.

    InformationsquelleAutor SLaks
  3. 9

    ArrayList utilise un Tableau d'Objet à stocker les données en interne.

    Lorsque vous initialisez une liste de tableaux, un tableau de taille 10 (capacité défaut) est créé et un élément ajouté à la liste de tableaux est en fait ajouté à ce tableau. 10 est la taille par défaut et il peut être passé en paramètre lors de l'initialisation de la liste de tableaux.

    Lors de l'ajout d'un nouvel élément, si le tableau est plein, un nouveau tableau de plus de 50% de la taille initiale est créée et le dernier tableau est copié dans ce nouvel ensemble, de sorte que maintenant il y a des espaces vides pour le nouvel élément à ajouter.

    Depuis le sous-jacent de la structure des données utilisées est un tableau, il est assez facile d'ajouter un nouvel élément à la liste de tableaux il est ajouté à la fin de la liste. Lorsqu'un élément est ajouté n'importe où ailleurs, dire que le début, puis tous les éléments doivent avoir à se déplacer d'une position vers la droite pour créer un espace vide au début pour le nouvel élément à ajouter. Ce processus est de temps (linéaire en temps). Mais l'Avantage de ArrayList est que de la récupération d'un élément à n'importe quelle position est très rapide (constante de temps), en tant que sous-jacente, il est tout simplement à l'aide d'un tableau d'objets.

    • Merci, cette info est très utile pour les personnes à comprendre comment la taille de la liste de tableaux se développe lorsque vous êtes en train d'ajouter, disons, 4000 éléments... Ne savais pas qu'il double la durée initiale de 10 à chaque fois qu'il est plein.
    InformationsquelleAutor kapil
  4. 1

    ArrayList a la structure de base de données:

    private transient Object[] elementData;

    Lorsque nous avons effectivement créer un ArrayList le morceau de code suivant est exécuté:

     this.elementData = new Object[initial capacity];

    ArrayList peuvent être créés dans les deux méthodes mentionnées ci-après:

    1. List list = new ArrayList();

    Le constructeur par défaut est appelé et permettra de créer en interne un tableau de Object avec la taille par défaut 10.

    1. List list = new ArrayList(5);

    Lorsque nous créons une ArrayList de cette façon, un constructeur avec un argument entier est appelé et
    créer un tableau de Object avec la taille par défaut 5.

    À l'intérieur de la add méthode est de vérifier que la taille actuelle de rempli d'éléments est supérieure/égale à la taille maximale de la
    ArrayList alors il va créer de nouveaux ArrayList avec la taille de la nouvelle arraylist = (current arraylist*3/2)+1 et de copier les données de l'ancien au
    nouveau tableau liste.

    InformationsquelleAutor Manikandan Rajaminor
  5. 0

    Elle utilise un tableau, et un couple d'entiers pour indiquer la première valeur de la dernière valeur de l'indice de

    private transient int firstIndex;

private transient int lastIndex;

private transient E[] array;

    Voici un exemple de mise en œuvre.

    InformationsquelleAutor Tom
  6. 0

    Généralement, des structures comme ArrayLists sont mis en œuvre par un bon vieux tableau défini à l'intérieur de la classe et ne sont pas directement accessibles à l'extérieur de la classe.

    Une certaine quantité d'espace est initialement allouée pour la liste, et lorsque vous ajoutez un élément qui dépasse la taille de la matrice, la matrice sera réinitialisé avec une nouvelle capacité (qui est généralement un multiple de la taille actuelle, de sorte que le cadre n'est pas constamment ré-allocation des tableaux avec chaque nouvelle entrée est ajoutée).

    InformationsquelleAutor Ryan Brunner
  7. 0

    La La plate-forme Java code source est disponible gratuitement. Voici un extrait:

    public class ArrayList<E> extends AbstractList<E>
  implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
  /**
   * The array buffer into which the elements of the ArrayList are stored.
   * The capacity of the ArrayList is the length of this array buffer.
   */
  private transient E[] elementData;
  .
  .
  .
}
    InformationsquelleAutor John Topley
  8. 0

    ArrayLists utiliser des tableaux pour stocker les données. Une fois le nombre d'éléments dépasse l'allocation d'un tableau, il copie les données dans un autre tableau, probablement le double de la taille.

    Un (mineur) de gain de performance est prise lors de la copie de la matrice, il est donc possible de définir la taille du tableau interne dans le constructeur de la liste de tableau.

    En outre, il met en œuvre java.util.Collection et et java.util.list, et il est donc possible d'obtenir l'élément à l'index spécifié, et itératif (comme un tableau).

    InformationsquelleAutor Jes
  9. 0

    Il utilise un Objet[]. Lorsque le tableau est plein, il crée un nouveau tableau qui est 50% plus grand en taille et copie les éléments de courant à nouveau tableau. Cela se fait automatiquement.

    • Pourriez-vous ajouter toute référence à l'appui de ce que vous dites?
    InformationsquelleAutor Krishna