Uso de punteros para eliminar elementos de la lista de enlaces únicos

En una reciente entrevista de Slashdot, Linus Torvalds dio un ejemplo de cómo algunas personas usan punteros de una manera que indica que realmente no entienden cómo usarlos correctamente.

Desafortunadamente, dado que soy una de las personas de las que él habla, tampoco pude entender su ejemplo:

He visto demasiadas personas que eliminan una entrada de la lista enlazada de forma individual al hacer un seguimiento de la entrada “anterior”, y luego eliminar la entrada, haciendo algo así como

if (prev) prev->next = entry->next; else list_head = entry->next; 

y cada vez que veo un código como ese, simplemente digo “Esta persona no entiende los punteros”. Y es tristemente bastante común. Las personas que entienden los punteros simplemente usan un “puntero al puntero de entrada” e inicializan eso con la dirección del list_head. Y luego, a medida que atraviesan la lista, pueden eliminar la entrada sin usar ningún condicionamiento, simplemente haciendo

 *pp = entry->next 

¿Puede alguien dar una explicación un poco más sobre por qué este enfoque es mejor y cómo puede funcionar sin un enunciado condicional?

Al principio, lo haces

 pp = &list_head; 

y, a medida que recorre la lista, avanza este “cursor” con

 pp = &(*pp)->next; 

De esta forma, siempre realiza un seguimiento del punto donde “vienes” y puede modificar el puntero que vive allí.

Entonces, cuando encuentre que la entrada se borrará, puede hacer

*pp = entry->next

De esta manera, usted se ocupa de los 3 casos que Afaq menciona en otra respuesta, eliminando efectivamente la verificación NULL en prev .

Volver a conectar la lista una vez que se va a eliminar un nodo es más interesante. Consideremos al menos 3 casos:

1. Removiendo un nodo desde el principio.

2. Removiendo un nodo del centro.

3. Remover un nodo del final.

Eliminar desde el principio

Al eliminar el nodo al principio de la lista, no se debe volver a vincular los nodos, ya que el primer nodo no tiene ningún nodo precedente. Por ejemplo, eliminar un nodo con a:

 link | v --------- --------- --------- | a | --+---> | b | --+---> | c | 0 | --------- --------- --------- 

Sin embargo, debemos corregir el puntero al comienzo de la lista:

 link | +-------------+ | v --------- --------- --------- | a | --+---> | b | --+---> | c | 0 | --------- --------- --------- 

Eliminar del medio

Para eliminar un nodo del medio, el nodo anterior se salta el nodo que se está eliminando. Por ejemplo, eliminar el nodo con b:

 link | v --------- --------- --------- | a | --+--+ | b | --+---> | c | 0 | --------- | --------- --------- | ^ +----------------+ 

Esto significa que necesitamos alguna forma de referirnos al nodo antes del que queremos eliminar.

Eliminando del final

Eliminar un nodo del final requiere que el nodo precedente se convierta en el nuevo final de la lista (es decir, no muestre nada después de él). Por ejemplo, eliminar el nodo con c:

 link | v --------- --------- --------- | a | --+---> | b | 0 | | c | 0 | --------- --------- --------- 

Tenga en cuenta que los dos últimos casos (medio y extremo) pueden combinarse diciendo que “el nodo que precede al que se va a eliminar debe señalar dónde lo hace el que se va a eliminar”.

En el primer enfoque, elimina un nodo desvinculándolo de la lista.

En el segundo enfoque, reemplaza el nodo que se va a eliminar con el siguiente nodo.

Aparentemente, el segundo enfoque simplifica el código de una manera elegante. Definitivamente, el segundo enfoque requiere una mejor comprensión de la lista vinculada y el modelo de cálculo subyacente.

Nota : Aquí hay una pregunta de encoding muy relevante pero ligeramente diferente. Bueno para poner a prueba nuestra comprensión: https://leetcode.com/problems/delete-node-in-a-linked-list/

Explicación por video

Este problema ha sido discutido por Philip Buuck en este video de YouTube . Te recomiendo que veas esto si necesitas una explicación más detallada.


Explicación por ejemplo

Si te gusta aprender de ejemplos, preparé uno. Digamos que tenemos la siguiente lista de enlaces únicos:

Ejemplo de lista enlazada individualmente

que se representa de la siguiente manera (haga clic para agrandar):

Representación de lista enlazada individualmente

Queremos eliminar el nodo con el value = 8 .

Código

