¿Implementación elegante de la lista circular solitaria en C?

Question

Pasando por las estructuras de datos clásicas y se han detenido en listas enlazadas. Solo implementé una lista circular de enlace único, pero tengo la abrumadora impresión de que esta lista podría expresarse de una manera más elegante, en particular la función remove_node. Teniendo en cuenta la eficiencia y la legibilidad del código, ¿podría alguien presentar una solución más concisa y eficiente para la lista circular unida de forma simple?

#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

Tome un vistazo a la lista enlazada circular en el código fuente del núcleo Linux: http://lxr.linux.no/linux+v2.6.36/include/linux/list.h

Su belleza se deriva del hecho de que usted no tiene una estructura especial para que sus datos encajan en la lista, solo tiene que incluir el struct list_head * en la estructura que desea tener como una lista. Las macros para acceder a los elementos de la lista manejarán el cálculo del desplazamiento para obtener del puntero struct list_head a sus datos.

Una explicación más detallada de la lista enlazada utilizada en el kernel se puede encontrar en kernelnewbies.org/FAQ/LinkedLists (Lo siento, no tengo suficiente karma para publicar dos hipervínculos).

Editar: Bueno, la lista es de doble enlace y no de enlace único como la que tiene, pero podría adoptar el concepto y crear su propia lista de enlaces únicos.

Answer 2

Algunos comentarios:

• creo que la función de eliminación no se ajusta correctamente los punteros lista circular cuando se elimina el nodo principal y la lista es mayor de 3 elementos. Como la lista es circular, debe señalar el último nodo de la lista con el nuevo encabezado.
• Es posible que pueda acortar ligeramente la función de eliminación creando una función "find_node". Sin embargo, dado que la lista es circular, seguirá existiendo la posibilidad de eliminar el nodo principal, que será más complejo que en una lista no circular.
• El código "belleza" está en el ojo del espectador. Como el código es suyo, es fácil de leer y entender, lo que supera mucho código en la naturaleza.

Answer 3

El procesamiento de listas (particularmente de listas circulares) se vuelve mucho más fácil cuando tratas el encabezado de la lista como un elemento de la lista (un llamado "centinela"). Muchos casos especiales simplemente desaparecen. Puede usar un nodo ficticio para el centinela, pero si el siguiente puntero es el primero en la estructura, no necesita hacer eso. El otro gran truco es mantener un puntero al siguiente puntero del nodo anterior (para que pueda modificarlo más adelante) cada vez que modifique la lista. Poniéndolo todo junto, obtienes esto:

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

Utilizo lo siguiente para crear una lista circular dinámica individualmente vinculada. Todo lo que requiere es el tamaño.

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 
} 

Y i defino Node ADT así:

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