Implémentation de liste chaînée XOR - Suivi

Question

Cette question est une question complémentaire à l' implémentation de la liste chaînée XOR .

Je poste un nouveau code ici en tenant compte des suggestions de Toby Speight et Deduplicator. Veuillez indiquer comment l'efficacité du code peut être améliorée.

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

struct StNode {
    int value;
    uintptr_t both;
}; 
typedef struct StNode StHexNode;

StHexNode *add(StHexNode *lastNode, int value)
{
    StHexNode *newNode = malloc(sizeof(struct StNode));
    newNode->value = value;
    
    //latest node's [both]=pointer value pointing previous node:
    newNode->both = (uintptr_t)lastNode; 
    //calculating previous node [both]:
    lastNode->both = (uintptr_t)newNode ^ lastNode->both;
    return newNode;
}

StHexNode *get(StHexNode *headNode, unsigned int index)
{
    
    StHexNode *prevNode;
    StHexNode *currNode;
    uintptr_t tmp;
    
    //cur=1, prev=0
    currNode = (struct StNode *) ((headNode->both) ^ 0);
    prevNode = headNode;
    
    for(int i=2; i<=index; i++)
    {
        tmp = (uintptr_t)prevNode;
        prevNode = currNode;
        currNode = (struct StNode *) (currNode->both ^ tmp);
    }
    return currNode;
}

int free_list(StHexNode *headNode)
{
    StHexNode *prevNode;
    StHexNode *currNode;
    uintptr_t tmp;
    int ctr=0;
    
    //case: there is a only head node in the list
    if(headNode->both == 0) 
    {
        free(headNode);
        return ++ctr;
    }
    
    //prev=head, curr=second_node
    currNode = (struct StNode *) ((headNode->both) ^ 0);
    prevNode = headNode;
    
    while(currNode->both != (uintptr_t)prevNode)
    {
        tmp = (uintptr_t)prevNode;
        free(prevNode);
        ctr++;
        prevNode = currNode;
        currNode = (struct StNode *) (currNode->both ^ tmp);
    }
    //last node
    free(currNode);
    ctr++;
    
    return ctr;
}

int main(void) 
{
    unsigned int i;
    
    //I named first node as headNode, and last node as tailNode
    //create head node with both=0 since there is no previous node to it
    StHexNode *headNode = malloc(sizeof(struct StNode));
    StHexNode *tailNode = headNode; //last node pointer in the list
    
    //lets add 100 nodes after head
    //special handling of both value at head node
    for(headNode->both = 0, i=100; i<200; i++)
    {
        tailNode = add(tailNode, i);
        //printf("last node value:%d\n", tailNode->value);
    }


     //get index=50 node value
     StHexNode *iNode = get(headNode, 50);
     printf( "result: %d\n",  iNode->value);

     //free memory
     printf("we released %d list\n", free_list(headNode));
       
    }

Answer 1

N'utilisez pas un nom différent pour a structet sontypedef

Pourquoi est struct StNodetypedef'ed to StHexNode? Qu'est-ce Hexque ça veut dire ici, je ne vois rien d'hexadécimal ou d'hexagonal dans le reste du code? Vous pouvez utiliser exactement le même nom pour un structque pour son typedef, donc je l'utiliserais simplement:

typedef struct StNode StNode;

Vous pouvez également combiner le typedefavec la structdéfinition:

typedef struct StNode {
    ...
} StNode;

Utilisez typedefs systématiquement

Je vois que vous utilisez StHexNodedans certains endroits et struct StNodedans d'autres. Soyez cohérent et n'utilisez que la variante typedef'ed.

Évitez de répéter les noms de type si possible

Dans cette ligne:

StHexNode *newNode = malloc(sizeof(struct StNode));

Outre l'utilisation inconstante du typedef, vous répétez le type deux fois. Cela rend cette erreur sujette (si vous faites une erreur sur le côté droit, il se compilera sans erreurs mais ce sera probablement faux), et si vous devez un jour changer le type de la variable newNode, vous devrez le faire au moins deux places. Il vaut mieux éviter de répéter le nom du type, mais plutôt répéter le nom de la variable:

StNode *newNode = malloc(sizeof(*newNode));

Préférez utiliser des opérateurs d'assignation composés pour éviter les répétitions

Utilisez si possible des opérateurs d'affectation composés pour enregistrer une partie de la saisie et éviter d'éventuelles erreurs. Par exemple, au lieu de:

lastNode->both = (uintptr_t)newNode ^ lastNode->both;

Préférer:

lastNode->both ^= (uintptr_t)newNode;

Simplifier get()

Vous pouvez simplifier get()quelque peu la fonction . En particulier, lorsque vous parcourez les éléments d'une liste, essayez de commencer à l'index 0et évitez de faire des cas particuliers de début et de fin. Vous pouvez faire ceci ici comme ceci:

StNode *get(StNode *headNode, unsigned int index)
{   
    StNode *currNode = headNode;
    uintptr_t prev = 0;
    
    for (int i = 0; i < index; i++)
    {
        uintptr_t next = currNode->both ^ prev;
        prev = (uintptr_t)currNode;
        currNode = (StNode *)(next);
    }

    return currNode;
}

