Dans une interview à TED 2016 (14:10), Linus Torvalds parle d'un bon style de codage. À titre d'exemple, il donne deux options pour supprimer des éléments de listes liées individuellement (voir ci-dessous). La première option a un cas particulier, tandis que l'autre n'en a pas. Linus préfère ce dernier.



Son commentaire:

[...] Inutile de se demander pourquoi il n'y a pas de déclaration if ici. Il est important de regarder le problème sous un angle différent et de le réécrire afin que le cas spécial disparaisse et devienne un cas normal, et c'est un bon code . - L. Torvalds

Linus montre un pseudocode de style C assez simple à titre d'exemple. Mais ne fournit pas d'explication conceptuelle. Par conséquent, il n'est pas immédiatement clair comment fonctionne un pointeur indirect.



Regardons de plus près cette solution et ses avantages. En prime, non seulement la suppression est représentée, mais également l'insertion d'un élément via un adressage indirect.

Le code

La structure de données de base pour une liste d'entiers liés à un seul lien est illustrée à la Fig. 1.





Fig. 1. Une seule liste d'entiers liés



Les nombres sont des valeurs entières sélectionnées aléatoirement, et les flèches correspondent à des pointeurs: head



 - c'est un pointeur de type IntListItem*



, tous les blocs sont des instances d'une structure IntListItem



, chacun avec sa propre variable ( next



dans le code) du type IntListItem*



, qui pointe vers l'élément suivant.



Implémentation de la structure de données en C:

struct IntListItem {
    int value;
    struct IntListItem* next;
};
typedef struct IntListItem IntListItem;

struct IntList {
    IntListItem* head;
};
typedef struct IntList IntList;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Aussi l'API (minimale):

/* The textbook version */
void remove_cs101(IntList* l, IntListItem* target);
/* A more elegant solution */
void remove_elegant(IntList* l, IntListItem* target);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Regardons maintenant les implémentations remove_cs101()



et remove_elegant()



. Le code des exemples ne contredit pas le pseudocode de l'exemple de Linus, mais il se compile et s'exécute.

Version de base

Figure: 2. Modèle conceptuel de la structure des données de liste dans l'algorithme de base

void remove_cs101(IntList *l, IntListItem *target)
{
    IntListItem *cur = l->head, *prev = NULL;
    while (cur != target) {
        prev = cur;
        cur = cur->next;
    }
    if (prev) {
        prev->next = cur->next;
    } else {
        l->head = cur->next;
    }
}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Dans l'approche standard, deux pointeurs de parcours cur



et prev



, qui marquent respectivement la position de parcours actuelle et précédente dans la liste. cur



commence en tête de liste head



et avance jusqu'à ce que la cible soit trouvée. À son tour, il prev



commence par NULL



et est ensuite mis à jour à la valeur précédente cur



chaque fois qu'il avance. Lorsque la cible est trouvée, l'algorithme vérifie si elle n'est pas prev



nulle. Si tel est le cas, il cur



pointe vers le premier élément de la liste, auquel cas la suppression signifie faire avancer la tête de la liste.

Une solution plus élégante

La version la plus élégante a moins de code et ne nécessite pas de branche séparée pour supprimer le premier élément de la liste.

void remove_elegant(IntList *l, IntListItem *target)
{
    IntListItem **p = &l->head;
    while ((*p) != target) {
        p = &(*p)->next;
    }
    *p = target->next;
}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Le code utilise un pointeur indirect p



qui contient l'adresse du pointeur vers l'élément de liste, en commençant à l'adresse head



. À chaque itération, ce pointeur est développé pour inclure l'adresse du pointeur vers l'élément suivant dans la liste, c'est-à-dire l'adresse de l'élément next



dans l' élément actuel IntListItem



. Lorsque le pointeur vers l'élément de liste (*p)



est égal target



, nous quittons la boucle de recherche et supprimons l'élément de la liste.

Comment ça fonctionne?

Un pointeur indirect présente p



deux avantages conceptuels:

1. Vous permet d'interpréter une liste chaînée de manière à ce que le pointeur head
   
   
   
   fasse partie intégrante de la structure de données. Cela élimine le besoin d'un cas spécial pour supprimer le premier élément.
   
   
2. Il vous permet également d'évaluer l'état de la boucle while
   
   
   
   sans avoir à relâcher le pointeur pointant vers target
   
   
   
   . Cela vous permet de changer le pointeur target
   
   
   
   et de vous déplacer avec un seul itérateur, contrairement à prev
   
   
   
   et cur
   
   
   
   .

Jetons un coup d'œil à chaque élément à son tour.

Intégration du pointeur de tête