Aquí está el código simple que hace esto:

 #include  #include  #include  struct node_t { int value; node_t *next; }; node_t* create_list() { int test_values[] = { 28, 1, 8, 70, 56 }; node_t *new_node, *head = NULL; int i; for (i = 0; i < 5; i++) { new_node = (node_t*)malloc(sizeof(struct node_t)); assert(new_node); new_node->value = test_values[i]; new_node->next = head; head = new_node; } return head; } void print_list(const node_t *head) { for (; head; head = head->next) printf("%d ", head->value); printf("\n"); } void destroy_list(node_t **head) { node_t *next; while (*head) { next = (*head)->next; free(*head); *head = next; } } void remove_from_list(int val, node_t **head) { node_t *del, **p = head; while (*p && (**p).value != val) p = &(*p)->next; // alternatively: p = &(**p).next if (p) { // non-empty list and value was found del = *p; *p = del->next; del->next = NULL; // not necessary in this case free(del); } } int main(int argc, char **argv) { node_t *head; head = create_list(); print_list(head); remove_from_list(8, &head); print_list(head); destroy_list(&head); assert (head == NULL); return EXIT_SUCCESS; } 

Si comstack y ejecuta este código, obtendrá:

 56 70 8 1 28 56 70 1 28 

Explicación del código

Vamos a crear **p ‘doble’ puntero a *head puntero de *head :

Singly-linked list example # 2

Ahora analicemos qué tan void remove_from_list(int val, node_t **head) funciona void remove_from_list(int val, node_t **head) . Se repite sobre la lista señalada por la head siempre que *p && (**p).value != val .

Singly-linked list example # 3

Ejemplo de lista enlazada individualmente # 4

En este ejemplo, la lista dada contiene el value que queremos eliminar (que es 8 ). Después de la segunda iteración del while (*p && (**p).value != val) loop (**p).value pasa a ser 8 , por lo que dejamos de iterar.

Tenga en cuenta que *p apunta a la variable node_t *next dentro de node_t que está antes del node_t que queremos eliminar (que es **p ). Esto es crucial porque nos permite cambiar el *next puntero del node_t que está delante del node_t que queremos eliminar, eliminándolo de la lista de manera efectiva.

Ahora asignemos la dirección del elemento que queremos eliminar ( del->value == 8 ) al *del puntero.

Ejemplo de lista enlazada individualmente # 5

Necesitamos arreglar el puntero *p para que **p apunte al elemento después de *del elemento que vamos a eliminar:

Ejemplo de lista enlazada individualmente # 6

En el código anterior, llamamos a free(del) , por lo que no es necesario establecer del->next a NULL , pero si queremos devolver el puntero al elemento ‘detached’ de la lista en lugar de eliminarlo completamente, establecería del->next = NULL :

Ejemplo de lista enlazada individualmente # 7

Prefiero el enfoque del nodo Dummy, un diseño de ejemplo:

 |Dummy|->|node1|->|node2|->|node3|->|node4|->|node5|->NULL ^ ^ | | curr curr->next // << toDel 

y luego, atraviesa el nodo para eliminar (toDel = curr> next)

 tmp = curr->next; curr->next = curr->next-next; free(tmp); 

De esta forma, no es necesario que compruebe si es el primer elemento, ya que el primer elemento siempre es falso y nunca se elimina.

Aquí hay un ejemplo completo de código, usando una función-llamada para eliminar elementos coincidentes:

  • rem() elimina elementos coincidentes, utilizando prev

  • rem2() elimina elementos coincidentes, usando puntero-a-puntero

 // code.c #include  #include  typedef struct list_entry { int val; struct list_entry *next; } list_entry; list_entry *new_node(list_entry *curr, int val) { list_entry *new_n = (list_entry *) malloc(sizeof(list_entry)); if (new_n == NULL) { fputs("Error in malloc\n", stderr); exit(1); } new_n->val = val; new_n->next = NULL; if (curr) { curr->next = new_n; } return new_n; } #define ARR_LEN(arr) (sizeof(arr)/sizeof((arr)[0])) #define CREATE_LIST(arr) create_list((arr), ARR_LEN(arr)) list_entry *create_list(const int arr[], size_t len) { if (len == 0) { return NULL; } list_entry *node = NULL; list_entry *head = node = new_node(node, arr[0]); for (size_t i = 1; i < len; ++i) { node = new_node(node, arr[i]); } return head; } void rem(list_entry **head_p, int match_val) // remove and free all entries with match_val { list_entry *prev = NULL; for (list_entry *entry = *head_p; entry; ) { if (entry->val == match_val) { list_entry *del_entry = entry; entry = entry->next; if (prev) { prev->next = entry; } else { *head_p = entry; } free(del_entry); } else { prev = entry; entry = entry->next; } } } void rem2(list_entry **pp, int match_val) // remove and free all entries with match_val { list_entry *entry; while ((entry = *pp)) { // assignment, not equality if (entry->val == match_val) { *pp = entry->next; free(entry); } else { pp = &entry->next; } } } void print_and_free_list(list_entry *entry) { list_entry *node; // iterate through, printing entries, and then freeing them for (; entry != NULL; node = entry, /* lag behind to free */ entry = entry->next, free(node)) { printf("%d ", entry->val); } putchar('\n'); } #define CREATELIST_REMOVEMATCHELEMS_PRINT(arr, match_val) createList_removeMatchElems_print((arr), ARR_LEN(arr), (match_val)) void createList_removeMatchElems_print(const int arr[], size_t len, int match_val) { list_entry *head = create_list(arr, len); rem2(&head, match_val); print_and_free_list(head); } int main() { const int match_val = 2; // the value to remove { const int arr[] = {0, 1, 2, 3}; CREATELIST_REMOVEMATCHELEMS_PRINT(arr, match_val); } { const int arr[] = {0, 2, 2, 3}; CREATELIST_REMOVEMATCHELEMS_PRINT(arr, match_val); } { const int arr[] = {2, 7, 8, 2}; CREATELIST_REMOVEMATCHELEMS_PRINT(arr, match_val); } { const int arr[] = {2, 2, 3, 3}; CREATELIST_REMOVEMATCHELEMS_PRINT(arr, match_val); } { const int arr[] = {0, 0, 2, 2}; CREATELIST_REMOVEMATCHELEMS_PRINT(arr, match_val); } { const int arr[] = {2, 2, 2, 2}; CREATELIST_REMOVEMATCHELEMS_PRINT(arr, match_val); } { const int arr[] = {}; CREATELIST_REMOVEMATCHELEMS_PRINT(arr, match_val); } return 0; } 

