Idée appli

L'intérêt de la liste chaînée est de pouvoir ajouter/supprimer des éléments au début, au milieu ou à la fin de la liste. Or si tu fais ça dans un tableau (ce que fais l'ArrayList par exemple), à chaque insertion/suppression tu vas devoir décaler tous tes éléments pour qu'ils restent contiguës, ce qui est très coûteux, en particulier dans le cas des files qui ne font que ce genre d'opérations.

Les listes chaînées ont une autre structure de données, avec davantage de références (pointeurs en C) qui permettent d'avoir des maillons indépendants que l'on peut ajouter/supprimer unitairement, sans impacter les autres maillons de la chaîne.

Exemple d'une liste doublement chaînée :

public class ListeChainee<E> {  
    private Maillon<E> premier;
    private Maillon<E> dernier;
}

public class Maillon<E> {
    private Maillon<E> avant;
    private Maillon<E> apres;
    private E valeur;
}

Avantages :

• on n'a pas besoin d'allouer plus de mémoire que le nombre de maillons nécessaires à la chaîne
• très efficace pour l'ajout/suppression dans la liste.

Inconvénient :

• unitairement chaque maillon est un petit peu plus gros en mémoire
• pas très efficace pour retrouver un élément en plein milieu de la liste (il faut tout parcourir)

C'est pour ça qu'il existe deux structures de données distinctes, totalement différentes et faire une "LinkedList" avec un tableau ça reviendrait à faire une ArrayList (mêmes avantages/inconvénients)