modifier l'ordre des éléments dans la liste chaînée

Question

J'essaie d'utiliser la liste chaînée simple:

struct index 
{ 
    struct index* next_element; 
    int data; 
    struct index* previous_element; 
} 

Quelle est la meilleure façon de changer l'ordre des éléments en termes de performance? Par exemple, j'ai 1 2 3 4 5 6 7 8 et j'ai besoin de 1 4 2 3 5 6 7 8.

Answer 1

C'est difficile à dire en général. Il semble que vous voulez déplacer l'élément 4 après l'élément 1. Avez-vous le index* pour les deux? Ou savez-vous seulement que le quatrième élément doit se déplacer de deux endroits? Cela affecte évidemment la quantité de listwalking que vous avez à faire.

En général, pour une efficacité maximale, vous voulez une fonction

void list_remove_unsafe_(index* i) { 
    // These two have to change (minimum needed) 
    i->previous_element->next_element = i->next_element; 
    i->next_element->previous_element-> = i->previous_element; 
    // We leave i itself unchanged (dangling) 
} 

et un suivi

void list_insert_unsafe_(index* after, index* i) { 
    // These four have to change (minimum needed) 
    index* before = after->next_element; 
    i->previous_element = after; 
    i->next_element = before; 
    before->previous_element = i; 
    after->next_element = i; 
} 

Ces opérations ne sont pas sécuritaires parce qu'ils quittent temporairement la liste dans un état cassé et faire beaucoup d'hypothèses (par exemple, pas de vérification pour le début/fin des listes). Ceux-ci ont besoin d'une manipulation spéciale. Pour l'opération de base, ces 6 écritures sont le strict minimum.