|
Publié le par Chloé MAHALIN

Structure de données

Qu'est-ce qu'un tableau ?

Définition

L'accès à un élément se fait à l'aide d'un indexe qui représente l'emplacement de l'élément dans la structure. Un tableau a une taille fixe. L'ajout d'un nouvel élément en fin d'un tableau plein doit passer par l'instanciation d'un nouveau tableau.

array

Un tableau peut contenir d'autres tableaux. On parle alors de matrice. Une matrice est un tableau de tableau.

  • Avantages :
    • Structure légère qui prend peu de place dans la ram
    • Les données sont accessibles librement à partir d'un index.
  • Inconvénients :
    • De taille fixe

NB : L'ArrayList de Java est une liste-tableau.

Extrait de la classe ArrayList :

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, Serializable {
    private static final int DEFAULT_CAPACITY = 10;
    private int size;
    private static final int MAX_ARRAY_SIZE = 2147483639;

    public ArrayList(int var1) {
        if (var1 > 0) {
            this.elementData = new Object[var1];
        } else {
            ...
        }
    }

La capacité par défaut d'une ArrayList est de 10. Sa taille maximum est de 2147483639 éléments. Il est tout à fait possible d'initier une ArrayList avec une taille par défaut.

Là ou l'on pourrait penser que sa taille n'est pas fixe, il faut savoir que le moteur Java réinstancie un tableau dès qu'il manque de place. Pour cela, il regarde le nombre d'éléments demandés à l'ajout : n. Si la capacité restante est inférieure à n, alors il va rajouter 8 cases (un bit) au tableau, et si cela ne suffit pas, il rajoutera alors n cases.