Удалить из двойного связанного списка

Question

Я пытаюсь удалить узел из двусвязного списка, но у меня есть проблема, и эта проблема возникает, когда узел является первым или посередине, вместо него выводится 0, и он не удаляется, но работает хорошо, когдаэто последний узел в списке, и вот код:

dList* del(dList*ptr, int x)
{

    dList *itr = NULL;
    for( itr = ptr; itr != NULL; itr = itr -> next)
    {
            // if the element is the first in the list
            if(itr -> value == x && itr -> prev == NULL)
            {
                itr -> next -> prev = NULL;
                ptr = itr -> next;
                free(itr);
            }
            // if the element is the last in the list
            else if(itr -> value == x && itr -> next == NULL)
            {
                itr -> prev -> next = NULL;

                free(itr);
            }
            // if its in the middle

            else if(itr -> value == x){
                    (itr -> prev) -> next = itr -> next;
                    (itr -> next) -> prev = itr -> prev;
                    free(itr);
            }
    }
    return ptr;
}

заранее спасибо!

Answer 1

Этот цикл

for( itr = ptr; itr != NULL; itr = itr -> next)
{
        // if the element is the first in the list
        if(itr -> value == x && itr -> prev == NULL)
        {
            itr -> next -> prev = NULL;
            ptr = itr -> next;
            free(itr);
        }
        // ...

имеет неопределенное поведение.

Например, в третьем выражении цикла for

itr = itr -> next

вы используете уже удаленный указатель

free(itr);

Если список, например, имеет только один узел, тоitr->next равно NULL. Итак, снова это утверждение

itr -> next -> prev = NULL;

также вызывает неопределенное поведение.

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

Такжеболее полезным возвращаемым значением является количество удаленных узлов в списке.

Определение функции может выглядеть следующим образом

size_t del( dList **ptr, int value )
{
    size_t n = 0;

    while ( *ptr != NULL )
    {
        if ( ( *ptr )->value == value )
        {
            dList *tmp = *ptr;
            *ptr = ( *ptr )->next;
            if ( *ptr ) ( *ptr )->prev = tmp->prev;

            free( tmp );
            ++n;
        }
        else
        {
            ptr = &( *ptr )->next;
        }
    }

    return n;
}

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

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

typedef struct dList
{
    int value;
    struct dList *prev;
    struct dList *next;
} dList;


size_t del( dList **ptr, int value )
{
    size_t n = 0;

    while ( *ptr != NULL )
    {
        if ( ( *ptr )->value == value )
        {
            dList *tmp = *ptr;
            *ptr = ( *ptr )->next;
            if ( *ptr ) ( *ptr )->prev = tmp->prev;

            free( tmp );
            ++n;
        }
        else
        {
            ptr = &( *ptr )->next;
        }
    }

    return n;
}

int push_front( dList **head, int value )
{
    dList *new_node = malloc( sizeof( dList ) );
    int success = new_node != NULL;

    if ( success )
    {
        new_node->prev = NULL;
        new_node->value = value;
        new_node->next = *head;

        if ( *head ) ( *head )->prev = new_node;

        *head = new_node;
    }

    return success;
}

void out( dList *head )
{
    for ( ; head != NULL; head = head->next )
    {
        printf( "%d --> ", head->value );
    }

    puts( "NULL" );
}

int main(void) 
{
    dList *head = NULL;

    push_front( &head, 1 );
    push_front( &head, 2 );
    push_front( &head, 1 );

    out( head );

    size_t n = del( &head, 1 );

    printf( "%zu nodes are deleted.\n", n );
    out( head );

    n = del( &head, 2 );

    printf( "%zu nodes are deleted.\n", n );
    out( head );

    return 0;
}

Его вывод

1 --> 2 --> 1 --> NULL
2 nodes are deleted.
2 --> NULL
1 nodes are deleted.
NULL