Удаление более одного списка ссылок на узлы одновременно.

Question

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

Могу ли я удалить более одного узла одним ходом по списку, не возвращаясь к началу списка и найти следующий узел, который нужно удалить?Смогу ли я сделать это с помощью двусвязного списка?Все, что мне нужно сделать, - это удалить определенные узлы при выполнении условия и продолжать обход списка в одно и то же время, не возвращаясь к началу списка.

Answer 1

Удаление элементов из любого места в двусвязном списке, как правило, не проблема. Очевидно, что вы не можете сделать, это перемещаться по списку из только что удаленного элемента - он больше не является частью списка. Хитрость заключается в том, чтобы удерживать действительную ссылку на элемент в вашем списке, пока вы его просматриваете. Поскольку вы не предоставили код, я приведу пример с использованием STL std::list и его итераторов:

std::list<int> mylist;
mylist.push_back(1);
mylist.push_back(2);
mylist.push_back(3);
mylist.push_back(4);

// now we want to remove elements 2 and 4
std::list<int>::iterator current = mylist.begin();
// current: item 1
++current;
// current: item 2
mylist.erase(current); // remove item 2
++current; // BUG! the iterator is invalid after removing the item it references

вместо

std::list<int>::iterator current = mylist.begin();
// current: item 1
++current;
// current: item 2
std::list<int>::iterator next = current;
++next; // move 'next' to item 3
mylist.erase(current); // remove item 2
current = next; // make current point to item 3
++current;
// current: item 4
mylist.erase(current); // remove item 4

Это не относится только к связанным спискам STL (или C ++) - вместо итератора у вас может быть указатель на элемент, но это тот же принцип.