Le modèle standard interprète une liste chaînée comme une séquence d'instances IntListItem



. Le début de la séquence peut être obtenu à l'aide d'un pointeur head



. Cela conduit au modèle conceptuel illustré à la Fig. 2. Le pointeur est head



simplement traité comme une poignée pour accéder au début de la liste. prev



et cur



sont des pointeurs de type IntListItem*



et pointent toujours vers ou NULL



.



L'implémentation élégante utilise un schéma d'adressage indirect, qui donne une vue différente de la structure des données:





Fig. 3. Modèle conceptuel de la structure de données de liste dans une solution plus élégante Représente



ici p



le typeIntListItem**



et contient l'adresse du pointeur vers l'élément de liste actuel. Lorsque le pointeur avance, son adresse passe à l'élément suivant.



Dans le code, cela ressemble à p = &(*p)->next



:

1. (*p)
   
   
   
   : déréférencer l'adresse du pointeur vers l'élément de liste actuel.
   
   
2. ->next
   
   
   
   : déréférencer à nouveau ce pointeur et sélectionner le champ avec l'adresse de l'élément suivant.
   
   
3. &
   
   
   
   : prenez l'adresse de ce champ (c'est-à-dire, obtenez un pointeur vers celui-ci).

Cela correspond à l'interprétation d'une structure de données, où une liste est une séquence de pointeurs vers des éléments IntListItem



(Figure 3).

La touche finale

Un avantage supplémentaire de cette interprétation particulière est qu'elle permet au pointeur next



d' être édité pour le prédécesseur de l'élément courant tout au long du parcours .



Si p



contient l'adresse d'un pointeur vers un élément de la liste, la comparaison dans la boucle de recherche devient:

while ((*p) != target) {
    ...
}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Le cycle de recherche se terminera s'il (*p)



est égal target



, et dès que cela se produit, nous pouvons encore changer (*p)



, puisque nous tenons son adresse p



. Ainsi, même si la boucle est itérée jusqu'à la fin, un descripteur (adresse de champ next



ou pointeur head



) est stocké qui peut être utilisé pour changer directement le pointeur vers un élément.



C'est pourquoi nous pouvons modifier l'entrée du pointeur d'élément pour pointer vers un emplacement différent, en utilisant *p = target->next



, et par conséquent, nous n'avons pas besoin de contourner les pointeurs prev



et cur



de supprimer l'élément.

Nouvelle application

Il s'avère que la même idée peut être appliquée à une implémentation extrêmement laconique d'une autre fonction dans des listes chaînées:, insert_before()



c'est-à-dire insérer cet élément avant un autre.

Insertion avant l'élément existant

Tout d'abord, ajoutons la déclaration suivante à list.h



:

void insert_before(IntList *l, IntListItem *before, IntListItem *item);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

La fonction prendra un pointeur vers la liste l, un pointeur avant un élément de cette liste et un pointeur vers un nouvel élément de liste que la fonction insérera avant lui.

Refactoring rapide

Avant de continuer, faisons de la boucle de recherche une fonction distincte:

static inline IntListItem **find_indirect(IntList *l, IntListItem *target)
{
    IntListItem **p = &l->head;
    while ((*p) && (*p) != target) {
        p = &(*p)->next;
    }
    return p;
}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

et utilisez-le dans remove_elegant()



:

void remove_elegant(IntList *l, IntListItem *target)
{
    IntListItem **p = find_indirect(l, target);
    *p = target->next;
}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Implémentation Insert_before ()

Son utilisation find_indirect()



est facile à mettre en œuvre insert_before()



:

void insert_before(IntList *l, IntListItem *before, IntListItem *item)
{
    IntListItem **p = find_indirect(l, before);
    *p = item;
    item->next = before;
}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

La sémantique solide pour les cas de bord est particulièrement agréable: si elle before



pointe vers la tête de la liste, un nouvel élément sera inséré au début, s'il before



est nul ou invalide (c'est-à-dire qu'il n'existe pas dans l



), un nouvel élément sera ajouté à la fin.

Conclusion

La condition préalable à une solution plus élégante pour supprimer des éléments est un changement simple: un pointeur indirect IntListItem**



pour itérer sur des pointeurs vers des éléments de liste. Tout le reste découle de là: il n'y a pas besoin de cas particuliers ou de branches. Un itérateur suffit pour trouver et supprimer l'élément cible. Et il s'avère que la même approche fournit une solution élégante pour l'insertion en général et l'insertion devant un élément existant en particulier.



Donc, pour revenir à la remarque initiale de Linus, est-ce un indicateur de bon goût? Dur à dire. Mais il existe clairement une solution créative et très élégante à un problème bien connu.