Vea el código en acción aquí:

Si comstack y usa valgrind (un corrector de memory leaks) como este:
gcc -std=c11 -Wall -Wextra -Werror -o go code.c && valgrind ./go
vemos que todo está bien.

@glglgl:

Escribí siguiendo un ejemplo simple. Espero que puedas echar un vistazo por qué funciona.
En la función void delete_node(LinkedList *list, void *data) , uso *pp = (*pp)->next; y funciona. Para ser honesto, no entiendo por qué funciona. Incluso dibujo el diagtwig de punteros pero aún no lo entiendo. Espero que puedas aclararlo.

 #include  #include  #include  typedef struct _employee { char name[32]; unsigned char age; } Employee; int compare_employee(Employee *e1, Employee *e2) { return strcmp(e1->name, e2->name); } typedef int (*COMPARE)(void *, void *); void display_employee(Employee *e) { printf("%s\t%d\n", e->name, e->age); } typedef void (*DISPLAY)(void *); typedef struct _node { void *data; struct _node *next; } NODE; typedef struct _linkedlist { NODE *head; NODE *tail; NODE *current; } LinkedList; void init_list(LinkedList *list) { list->head = NULL; list->tail = NULL; list->current = NULL; } void add_head(LinkedList *list, void *data) { NODE *node = (NODE *) malloc(sizeof(NODE)); node->data = data; if (list->head == NULL) { list->tail = node; node->next = NULL; } else { node->next = list->head; } list->head = node; } void add_tail(LinkedList *list, void *data) { NODE *node = (NODE *) malloc(sizeof(NODE)); node->data = data; node->next = NULL; if (list->head == NULL) { list->head = node; } else { list->tail->next = node; } list->tail = node; } NODE *get_node(LinkedList *list, COMPARE compare, void *data) { NODE *n = list->head; while (n != NULL) { if (compare(n->data, data) == 0) { return n; } n = n->next; } return NULL; } void display_list(LinkedList *list, DISPLAY display) { printf("Linked List\n"); NODE *current = list->head; while (current != NULL) { display(current->data); current = current->next; } } void delete_node(LinkedList *list, void *data) { /* Linus says who use this block of code doesn't understand pointer. NODE *prev = NULL; NODE *walk = list->head; while (((Employee *)walk->data)->age != ((Employee *)data)->age) { prev = walk; walk = walk->next; } if (!prev) list->head = walk->next; else prev->next = walk->next; */ NODE **pp = &list->head; while (((Employee *)(*pp)->data)->age != ((Employee *)data)->age) { pp = &(*pp)->next; } *pp = (*pp)->next; } int main () { LinkedList list; init_list(&list); Employee *samuel = (Employee *) malloc(sizeof(Employee)); strcpy(samuel->name, "Samuel"); samuel->age = 23; Employee *sally = (Employee *) malloc(sizeof(Employee)); strcpy(sally->name, "Sally"); sally->age = 19; Employee *susan = (Employee *) malloc(sizeof(Employee)); strcpy(susan->name, "Susan"); susan->age = 14; Employee *jessie = (Employee *) malloc(sizeof(Employee)); strcpy(jessie->name, "Jessie"); jessie->age = 18; add_head(&list, samuel); add_head(&list, sally); add_head(&list, susan); add_tail(&list, jessie); display_list(&list, (DISPLAY) display_employee); NODE *n = get_node(&list, (COMPARE) compare_employee, sally); printf("name is %s, age is %d.\n", ((Employee *)n->data)->name, ((Employee *)n->data)->age); printf("\n"); delete_node(&list, samuel); display_list(&list, (DISPLAY) display_employee); return 0; } 

salida:

 Linked List Susan 14 Sally 19 Samuel 23 Jessie 18 name is Sally, age is 19. Linked List Susan 14 Sally 19 Jessie 18