liste chainée ou array

Bonjour,

tout d'abord je me présente :
je suis débutant en C, c'est le premier language compilé que j'apprends, mais je programme depuis deux ans ; je connais principalement javascript et python.

Pour en venir à mon problème :

je me demande ce qu'il est préférable d'utiliser entre une liste chainée et une liste "simple" de type array :

Pour créer la liste, j'ai une structure de départ. Un membre de cette structure me permet de trouver le noeud suivant (via une fonction). Je mets les éléments au fur et à mesure dans la liste. Je teste un autre membre de la structure pour savoir si j'ai fini. Par la suite, je veux accèder aux élements à partir d'un indice.

J'ai pensé à une liste simple, j'alloue 1, puis quand ça dépasse je réalloue (realloc) 2 puis 4, 8, etc.
Sinon, j'ai pensé aussi à utiliser une liste chainée, mais par la suite, je ne pourrais plus accéder aux éléments en temps constant.

Quelle est la meilleure méthode entre celles-la ? Y'en a-t-il d'autres auxquelles je n'ai pas pensé ?

merci d'avance.

La réponse est normalement dans le cahier des charges :

Si tu as besoin d'insérer ou de supprimer des éléments au début ou en milieu de conteneur, alors la liste chainée est à priori le bon choix.

Sinon, si tout ce dont tu as besoin c'est un conteneur qui grandit ou réduit au gré des besoins, mais toujours par la fin, alors le tableau dynamique est préférable.

Citation:

---

Envoyé par arno.

je me demande ce qu'il est préférable d'utiliser entre une liste chainée et une liste "simple" de type array :

---

Un tableau n'est pas une liste.

Le choix se fait généralement en fonction de l'utilisation:
- liste chaînée:

* permet des insertions/effacements n'importe où
* un élément aloué ne bouge pas, donc on peut pointer dessus et conserver le pointeur qui n'est pas invalidé par les effacements/ajouts

- tableau

* permet un accès en temps constant

On peut faire un tableau qui est modifiable par les deux bouts en jouant sur les indices: s'il faut ajouter avant le début de la zone allouée, on ajoute à la fin de la zone allouée; l'adressage se fait toujours en temps constant mais est un peu plus compliqué.

Citation:

---

J'ai pensé à une liste simple, j'alloue 1, puis quand ça dépasse je réalloue (realloc) 2 puis 4, 8, etc.

---

On ne double généralement pas parce qu'alors la mémoire nécessaire est toujours supérieure à la mémoire libérée. Si ton tableau est la seule structure dynamique du programme, en doublant comme ça tu doubles à peu près la mémoire nécessaire.

Personnellement, j'utilise un facteur 1.5, mais si j'ai bonne mémoire, n'importe quel facteur inférieur au nombre d'or fonctionne.

Citation:

---

Sinon, j'ai pensé aussi à utiliser une liste chainée, mais par la suite, je ne pourrais plus accéder aux éléments en temps constant.

---

En fait, ça dépend de comment tu utilises ta liste.

Si tu ne fais que parcourir la liste, tu peux sauvegarder la dernière position lue, et donc atteindre la position suivante en temps constant, ce qui fait que chaque accès se sera fait en temps constant.

Maintenant, si tu es susceptible d'accèder à n'importe quel élément "aléatoirement", ça ne sera plus constant !

merci à tous pour vos réponses. C'est donc une liste dynamique dont j'ai besoin.

Citation:

---

On ne double généralement pas parce qu'alors la mémoire nécessaire est toujours supérieure à la mémoire libérée. Si ton tableau est la seule structure dynamique du programme, en doublant comme ça tu doubles à peu près la mémoire nécessaire.

---

Je n'ai pas bien compris cette histoire. Est-ce que quelqu'un aurait des pointeurs vers de la doc pour comprendre ça ?

Citation:

---

Envoyé par arno.

Je n'ai pas bien compris cette histoire. Est-ce que quelqu'un aurait des pointeurs vers de la doc pour comprendre ça ?

---

Quand tu alloues en doublant, tu alloues successivement 1, 2, 4, 8, 16... fois la taille initiale. A chaque fois, tu alloues plus que la somme de ce qui a été alloué précédemment. Donc l'espace libéré ne peut pas être réutilisé pour ça (il peut l'être pour autre chose). Comme en plus, juste après une allocation, on n'utilise que la moitié de la mémoire, on se retrouve donc dans une situation ou un quart de la mémoire consommée est réellement utilisée.

Si tu alloues en multipliant par 1.5, ça va être 1, 1.5, 2.25, 3.37, 5.06, 7.59 ... fois la taille initiale. Ici tu remarques que la somme des 4 premiers termes vaut 8.12 et donc cet espace peut être utilisé pour allouer les 7.59 (les 5.06 ne sont pas pris en compte dans la somme, on alloue d'abord la nouvelle zone avant de libérer l'ancienne!) et donc on peut réutiliser l'espace (s'il est bien contigu, s'il n'a pas été alloué pour autre chose, ...). Si j'ai bonne mémoire, la limite entre la récupération possible et l'absence de récupération est au nombre d'or.

ok, merci