Théorie 4.2: liste avec tableau #

Liste par tableau plus efficace #

Si on veut être plus efficace, il faut éviter de toujours recopier les éléments
Une façon de faire est d’utiliser un tableau plus grand

public class ListeTableau<E extends Object> extends ListeJava<E> {
    
    private final int TAILLE_INITIALE = 1; // Pour tester agrandir

    private E[] grosTableau;
    private int indiceDernierElement = -1;

Quand on ajoute un élément, on peut simplement mémoriser que la liste grandit

    @Override
    public void add(E e) {

        indiceDernierElement++;

        grosTableau[indiceDernierElement] = e;

Évidemment, il faudra parfois faire grandir le tableau aussi:

    @Override
    public void add(E e) {
        if(indiceDernierElement == grosTableau.length - 1) {
            agrandir();
        }
        
        indiceDernierElement++;

        grosTableau[indiceDernierElement] = e;

Néanmoins, add est beaucoup plus efficace:
Ainsi que retirer à la fin:
C’est un exemple de compromis temps/espace mémoire
- en utilisant plus d’espace mémoire, on améliore le temps d’exécution
Par contre, retirer au début est presqu’identique:

Exemples #

Ajouts à partir d’une liste vide #

`liste`	`[null,null,null,...,null]` `indiceDernierElement == -1`
`liste.add('a')`	`[a,null,null,...,null]` `indiceDernierElement == 0`
`liste.add('b')`	`[a,b,null,...,null]` `indiceDernierElement == 1`

Un retrait au milieu #

`liste`	`[a,b,c,d,e,null,...,null]` `indiceDernierElement == 4`
`liste.remove('c')`	`[a,b,d,d,e,null,...,null]` `[a,b,d,e,e,null,...,null]` `indiceDernierElement == 3`

Implanter un mélangeur efficace #

Re-considérer notre mélangeur:

ListeJava<Character> melanger(ListeJava<Character> entree){

    ListeJava<Character> resultat;
    resultat = nouvelleListe();

    while(!entree.isEmpty()){

        int positionAuHasard = alea.nextInt(entree.size());

        Character elementAuHasard = entree.get(positionAuHasard);

        resultat.add(elementAuHasard);   // efficace

        entree.remove(positionAuHasard); // à éviter!
    }

    return resultat;
}

L’efficacité du mélangeur est améliorée:
Mais on peut faire mieux!
Comment modifier notre mélangeur pour ne pas utiliser remove?
On pourrait alors avoir:
Pour écrire du code efficace, il faut:
- savoir quelles opérations sont coûteuses sur notre structure de données