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

romutv

Question

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?

Answer 1

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:

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

Queremos eliminar el nodo con el value = 8 .

Código

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

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

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 compila 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 :

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 .

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.

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

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 :

Answer 2

@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 diagrama de punteros pero aún no lo entiendo. Espero que puedas aclararlo.

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

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

Answer 3

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 .

Answer 4

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 <stdio.h>
#include <stdlib.h>


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í:

• gcc https://wandbox.org/permlink/LxgMddqCZWyj7lMI
• clang https://wandbox.org/permlink/5aEkxh24sGfAecwF

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

Answer 5

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 codificación muy relevante pero ligeramente diferente. Bueno para poner a prueba nuestra comprensión: https://leetcode.com/problems/delete-node-in-a-linked-list/

Answer 6

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.

Answer 7

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".