2.8 KiB
Principe
Une liste est une structure de données abstraites. C'est une collection d'éléments que l'on a ordonnés. On peut donc les numéroté et en obtenir un indice/rang, le premier élément est l'indice 0.
Les opérations basiques peuvent être :
- consulter l'élément à un indice donné
- remplacer l'élément à un indice donné
- supprimer l'élément à un indice donné
- insérer un élément à un indice donné
[!info] Il est difficile d'assurer une performance idéale pour toutes ces opérations à la fois. Mini conclusion : les listes c'est mauvais on sait pas ce que ça donne et génère souvent une perte de performance.
En java
L'interface Collection représente les collections en général. Elle hérite de l'interface Iterable, ce qui la rend compatible avec les boucles énumératives. L'interface List hérite de Collection et représente une liste. Il y a aussi Iterator avec ses méthode :
- boolean hasNext : Returns
trueif the iteration has more elements. - E remove(int index) Removes the element at the specified position in this list (optional operation).
- add(int index, E element)Inserts the specified element at the specified position in this list (optional operation). Parmi les classes qui réalisent List, on note ArrayList et LinkedList
Codage Pour coder une liste avec un tableau, on fait correspondre les indices du tableau avec les indices de la liste. Une liste n'a pas de limite avec les indices de la liste. Une liste n'a pas de limite de capacité. On peut seulement réaliser une liste bornée, ou prévoir un redimensionnement en cas de besoin.
Pour coder une liste avec une liste chaînée, on fait correspondre l'ordre des maillons avec l'ordre de la liste. Les maillons nécessitent une classe séparée, qui contient typiquement des méthodes récursives. Les objets de cette classe ne doivent pas être exposés aux utilisateurs de la liste !
Quand on déclare une variable ou un attribut qui va désigner une liste, on utilise le type List et pas le type concret de l'objet. Ceci permet de préserver la capacité à changer la réalisation.