Implémentation d'une liste

Bonjour à tous et à toutes.
On sait qu’on peut implémenter une liste en tant que structure de données à l’aide d’un tableau. Bien entendu ce choix n’est pas judicieux et donc à éviter dans la partie conception détaillée de la liste. Mais, cela existe et même proposé dans un livre.
Quel est votre avis sur la question ?
Peut-on, dans ce contexte, tenir le discours habituel qui compare une liste (accès séquentiel, tri facile, …) avec un tableau (accès direct, tri difficile,….) ? Qui à mon avis se trouve faussé par cette implémentation. On devrait même pas se permettre cette comparaison.
Merci à vous

Tu peux être plus clair sur ta question? Parce qu'un tableau n'est certainement pas difficile à trier, bien au contraire. Une liste n'est pas restreinte à un accès séquentiel. Elle n'a pas nécessairement le tri facile non plus.

En fait, j'ai l'impression que tu confond liste et liste chainée.

Une liste est bien plus difficile à trier qu'un tableau. Le seul algorithme qui tient la route pour trier une liste c'est le tri à bulle, alors que sur un tableau on peut utiliser quicksort ou ce qu'on veut.
Tu parles peut-être de la maintenir triée, c'est autre chose, mais à ce niveau-là il vaut mieux un arbre de recherche.
Les points forts d'une liste c'est l'insertion et la suppression d'éléments ailleurs qu'à la fin.

Concernant ta question, je dirais que ça dépend comment la liste est implémentée avec un tableau. À la base, la mémoire de l'ordinateur c'est un tableau, donc forcément, toutes les implémentations de liste utilisent un tableau. C'est juste qu'en principe pour chaque élément elles réservent un espace mémoire, qui contient cet élément ainsi que où trouver en mémoire le suivant et le précédent. On peut faire pareil dans un tableau : chercher un index où il n'y a pas d'élément, et y mettre un élément, ainsi que quel est l'index dans le tableau où se trouve le précédent, pareil pour le suivant.
Disons que c'est plus difficile, parce qu'on se tape le problème de l'allocation mémoire au lieu de laisser le langage s'en charger pour nous.


... Et il faut bien reconnaître que c'est des questions pas très pertinentes pour Java, tout ça.

Ok. Merci pour ta réponse.
On peut implémenter le principe d'une liste de plusieurs manières!
J'ai implémenté dernièrement une liste chaînée et ce n'est pas ce principe dont je parle.
Pour une étude de complexité, j'ai également implémenté en java une liste à l'aide d'un tableau. Ce n'était pas top! D’où ce post.

Je reformule ma question :

On sait qu’on peut implémenter une liste en tant que structure de données à l’aide d’un tableau.
Bien entendu ce choix n’est pas judicieux et donc à éviter dans la partie conception détaillée de la liste. Mais, cette solution existe et même proposée dans un livre.
On a également l'habitude de comparer les deux structures liste et tableau dans les différents cours, sans avoir le détail d'implémentation, en se basant sur plusieurs points tels que le type d’accès (direct, séquentiel), les types de traitements, connaissance ou pas de la taille dès le début, ....

Quel est votre avis sur la question ?

Peut-on, dans ce contexte, tenir le discours habituel qui compare une liste avec un tableau ? Qui à mon avis se trouve faussé par cette implémentation. On devrait même pas se permettre cette comparaison.

J'espère être clair et votre avis est précieux.

Merci à vous

Merci Thelvin.

Citation:

---

Et il faut bien reconnaître que c'est des questions pas très pertinentes pour Java, tout ça.

---

C'est vrai, c'est au delà d'une simple utilisation de java. C'est bien à savoir quand même! La preuve , c'est que tu m'as convaincu pour cette petite curiosité.
Merci beaucoup

Citation:

---

Envoyé par wafiwafi

On sait qu’on peut implémenter une liste en tant que structure de données à l’aide d’un tableau.
Bien entendu ce choix n’est pas judicieux et donc à éviter dans la partie conception détaillée de la liste.

---

Y a pas de raison. L'implémentation de la liste la plus utilisé en java, c'est l'ArrayList, elle est implémentée via l'utilisation d'un tableau, rapide d'accès aléatoire et pas spécialement lente en accès séquentiel, et elle occupe bien moins de mémoire qu'une liste chainée. Elle ne deviens problématique que lorsque la taille deviens conséquente (besoin d'une zone de mémoire contigüe) et ne garantis pas les performances à l'insertion.

Citation:

---

Envoyé par wafiwafi

On a également l'habitude de comparer les deux structures liste et tableau dans les différents cours, sans avoir le détail d'implémentation, en se basant sur plusieurs points tels que le type d’accès (direct, séquentiel), les types de traitements, connaissance ou pas de la taille dès le début, ....

---

Comme tu l'a bien relevé, un tableau, on sais ce que sait, une liste on sais pas ce que sait. Si tu ne définis pas plus clairement "liste", ça peut représenter tout et n'importe quoi et tu sais même pas comparer liste avec liste :)

C'est très pertinent ce que tu viens de dire!! Merci à toi.