Удалить объект из списка

Question

Мой элемент списка:

typdef struct sNode
{
   struct sNode* next;
   myData data;
} tNode;

Я хочу реализовать следующий API:

bool removeNode(tNode* node)
{
... // need to fix list and free node
}

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

Answer 1

Нет. Вам нужно пройти от начала списка, чтобы найти предыдущий узел, что довольно неэффективно. Это проблема с односвязными списками. Если вам нужно, чтобы это было быстро, используйте двусвязный список (каждый узел имеет указатель next и указатель previous ).

Answer 2

Вы используете один связанный список, если вы хотите удалить узел из списка, вы должны пройти список из головы. Итак, вам нужно изменить свой API на что-то вроде этого:

bool removeNode(tNode * head, tNode* node);

Answer 3

Да (почти) - вы можете скопировать содержимое node->next в node, а затем удалить node->next.

В псевдокоде:

sNode* next = node->next; // see below for an important special case
node->data = next->data;
node->next = next->next;
free(next);

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

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

Если вы часто удаляете узлы по указателю, вам следует подумать о том, является ли односвязный список правильной структурой данных. Например, двусвязный список не имеет этой проблемы (но имеет дополнительные издержки одного дополнительного указателя на узел).