Удаление ссылок в двусвязном списке

Question

Я пишу код, основанный на двухсвязных списках, на языке C. Я ошибочно предположил, что удаляю головной узел, выполняя free(head_node). И я мог видеть, как компьютер замедлялся по мере запуска (что, очевидно, связано с утечкой памяти). Я искал stackoverflow и другие сайты, и код, с которым я обычно сталкивался для удаления связанного списка, был следующим:

Node* current = head;
while( current != NULL ) {
Node* next = current->Next;
free( current );
current = next;
}

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

Answer 1

Код, который вы разместили, должен работать для односвязных или двусвязных списков, но делает некоторые допущения:

• что очистка узла не производится перед его освобождением;это часто неверное предположение.
• что конец списка помечен нулевым указателем (т. е. член Next последнего узла равен NULL)

Относительно первого предположения: Поскольку у вас есть динамически распределенные данные в ваших узлах, и предполагается, что у вас нет другого указателя на них где-то еще, который вы будете использовать для очистки их позже, вам нужно будет освободить этоданные, прежде чем освободить каждый узел.В Си это не сделано для вас;общее правило заключается в том, что если вы должны были распределить его самостоятельно, вы должны освободить его и сами.Разумный способ справиться с этим - написать функцию для очистки и освобождения узла и вызвать ее вместо простого вызова free();Ваша функция очистки по-прежнему освобождает узел, но сначала освобождает данные узла.

Что касается второго предположения: Довольно распространенная практика - указывать указатель Next последнего узла наNULL для обозначения конца, поскольку с его помощью легко определить, когда вы прошли весь список.Для двусвязного списка то же самое относится к указателю Prev первого узла *1022*.Однако, если это круговой список, последний узел просто указывает на первый узел - и это нарушит код, который вы опубликовали.В этой ситуации вы должны начать с узла head->Next вместо head и проверить, не является ли current head, а не NULL.Затем разберитесь с head в конце, так как вы сначала его пропустили.

И еще одна вещь: Убедитесь, что после того, как вы закончили освобождение своего списка, вы не покидаете его.head указывает на недопустимый (уже освобожденный) узел, а затем снова пытается получить доступ к списку ...

Answer 2

Когда я освобождаю одну из ссылок, освобождает ли она все данные, на которые указывают участники?

Нет.Это то, что произошло бы, если бы вы удалили последнюю ссылку на объект на языке сборки мусора, но C не работает так.Вам нужно вручную освободить каждый бит памяти, который вы выделили.

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

В данных моего списка тоже много указателей.

Поскольку они есть, вам необходимо освободить каждого current->value (и если они являются указателями на указатели ...).