Les listes liées devraient-elles toujours avoir un pointeur de queue?

Ma compréhension...

Avantages:

• L'insertion à la fin est O (1) au lieu de O (N).
• Si la liste est une liste à double liaison, la suppression de la fin est également O (1) au lieu de O (N).

Désavantage:

• Prend une quantité insignifiante de mémoire supplémentaire: 4 à 8 octets .
• Le réalisateur doit garder une trace de la queue.

En regardant ces avantages et inconvénients, je ne vois pas pourquoi une liste liée éviterait jamais d'utiliser un pointeur de queue. Y a-t-il quelque chose qui me manque?

Vous avez raison, un pointeur de queue ne fait jamais de mal et ne peut que vous aider. Cependant, il y a une situation où l'on n'a pas du tout besoin d'un pointeur de queue.

Si l'on utilise une liste chaînée pour implémenter une pile, il n'est pas nécessaire d'avoir un pointeur de queue car on peut garantir que tous les accès, insertions et suppressions se produisent en tête. Cela étant dit, on pourrait utiliser une liste à double liaison avec un pointeur de queue de toute façon parce que l'implémentation standard dans une bibliothèque ou une plate-forme et la mémoire est bon marché, mais on n'en a pas besoin .

Les listes liées sont très souvent persistantes et immuables. En fait, dans les langages de programmation fonctionnels, cette utilisation est omniprésente. Les pointeurs de queue cassent ces deux propriétés. Cependant, si vous ne vous souciez pas de l'immuabilité ou de la persistance, il y a très peu d'inconvénients à inclure un pointeur de queue.

J'utilise rarement un pointeur de queue pour les listes liées et j'ai tendance à utiliser des listes liées individuellement plus souvent lorsqu'un modèle d'insertion et de suppression push / pop de type pile (ou simplement une suppression linéaire du milieu) suffit. C'est parce que dans mes cas d'utilisation courants, le pointeur de queue est en fait cher, tout comme la transformation de la liste à liaison unique en une liste à double liaison est coûteuse.

Souvent, mon utilisation courante de cas pour une liste liée individuellement peut stocker des centaines de milliers de listes liées qui ne contiennent que quelques nœuds de liste chacun. Je n'utilise généralement pas de pointeurs pour les listes chaînées. J'utilise plutôt des indices dans un tableau car les indices peuvent être 32 bits, par exemple, en prenant la moitié de l'espace d'un pointeur 64 bits. En règle générale, je n'alloue pas de nœuds de liste un à la fois et, à la place, j'utilise simplement un grand tableau pour stocker tous les nœuds, puis j'utilise des index 32 bits pour relier les nœuds ensemble.

Par exemple, imaginez un jeu vidéo utilisant une grille 400x400 pour partitionner un million de particules qui se déplacent et rebondissent les unes sur les autres pour accélérer la détection des collisions. Dans ce cas, un moyen assez efficace de stockage consiste à stocker 160.000 listes à liaison unique, ce qui se traduit par 160.000 entiers 32 bits dans mon cas (~ 640 kilo-octets) et un surdébit entier 32 bits par particule. Maintenant que les particules se déplacent sur l'écran, tout ce que nous avons à faire est de mettre à jour quelques entiers 32 bits pour déplacer une particule d'une cellule à l'autre, comme ceci:

... avec l' nextindex ("pointeur") d'un nœud de particule servant d'index à la prochaine particule dans la cellule ou à la prochaine particule libre à récupérer si la particule est morte (essentiellement une implémentation d'allocateur de liste libre utilisant des indices):

La suppression du temps linéaire d'une cellule n'est pas en fait un surcoût puisque nous traitons la logique des particules en itérant à travers les particules dans une cellule, donc une liste doublement liée ajouterait simplement un surcoût d'un type qui n'est pas bénéfique pour tout dans mon cas, tout comme une queue ne me profiterait pas non plus.

Un pointeur de queue doublerait l'utilisation de la mémoire de la grille et augmenterait le nombre de ratés du cache. Il nécessite également une insertion pour exiger qu'une branche vérifie si la liste est vide au lieu d'être sans branche. En faire une liste doublement couplée doublerait la surcharge de la liste de chaque particule. 90% du temps j'utilise des listes chaînées, c'est pour des cas comme ceux-ci, et donc un pointeur de queue serait en fait assez cher à stocker.

Donc, 4 à 8 octets ne sont en fait pas triviaux dans la plupart des contextes dans lesquels j'utilise des listes liées en premier lieu. Je voulais juste y intégrer car si vous utilisez une structure de données pour stocker une cargaison d'éléments, alors 4 à 8 octets ne sont pas toujours si négligeables. J'utilise en fait des listes liées pour réduire le nombre d'allocations de mémoire et la quantité de mémoire requise par opposition, par exemple, au stockage de 160 000 tableaux dynamiques qui se développent pour la grille, ce qui aurait une utilisation explosive de la mémoire (généralement un pointeur plus deux entiers au moins par cellule de grille) avec des allocations de tas par cellule de grille par opposition à un seul entier et zéro allocations de tas par cellule).

Je trouve souvent que de nombreuses personnes recherchent des listes chaînées pour leur complexité en temps constant associée à la suppression avant / intermédiaire et à l'insertion avant / intermédiaire lorsque les LL sont souvent un mauvais choix dans ces cas en raison de leur manque général de contiguïté. Là où les LL sont beaux pour moi du point de vue des performances, c'est la possibilité de simplement déplacer un élément d'une liste à une autre en manipulant simplement quelques pointeurs et en étant en mesure d'obtenir une structure de données de taille variable sans allocateur de mémoire de taille variable (puisque chaque nœud a une taille uniforme, nous pouvons utiliser des listes gratuites, par exemple). Si chaque nœud de liste est alloué individuellement par rapport à un allocateur à usage général, c'est généralement lorsque les listes liées se comportent bien moins bien que les alternatives, et cela '

Je suggérerais plutôt que pour la plupart des cas où les listes chaînées servent d'optimisation très efficace par rapport aux alternatives simples, les formes les plus utiles sont généralement liées individuellement, n'ont besoin que d'un pointeur de tête et ne nécessitent pas d'allocation de mémoire à usage général par nœud et peut à la place simplement regrouper la mémoire déjà allouée par nœud (à partir d'un grand tableau déjà alloué à l'avance, par exemple). De plus, chaque SLL stocke généralement un très petit nombre d'éléments dans ces cas, comme des arêtes connectées à un nœud de graphe (de nombreuses petites listes liées par opposition à une liste liée massive).

Il convient également de garder à l'esprit que nous avons une cargaison de DRAM ces jours-ci, mais c'est le deuxième type de mémoire le plus lent disponible. Nous sommes toujours à quelque chose comme 64 Ko par cœur en ce qui concerne le cache L1 avec des lignes de cache de 64 octets. En conséquence, ces petites économies d'octets peuvent vraiment avoir de l'importance dans un domaine critique pour les performances comme la simulation de particules ci-dessus lorsqu'elle est multipliée des millions de fois si cela signifie la différence entre stocker deux fois plus de nœuds dans une ligne de cache ou non, par exemple