Contrôle de cohérence pour une liste liée

Question

Tout d'abord, qu'est-ce qu'un invariant de liste dans la liste-liée?

Comment vérifier si une liste liée est cohérente en utilisant un algorithme qui s'exécute en temps O (n) et O (1) en mémoire supplémentaire?

Answer 1

Dans une liste à double liaison, l'invariant est que chaque nœud est le prédécesseur de son successeur.

Considérons une implémentation dans laquelle chaque noeud gère deux pointeurs, un pointeur succ pointant vers son noeud successeur et un pointeur pred pointant vers son noeud précédent.

Dans une liste correcte, les pointeurs sont pondus comme ceci:

Notez que lorsque vous suivez le pointeur succ d'un nœud à l'autre, vous pouvez toujours utiliser le pointeur pred aller Retour à votre noeud d'origine. Chaque opération manipulant la liste doit s'assurer que cette condition reste intacte.

Une liste qui ne respecte pas cet invariant pourrait ressembler à ceci:

Cela pourrait par exemple se produire si une opération d'insertion correctement mis en œuvre a essayé d'insérer un nœud n2 au milieu de la liste, mais il a oublié pour mettre à jour le pointeur pred de .

Vérification de cet invariant est simple: parcourir la liste en traversant le long des succ pointeurs (O(n)) et maintenir le dernier noeud visité dans un tampon de mémoire (O(1)). Ensuite, vérifiez à chaque nœud si le pointeur pred du nœud actuel pointe vers le dernier nœud visité.

Si vous connaissez également le noeud final de la liste, vérifiez si le dernier noeud auquel vous arrivez (celui qui n'a pas de successeur) est le noeud final attendu.

Notez qu'avec une seule liste chaînée, aucun tel invariant n'existe.