Après j'ai du mal à voir l'intérêt d'implémenter une liste chaînée dans un tableau ...
Le seul intérêt, c'est de trouver un élément libre en O(1) et d'y accéder en O(1).
Tu ordonnes tes éléments ?
Non.
C'est pour parcourir l'ensemble de tes éléments en une seule passe comme avec une liste chaînée sans tester si une case est vide ?
Non plus. Je chaine juste les élément de façon a facilité l'usage de champ généraux : first_free_index, first_use_index et last_use_index.
J'obtiens un truc du genre :
struct
{
int first_free_index;
int first_use_index;
int last_use_index;
struct {
...
int prev_index;
int next_index;
}
};
Pour ajouter un élément, je prends le first free, et je le chaine avec le first use, je déchaine avec le next du first free.
Pour enlevé un élément, je rechaine ensemble le prev et le next, je le note en first free, je le rechaine avec l'ancien first free.
C'est pour éviter les allocations / désallocations mémoires ?
Oui. Contrainte produit :-(
[^] # Re: Vala ?
Posté par Anthony Jaguenaud . En réponse au journal Tomboy re-écrit en C++. Évalué à 2.
Le seul intérêt, c'est de trouver un élément libre en O(1) et d'y accéder en O(1).
Tu ordonnes tes éléments ?
Non.
C'est pour parcourir l'ensemble de tes éléments en une seule passe comme avec une liste chaînée sans tester si une case est vide ?
Non plus. Je chaine juste les élément de façon a facilité l'usage de champ généraux : first_free_index, first_use_index et last_use_index.
J'obtiens un truc du genre :
struct
{
int first_free_index;
int first_use_index;
int last_use_index;
struct {
...
int prev_index;
int next_index;
}
};
Pour ajouter un élément, je prends le first free, et je le chaine avec le first use, je déchaine avec le next du first free.
Pour enlevé un élément, je rechaine ensemble le prev et le next, je le note en first free, je le rechaine avec l'ancien first free.
C'est pour éviter les allocations / désallocations mémoires ?
Oui. Contrainte produit :-(