Cette question mentionne que c'est possible pour faire la mise en œuvre d'une liste liée dans un tableau.
tandis que je peux imaginer comment faire cela avec plusieurs tableaux, comment peut-on faire avec un seul tableau?
Edit: Peut-on faire fonctionner efficacement que des éléments devront être supprimés et insérés de la liste - nécessitant probablement une identification d'éléments libres dans le tableau?
5 Réponses :
Vous pouvez (par exemple) avoir une liste liée des entiers en mettant votre premier élément de données dans l'élément de la matrice et l'index de l'élément suivant dans le deuxième élément. Cela vous limiterait à stocker des types compatibles avec / convertibles à un index.
Oui, le problème de type semble être une restriction. Aussi - Comment trouver efficacement l'espace libre dans la matrice lorsque des éléments sont supprimés?
Stocker les objets / les structures (je ne sais pas si Java a des structures) contenant la valeur et l'index comme deux champs. Et pour stocker un espace libre, conservez simplement deux listes liées dans le même tableau, l'un de tous les éléments libres et un avec tous les éléments utilisés.
Vous voudrez généralement suivre l'espace libre avec une liste liée de nœuds libres. Donc, vous avez (au moins) un "pointeur" (index) au début des éléments utilisés et un autre aux éléments libres. Lorsque vous libérez un élément, vous l'ajoutez à la liste gratuite. Lorsque vous avez besoin d'un élément, vous avez mal raccordé de la liste gratuite.
@ Lassev.karlsen: Oui, si vous avez des structures - mais presque inévitablement, si vous avez des structures, vous avez de meilleures alternatives à cela en général. Un usage réel serait avec quelque chose comme Fortran 77 qui n'avait ni des structures ni des pointeurs.
@Jerry Coffin - Donc, deux tableaux sont nécessaires (un avec des valeurs, une pour suivre l'espace libre) pour une performance raisonnable?
@Joel: Non, pas du tout. Vous avez un seul tableau et chaque paire d'éléments de tableau est dans la liste Free ou la liste utilisée. Vous commencez avec tous les éléments de la liste gratuite, puis dans la mesure où vous ajoutez des données, des éléments sont déplacés vers la liste utilisée. Pour supprimer un élément de données, vous le déplacez dans la liste GRATUITE (et corrigez le "pointeur" autour de celui-ci dans la liste utilisée, comme avec une liste liée normale).
en C ++ j'ai rapidement écrit cela et ça marche. Chaque index de la matrice contient une liste doublement liée.
$ g++ ll-in-array.cpp && ./a.out 100 90 80 70 60 50 40 30 20 10 100 90 80 70 60 50 40 30 20 10 100 90 80 70 60 50 40 30 20 10 100 90 80 70 60 50 40 30 20 10 100 90 80 70 60 50 40 30 20 10 100 90 80 70 60 50 40 30 20 10 100 90 80 70 60 50 40 30 20 10 100 90 80 70 60 50 40 30 20 10 100 90 80 70 60 50 40 30 20 10 100 90 80 70 60 50 40 30 20 10
Mon C ++ n'est pas génial, mais en supposant que vous ayez eu un style Java "int [] tableau" Comment cela fonctionne-t-il: "Chaque index dans la matrice contient une liste doublement liée". ?
Cette réponse n'a pas implémenté une liste liée à l'aide d'une matrice, il vient de stocker des listes liées ordinaires dans le tableau.
@ Lassev.karlsen Je dirais que la définition de "mise en œuvre" est une ligne grise. Je ne l'ai pas impliqué à partir de la terre, ma mise en œuvre utilise plutôt une liste liée pré-conçue. Mais je vois maintenant que tu as raison et que l'Op cherchait quelque chose de la terre. @Joel My Java n'est pas génial, mais je pense que vous pouvez également créer des tableaux comme int gray [] tout comme comment j'ai fait dans mon exemple. Dans mon exemple, j'ai un éventail de listes liées de type INT (c'est-à-dire des listes liées dans un tableau).
@Dennis L'OP demande la mise en œuvre d'une liste liée à l'aide de la matrice en tant que structure de données sous-jacente, c'est-à-dire stocker les nœuds de la matrice. Chaque nœud a (réseau) index au lieu des pointeurs. Veuillez envisager de modifier votre réponse ou de la supprimer complètement car il ne fournit aucune information précieuse.
S'il s'agit d'un tableau d'objets, chaque objet stockerait une valeur et un pointeur sur l'objet suivant.
[0] -> {"a",1}
[1] -> {"b",2}
[2] -> {"c",4}
[3] -> {"1",5}
[4] -> {"d",7}
[5] -> {"2",6}
[6] -> {"3",8}
[7] -> {"e",-1}
[8] -> {"4",-1}
Si je mettez en place une liste liée en tant que tableau, cela conduira-t-il à une meilleure utilisation des lignes de cache?
Oui, il sera. C'est peut-être l'un des plus grands avantages.
Vous pouvez utiliser un allocateur de bloc de mémoire de taille fixe où chaque bloc a un point de pointeur suivant à l'élément suivant de la liste liée.
Une bonne et simple implémentation provient du système d'exploitation Contiki (licence BSD), Voir la mise en œuvre de Membr et liste . p>
Vous les utilisez comme ceci: p>
struct connection {
struct connection *next;
/* ... */
};
/* This allocates a fixed size array of 16 'struct connection' */
MEMB(connection_mem, struct connection, 16);
/* This is just a void ** keeping track of list elements in a linked list */
LIST(connection_list);
void main()
{
/* Initialize the memory block */
memb_init(&connection_mem);
/* Allocate a new chunk */
struct connection *c = memb_alloc(&connection_mem);
if(c != NULL) {
/* Add to list */
list_add(connection_list, c);
}
for(c = list_head(connection_list); c != NULL; c = c->next) {
/* ... */
}
}
Comment implémentez-vous une liste liée dans un tableau? p>
Voici une approche possible (en utilisant c ++) sup>: votre nœud serait composé d'index des éléments suivants et antérieurs
dans la liste forte>: p> void push_back(Link** head, Link* new_link) { // chech pointer validity int index = get_available_index(); // probably using: placement new(), to construct a node in that location // new(head + index) new_link;? or just head[index] = new_link; if (last != -1) // list not empty { head[last]->next = index; head[index]->prev = (last - head[0]); // gives you the index of the last node } else { first = index; head[index]->prev = -1; } last = index; head[index]->next = -1; }
Qu'en est-il de redéfinir le nœud dans une liste liée en remplaçant la référence au nœud suivant avec l'index du nœud suivant?