Правильный способ удаления связанного списка - PullRequest
Новая
       19

Правильный способ удаления связанного списка

3 голосов
/ 30 августа 2011

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

struct Node {
  Data d;
  Node *pNext;
  // methods
  ~Node();
};

Заголовок связанного списка сохраняется как, 

Node *m_Head; // member of some class

Когда я закончу со списком, я очистю его, удалив каждый узел как, 

void Erase()
{
  Node *pIter, *pTemp = m_Head;
  while((pIter = pTemp) != 0)
  {
    pTemp = pIter->pNext;
    delete pIter;
    pIter = pTemp;
  }
}

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

delete m_Head;

и деструктор будет выглядеть так: 

Node::~Node() { delete this->pNext; }

Здесь я беспокоюсь, не вызовет ли это рекурсию (неявно из-за delete)? Если да, то это определенно касается больших связанных списков. Может ли компилятор каким-либо образом помочь в его оптимизации?

[Примечание: не использовать библиотечные средства, такие как std::list или другие.]

Ответы [ 4 ]

3 голосов
/ 30 августа 2011

Я думаю, что вопрос, который вы должны задать, состоит в том, имеет ли каждый Node в списке свой свой pNext Node?Если нет, то он не имеет никакого дела, удаляя свой узел pNext в своем деструкторе.

В большинстве реализаций связанного списка все узлы принадлежат списку, узел не владеет всеми узлами после него всписок.Более разумно сохранять узлы как немые (POD-структуры) и позволять всей логике находиться в списке.

Это определенно "запах" дизайна, что у вашего узла есть деструктор, но нет конструктора копирования илиоператор копирования копирования.Я думаю, что этот подход вызовет большую сложность, когда вы придете к коду, реализующему функции вставки, объединения и удаления одноэлементных функций, поскольку вам придется в любом случае вручную управлять указателями pNext, чтобы избежать непреднамеренного уничтожения всего хвоста списка.

2 голосов
/ 30 августа 2011

Конечно: делайте это только в целях обучения или когда вы уверены, что ваш собственный Список действительно лучше для вашего варианта использования

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

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

Кроме того, я думаю, что рекурсия действительно не совсем подходит для концепции родственных узлов. Иерархия узлов, как и quadtree , требует рекурсии, но я не очень хорошо думаю о рекурсии (которая формирует вызов иерархия ), когда концепция списка о родственный -nodes.

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

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

class List {
public:
    ~List() {
        for-each-node
            delete-node
    }

private:
    class Node {
        Node *node_;
        ...
    };
    ...
};

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

1 голос
/ 30 августа 2011

Большинство компиляторов делают удаление хвостовых вызовов в настройках по умолчанию.Некоторые умнее могут конвертировать не-хвостовые вызовы в хвостовые.

Итак, этот метод в порядке, если у вас включена некоторая оптимизация.

0 голосов
/ 30 августа 2011

сырые указатели?Ручные вызовы delete?

Почему бы просто: 

struct Node {
  Data d;
  std::unique_ptr<Node> next;
};

Тогда вам даже не придется беспокоиться об управлении памятью, оно автоматическое!

...