удаление узла из односвязного списка

Question

У меня есть простая функция, которая ищет узел с данным ключом из одного связанного списка и удаляет его. Функция работает, когда узел с этим ключом находится везде, кроме случаев, когда этот узел является главой списка. Почему это происходит?

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


struct Node{
    int data;
    struct Node* next;
};

void printlist(struct Node* node){
    while(node!=NULL){
        printf("%d", node->data);
        node = node->next;
    }
    printf("\n");
}

/* Given a reference (pointer to pointer) to the head of a list 
   and a key, deletes the first occurrence of key in linked list */
void deleteNode(struct Node* head, int key){
    if(head->data==key){
        head = head->next;
    }
    else {
        while(head->next->data!=key){
            head = head->next;
        }
        head->next = head->next->next;
    }
}

int main(){

    struct Node* first = (struct Node*)malloc(sizeof(struct Node));
    struct Node* second = (struct Node*)malloc(sizeof(struct Node));
    struct Node* third = (struct Node*)malloc(sizeof(struct Node));
    first->data = 1;
    second->data = 2;
    third->data = 3;
    first->next = second;
    second->next = third;
    third->next = NULL;

    printlist(first); // prints 123

    deleteNode(first, 2);  
    printlist(first); // prints 13

    deleteNode(first, 1);
    printlist(first); // still prints 13
}

Answer 1

Функция имеет дело с копией оригинальной головы. Таким образом, изменение копии не влияет на исходный узел. Вы должны либо передать головной узел по ссылке через указатель, либо вернуть из функции измененный головной узел. Также вы должны проверить в начале функции, равен ли головной узел NULL. В противном случае функция может вызывать неопределенное поведение.

Например

void deleteNode( struct Node **head, int key )
{
    while( *head != NULL && ( *head )->data != key ) head = &( *head )->next;

    if ( *head != NULL ) *head = ( *head )->next;
}

И вызывать его как

deleteNode( &first, 1 );

Вот демонстрационная программа

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

struct Node{
    int data;
    struct Node* next;
};

void printlist(struct Node* node){
    while(node!=NULL){
        printf("%d", node->data);
        node = node->next;
    }
    printf("\n");
}

/* Given a reference (pointer to pointer) to the head of a list 
   and a key, deletes the first occurrence of key in linked list */
void deleteNode( struct Node **head, int key )
{
    while( *head != NULL && ( *head )->data != key ) head = &( *head )->next;

    if ( *head != NULL ) *head = ( *head )->next;
}

int main(){

    struct Node* first = (struct Node*)malloc(sizeof(struct Node));
    struct Node* second = (struct Node*)malloc(sizeof(struct Node));
    struct Node* third = (struct Node*)malloc(sizeof(struct Node));
    first->data = 1;
    second->data = 2;
    third->data = 3;
    first->next = second;
    second->next = third;
    third->next = NULL;

    printlist(first); // prints 123

    deleteNode(&first, 2);  
    printlist(first); // prints 13

    deleteNode(&first, 1);
    printlist(first); // still prints 13
}

Его вывод:

123
13
3

Или

struct Node * deleteNode( struct Node *head, int key )
{
    if ( head != NULL )
    {
        if ( head->data == key )
        {
            head = head->next;
        }
        else 
        {
            struct Node *current = head;
            while( current->next != NULL && current->next->data != key )
            {
                current = current->next;
            }
            if ( current->next != NULL ) current->next = current->next->next;
        }
    }

    return head;
}

и назовите его как

first = deleteNode( first, 1 );

Вот еще одна демонстрационная программа

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

struct Node{
    int data;
    struct Node* next;
};

void printlist(struct Node* node){
    while(node!=NULL){
        printf("%d", node->data);
        node = node->next;
    }
    printf("\n");
}

/* Given a reference (pointer to pointer) to the head of a list 
   and a key, deletes the first occurrence of key in linked list */
    struct Node * deleteNode( struct Node *head, int key )
    {
        if ( head != NULL )
        {
            if ( head->data == key )
            {
                head = head->next;
            }
            else 
            {
                struct Node *current = head;
                while( current->next != NULL && current->next->data != key )
                {
                    current = current->next;
                }
                if ( current->next != NULL ) current->next = current->next->next;
            }
        }

        return head;
    }

int main(){

    struct Node* first = (struct Node*)malloc(sizeof(struct Node));
    struct Node* second = (struct Node*)malloc(sizeof(struct Node));
    struct Node* third = (struct Node*)malloc(sizeof(struct Node));
    first->data = 1;
    second->data = 2;
    third->data = 3;
    first->next = second;
    second->next = third;
    third->next = NULL;

    printlist(first); // prints 123

    first = deleteNode(first, 2);  
    printlist(first); // prints 13

    first = deleteNode(first, 1);
    printlist(first); // still prints 13
}

Снова его вывод

123
13
3

В общем случае узлы списков размещаются динамически. Поэтому функция, которая удаляет узлы, должна также освободить удаленный узел или вернуть его из функции.

Answer 2

Когда вы вызываете эту функцию: void deleteNode(struct Node* head, int key) с первым аргументом, который является указателем на структуру Node (как вы делаете дважды в вашем main), тогда то, что функция получает в качестве первого аргумента, является копия указателя, который вы дали !

Вы, вероятно, знаете, что функция: void Increment(int n) может делать все, что ей нравится, переданной ей n без измененияпеременная в вызывающем модуле. Итак, если вы хотите, чтобы функция фактически изменила значение в вызывающем блоке, вы даете ей указатель:

void Increment(int* n) {
    ++(*n);
}

Аналогично, если вы хотите, чтобы функция изменила указатель, вам нужно передать его указатель на этот указатель . Попробуйте это:

void deleteNode(struct Node** head, int key){
    Node* temp = *head;
    if(temp->data==key){
        *head = temp->next; // Only need to change *head if its the first one ...
    }
    else {
        while(temp->next->data!=key){
            temp = temp->next;
        }
        temp->next = temp->next->next; // ... else we have already changed the actual "links"
    }
}

И, в main, используйте:

deleteNode(&first, 2);

и:

deleteNode(&first, 1);

Сообщите нам, что происходит.

Примечание: Между прочим, это не «лучший из возможных кодов» - удаляя ссылку без фактического удаления указанного объекта, вы создаете утечку памяти.

Примечание 2: Кроме того, если key не найден, ваш код будет «падать» в конец списка, когда он найдет указатель NULL next!