Elegante implementazione dell'elenco circolare unico in C?

Question

Passa attraverso le classiche strutture dati e si è fermato sulle liste collegate. Ho implementato una lista circolare a link singolo, ma ho l'impressione travolgente che questa lista possa essere espressa in modo più elegante, in particolare la funzione remove_node. Tenendo a mente l'efficienza e la leggibilità del codice, qualcuno potrebbe presentare una soluzione più concisa ed efficiente per la lista circolare con link singoli?

#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

Date un'occhiata alla lista concatenata circolare nei sorgenti del kernel di Linux: http://lxr.linux.no/linux+v2.6.36/include/linux/list.h

La sua bellezza deriva dal fatto che non si dispone di una struttura speciale per i vostri dati per entrare nella lista, devi solo includere lo struct list_head * nella struttura che vuoi avere come lista. Le macro per l'accesso agli elementi nell'elenco gestiranno il calcolo dell'offset per ottenere dal puntatore struct list_head i dati.

Una spiegazione più dettagliata dell'elenco collegato utilizzato nel kernel può essere trovata in kernelnewbies.org/FAQ/LinkedLists (Spiacente, non ho abbastanza karma per pubblicare due hyperlink).

Modifica: Bene, l'elenco è un elenco a collegamento doppio e non a collegamento singolo come si ha, ma è possibile adottare il concetto e creare il proprio elenco a collegamento singolo.

Answer 2

Alcuni commenti:

• credo che la funzione di rimozione non si regola correttamente i puntatori lista circolare quando si elimina il nodo principale e la lista è più grande di 3 elementi. Poiché la lista è circolare, devi puntare l'ultimo nodo nell'elenco alla nuova testa.
• Potrebbe essere possibile abbreviare leggermente la funzione di rimozione creando una funzione "find_node". Poiché la lista è circolare, tuttavia, ci sarà ancora il caso limite di eliminare il nodo principale che sarà più complesso di un elenco non circolare.
• Il codice "bellezza" è negli occhi di chi guarda. Come il codice va tuo è facile da leggere e capire che batte un sacco di codice in the wild.

Answer 3

L'elaborazione di elenchi (in particolare di elenchi circolari) diventa più semplice quando si considera la lista come un elemento della lista (un cosiddetto "sentinella"). Un sacco di casi speciali scompaiono. È possibile utilizzare un nodo fittizio per la sentinella, ma se il prossimo puntatore è il primo nella struttura, non è necessario fare nemmeno quello. L'altro grande trucco consiste nel mantenere un puntatore al puntatore successivo del nodo precedente (in modo da poterlo modificare in seguito) ogni volta che si modifica l'elenco. Mettendo tutto insieme, ottieni questo:

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

Io uso quanto segue per creare un elenco circolare dinamico collegato singolarmente. Tutto ciò che richiede è la dimensione.

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 
} 

E definisco Node ADT modo:

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