Notez que vous pourriez même éviter la déclaration de currNodesi vous changez le nom de headNodeen currNode, mais je le garderais personnellement tel quel ci-dessus, car cela rend le rôle du paramètre et de la variable locale plus clair.

Simplifier free_list()

Il en va de même free_list(): vous ne devriez pas avoir besoin de faire d'une liste d'un élément un cas particulier. Aussi, pourquoi free_list()calculer le nombre d'éléments d'une liste qui auront été supprimés au moment de son retour?

void free_list(StNode *headNode)
{
    StNode *currNode = headNode;
    uintptr_t prev = 0;
    
    while (currNode)
    {
        uintptr_t next = currNode->both ^ prev;
        prev = (uintptr_t)currNode;
        free(currNode);
        currNode = (StNode *)(next);
    }
}

Utilisez un schéma de dénomination unique et cohérent

Si vous souhaitez utiliser votre liste chaînée XOR dans un programme réel, considérez que les noms aiment StNodeet get()sont très génériques et seront probablement en conflit avec d'autres parties d'un projet plus vaste. Peut-être avez-vous également besoin d'une implémentation d'arbre binaire par exemple, et comment allez-vous nommer sa fonction pour récupérer un élément à un index donné? Pour résoudre ce problème en C, créez un préfixe unique que vous pouvez utiliser pour tous les noms de structure et de fonction. Par exemple, préfixez tout avec xllist_:

typedef struct xllist_node {
    ...
} xllist_node;

xllist_node *xllist_add(xllist_node *lastNode, int value);
xllist_node *xllist_get(xllist_node *headNode, usigned int index);
void xllist_free(xllist_node *headNode);

Bien sûr, vous pouvez discuter de ce que le préfixe devrait être exactement. Je trouve quelque chose comme xor_linked_listou XorLinkedListun peu trop verbeux, donc xllistc'est un compromis: il a toujours listclairement dans le nom, et si vous ne savez pas ce que xlvous pouvez le rechercher, et une fois que vous avez vu ce que cela signifie, il est facile de rappelez-vous que cela xlsignifie XOR linkedj'espère.

Créer un structreprésentant la liste entière

Vous avez un structpour un nœud, mais pas un pour toute la liste. Cela signifie que l'appelant de vos fonctions doit allouer manuellement le premier élément de la liste, et il doit garder une trace du nœud de tête et de queue. C'est beaucoup mieux si vous créez un structreprésentant la liste:

typedef struct xllist {
    xllist_node *head;
    xllist_node *tail;
} xllist;

Et puis passez un pointeur vers ceci structà des fonctions comme xllist_get(), xllist_add()et xllist_free(), comme ceci:

xllist_node *xllist_add(xllist *list, int value) {
    xllist_node *newNode = malloc(sizeof(*newNode));
    newNode->both = (uintptr_t)xllist->tail;
    newNode->value = value;

    if (xllist->tail) {
        // Append it to the existing tail node
        xllist->tail->both ^= (uintptr_t)newNode;
        xllist->tail = newNode;
    } else {
        // The list was empty
        xllist->head = newNode;
        xllist->tail = newNode;
    }

    return newNode;
}

Et vous l'utilisez comme ça dans main():

xllist myList = {NULL, NULL}; // declare an empty list

for (int i = 100; i < 200; i++)
{
    xllist_add(&myList, i);
}

Answer 2

Version mise à jour après application des conseils de G. Sliepen.

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

typedef struct StNode {
    int value;
    uintptr_t both;
} StNode; 

//keep track of linked list head and tail
typedef struct xllist {
    //I named first node as headNode, and last node as tailNode
    StNode *head;
    StNode *tail;
} xllist;

StNode *xllist_add(xllist *list, int value)
{
    StNode *newNode = malloc(sizeof *newNode);  
    newNode->value = value;
    if(list->head == NULL)
    {
        //very first node
        list->head = newNode;
        list->tail = newNode;
        list->head->both = 0;
        return newNode;
    }
    
    list->tail->both ^= (uintptr_t)newNode;
    newNode->both = (uintptr_t)list->tail;
    list->tail = newNode;
    
    return newNode;
}

StNode *xllist_get(xllist *list, unsigned int index)
{   
    StNode *currNode = list->head;
    uintptr_t prev=0;
    
    for(int i=0; i<index; i++)
    {
        uintptr_t next = currNode->both ^ prev;
        prev = (uintptr_t)currNode;
        currNode = (StNode *)next;
    }
    return currNode;
}

void xllist_free(xllist *list)
{
    StNode *currNode=list->head;
    uintptr_t prev=0, next;
    
    while(currNode)
    {
        next = prev ^ (uintptr_t)currNode->both;
        prev = (uintptr_t)currNode;
        free(currNode);
        currNode = (StNode *)next;
        
    }
    
}

int main(void) 
{
    unsigned int i; 
    xllist myList = {NULL, NULL};
    
    //lets xllist_add 100 nodes after head
    //special handling of both value at head node
    for(i=100; i<200; i++)
    {
        xllist_add(&myList, i);
    }
    
    //xllist_get index=50 node value
    StNode *iNode = xllist_get(&myList, 50);
    printf( "result: %d\n",  iNode->value);
    
    //free memory
    xllist_free(&myList);
   
}