Implantation élégante de la liste circulaire à un seul lien en C?

Question

Traversant les structures de données classiques et s'être arrêté sur des listes chaînées. Il suffit d'implémenter une liste circulaire unique, mais j'ai l'impression écrasante que cette liste pourrait s'exprimer de manière plus élégante, en particulier remove_node. En gardant à l'esprit l'efficacité et la lisibilité du code, quelqu'un pourrait-il présenter une solution plus concise et efficace pour une liste circulaire à lien unique?

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


struct node{ 
    struct node* next; 
    int value; 
}; 


struct list{ 
    struct node* head; 
}; 


struct node* init_node(int value){ 
    struct node* pnode; 
    if (!(pnode = (struct node*)malloc(sizeof(struct node)))){ 
     return NULL; 
    } 
    else{ 
     pnode->value = value; 
    } 
    return pnode; 
} 

struct list* init_list(){ 
    struct list* plist; 
    if (!(plist = (struct list*)malloc(sizeof(struct list)))){ 
     return NULL;   
    } 
    plist->head = NULL; 
    return plist; 
} 


void remove_node(struct list*a plist, int value){ 

    struct node* current, *temp; 
    current = plist->head; 
    if (!(current)) return; 
    if (current->value == value){ 
     if (current==current->next){ 
      plist->head = NULL; 
      free(current); 
     } 
     else { 
      temp = current; 
      do {  
       current = current->next;  
      } while (current->next != plist->head); 

      current->next = plist->head->next; 
      plist->head = current->next; 
      free(temp); 
     } 
    } 
    else { 
     do { 
      if (current->next->value == value){ 
       temp = current->next; 
       current->next = current->next->next; 
       free(temp); 
      } 
      current = current->next; 
     } while (current != plist->head); 
    } 
} 

void print_node(struct node* pnode){ 
    printf("%d %p %p\n", pnode->value, pnode, pnode->next); 
} 
void print_list(struct list* plist){ 

    struct node * current = plist->head; 

    if (!(current)) return; 
    if (current == plist->head->next){ 
     print_node(current); 
    } 
    else{ 
     do { 
      print_node(current); 
      current = current->next; 

     } while (current != plist->head); 
    } 

} 

void add_node(struct node* pnode,struct list* plist){ 

    struct node* current; 
    struct node* temp; 
    if (plist->head == NULL){ 
     plist->head = pnode; 
     plist->head->next = pnode; 
    } 
    else { 
     current = plist->head; 
     if (current == plist->head->next){ 
      plist->head->next = pnode; 
      pnode->next = plist->head;  
     } 
     else { 
      while(current->next!=plist->head) 
       current = current->next; 

      current->next = pnode; 
      pnode->next = plist->head; 
     } 

    } 
} 

Answer 1

Jetez un oeil à la liste chaînée circulaire dans la source du noyau Linux: http://lxr.linux.no/linux+v2.6.36/include/linux/list.h

Sa beauté vient du fait que vous ne disposez pas d'un struct spécial pour vos données pour tenir dans la liste, vous devez seulement inclure le struct list_head * dans la structure que vous voulez avoir comme liste. Les macros permettant d'accéder aux éléments de la liste géreront le calcul de décalage pour obtenir le pointeur struct list_head vers vos données.

Une explication plus détaillée de la liste liée utilisée dans le noyau peut être trouvée sur kernelnewbies.org/FAQ/LinkedLists (Désolé, je n'ai pas assez de karma pour publier deux hyperliens). Editer: Eh bien, la liste est une liste à double lien et non une seule, comme vous l'avez fait, mais vous pouvez adopter le concept et créer votre propre liste à liens uniques.

Answer 2

Quelques commentaires:

• Je pense que la fonction de suppression ne se règle pas correctement les pointeurs de liste circulaire lorsque vous supprimez le nœud de tête et la liste est supérieure à 3 éléments. Puisque la liste est circulaire, vous devez pointer le dernier nœud de la liste vers la nouvelle tête.
• Vous pourriez raccourcir légèrement la fonction de suppression en créant une fonction "find_node". Puisque la liste est circulaire, cependant, il y aura toujours le cas de la suppression du nœud principal qui sera plus complexe que dans une liste non-circulaire.
• Le code "beauté" est dans l'oeil du spectateur. Comme le code va le vôtre est facile à lire et à comprendre ce qui bat beaucoup de code dans la nature.

Answer 3

Le traitement des listes (en particulier des listes circulaires) devient plus facile lorsque vous traitez la tête de liste comme un élément de la liste (une "sentinelle"). Beaucoup de cas spéciaux disparaissent. Vous pouvez utiliser un noeud factice pour la sentinelle, mais si le pointeur suivant est premier dans la structure, vous n'avez même pas besoin de faire cela. L'autre grosse astuce consiste à garder un pointeur sur le prochain pointeur du nœud précédent (donc vous pourrez le modifier plus tard) chaque fois que vous modifiez la liste. Tout mettre ensemble, vous obtenez ceci:

struct node* get_sentinel(struct list* plist) 
{ 
    // use &plist->head itself as sentinel! 
    // (works because struct node starts with the next pointer) 
    return (struct node*) &plist->head; 
} 

struct list* init_list(){ 
    struct list* plist; 
    if (!(plist = (struct list*)malloc(sizeof(struct list)))){ 
     return NULL;   
    } 
    plist->head = get_sentinel(plist); 
    return plist; 
} 

void add_node_at_front(struct node* pnode,struct list* plist){ 
    pnode->next = plist->head; 
    plist->head = pnode; 
} 

void add_node_at_back(struct node* pnode,struct list* plist){ 
    struct node *current, *sentinel = get_sentinel(plist); 

    // search for last element 
    current = plist->head; 
    while (current->next != sentinel) 
     current = current->next; 

    // insert node 
    pnode->next = sentinel; 
    current->next = pnode; 
} 

void remove_node(struct list* plist, int value){ 
    struct node **prevnext, *sentinel = get_sentinel(plist); 
    prevnext = &plist->head; // ptr to next pointer of previous node 
    while (*prevnext != sentinel) { 
     struct node *current = *prevnext; 
     if (current->value == value) { 
      *prevnext = current->next; // remove current from list 
      free(current); // and free it 
      break; // we're done! 
     } 
     prevnext = &current->next; 
    } 
} 

void print_list(struct list* plist){ 
    struct node *current, *sentinel = get_sentinel(plist); 
    for (current = plist->head; current != sentinel; current = current->next) 
     print_node(current); 
} 

Answer 4

J'utilise ce qui suit pour créer une liste circulaire simple liée dynamique. Tout ce qu'il faut, c'est la taille.

Node* createCircularLList(int size) 
{ 
    Node *it; // to iterate through the LList 
    Node *head; 

    // Create the head /1st Node of the list 
    head = it = (Node*)malloc(sizeof(Node)); 
    head->id = 1; 

    // Create the remaining Nodes (from 2 to size) 
    int i; 
    for (i = 2; i <= size; ++i) { 
     it->next = (Node*)malloc(sizeof(Node)); // create next Node 
     it = it->next;       // point to it 
     it->id = i;        // assign its value/id 
     if (i == 2) 
      head->next = it; // head Node points to the 2nd Node 
    } 
    // close the llist by having the last Node point to the head Node 
    it->next = head; 

    return head; // return pointer to start of the list 
} 

Et je définis Node ADT comme ceci:

typedef struct Node { 
    int id; 
    struct Node *next; 
} Node;