Использование указателей для удаления элемента из одноуровневого списка

Ответ 1

В начале вы делаете

pp = &list_head;

и, по мере прохождения списка, вы продвигаете этот "курсор" с помощью

pp = &(*pp)->next;

Таким образом, вы всегда отслеживаете точку, откуда "вы пришли", и можете изменять указатель, живущий там.

Итак, когда вы обнаружите, что запись будет удалена, вы можете просто сделать

*pp = entry->next

Таким образом, вы заботитесь обо всех трех случаях Afaq упоминает в другом ответе, эффективно устраняя проверку NULL на prev.

Ответ 2

Повторное подключение списка после удаления node более интересно. Рассмотрим хотя бы 3 случая:

1. Восстановить node с самого начала.

2.Удаление a node из середины.

3.Удаление node с конца.

Удаление с самого начала

При удалении node в начале списка нет повторения узлов, которые должны выполняться, поскольку первый node не имеет предшествующего node. Например, удалив node с помощью:

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

Однако мы должны исправить указатель на начало списка:

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

Удаление из середины

Удаление node из середины требует, чтобы предыдущий node пропустил удаление node. Например, удаление node с помощью b:

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

Это означает, что нам нужно каким-то образом ссылаться на node до того, который мы хотим удалить.

Удаление с конца

Удаление node с конца требует, чтобы предыдущий node стал новым концом списка (т.е. ничего не указывает после него). Например, удаление node с помощью c:

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

Обратите внимание, что последние два случая (средний и конец) можно комбинировать, говоря, что "node, предшествующий удаляемому, должен указывать, где должен быть удален тот, который нужно удалить".

Ответ 3

Если вам нравится учиться на примерах, я подготовил один. Допустим, у нас есть следующий односвязный список:

это выглядит следующим образом (нажмите, чтобы увеличить):

Мы хотим удалить узел с помощью value = 8.

Код

Вот простой код, который делает это:

#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;
}

Если вы скомпилируете и запустите этот код, вы получите:

56 70 8 1 28 
56 70 1 28

Объяснение кода

Давайте создадим **p двойной указатель на *head указатель:

Теперь давайте проанализируем, как работает void remove_from_list(int val, node_t **head). Он перебирает список, указанный в head, до тех пор, пока *p && (**p).value != val.

В этом примере данный список содержит value, который мы хотим удалить (то есть 8). После второй итерации цикла while (*p && (**p).value != val) (**p).value становится 8, поэтому мы прекращаем итерацию.

Обратите внимание, что *p указывает на переменную node_t *next внутри node_t, которая находится перед node_t, который мы хотим удалить (то есть **p). Это очень важно, поскольку позволяет нам изменить указатель *next на node_t, который находится перед node_t, который мы хотим удалить, эффективно удаляя его из списка.

Теперь давайте назначим адрес элемента, который мы хотим удалить (del->value == 8), указателю *del.

Нам нужно исправить указатель *p так, чтобы **p указывал на один элемент после элемента *del, который мы собираемся удалить:

В приведенном выше коде мы вызываем free(del), поэтому нет необходимости устанавливать для del->next значение NULL, но если мы хотим вернуть указатель на элемент, "отсоединенный" из списка, вместо того, чтобы полностью удалить его, мы установит del->next = NULL:

Ответ 4

В первом подходе вы удалите node из unlink из списка.

Во втором подходе вы замените подлежащий удалению node следующим node.

По-видимому, второй подход упрощает код элегантным способом. Определенно, второй подход требует лучшего понимания связанного списка и базовой вычислительной модели.

Примечание. Вот очень важный, но немного другой вопрос с кодировкой. Хорошо для тестирования одного понимания: https://leetcode.com/problems/delete-node-in-a-linked-list/

Ответ 5

Я предпочитаю подход Dummy node, пример макета:

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

а затем вы переходите к node для удаления (toDel = curr > next)

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

Таким образом, вам не нужно проверять, является ли это первым элементом, потому что первый элемент всегда является Dummy и никогда не удаляется.

Ответ 6

@glglgl:

Я написал следующий простой пример. Надеюсь, вы можете посмотреть, почему это работает.
В функции void delete_node(LinkedList *list, void *data) я использую *pp = (*pp)->next;, и он работает. Честно говоря, я не понимаю, почему это работает. Я даже рисую диаграмму указателей, но все еще не понимаю. Надеюсь, вы сможете это прояснить.

#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;
}

выход:

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

Linked List
Susan   14
Sally   19
Jessie  18

Ответ 7

Здесь приведен полный пример кода, используя функцию-вызов для удаления соответствующих элементов:

• rem() удаляет соответствующие элементы, используя prev

• rem2() удаляет соответствующие элементы, используя указатель на указатель

// 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;
}

Смотрите код в действии здесь:

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

Если компилировать и использовать valgrind (средство проверки утечки памяти), например:
gcc -std=c11 -Wall -Wextra -Werror -o go code.c && valgrind ./go
мы видим, что все хорошо.