Удаление прямого связанного списка

Question

Есть два известных способа (только два?), Чтобы удалить прямой связанный список

1. Одним из способов является рекурсивная функция, которая неэффективна и может привести к переполнению стека, если список слишком большой

2. Другой способ (эффективный) - это функция, которая выполняет итерацию и удаление узлов следующим образом:

   class Forward_list {
   public:
      // Constructor...
   
      ~Forward_list() { if(head) destroy(); }
   
      void destroy() {
           node* prev = nullptr;
           while (head) {
               prev = head;
               head = head->next;
               delete prev;
           }
       }
   
       // functions...
   private:
       // data members...
       node* head;
   };
   

А как насчет этого:

class Forward_list {
public:
    // Constructor...

    ~Forward_list() { if(head) delete this->head; }

    // functions...
private:
    struct node {
        ~node() { delete this->next; } // <- this way
        type data;
        node* next;
    };
    node* head;
    // data members...
};

Я проверил его, и он работает нормально... Я считаю, что так чище, но не уверен, будут ли побочные эффекты?

Answer 1

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

Answer 2

~node() { delete this->next; } // <- this way

Я считаю этот способ чище, но не уверен, будут ли побочные эффекты?

Ну, "побочным эффектом" будет то, что вы не можете удалить какие-либо узлы из списка, не удаляя весь остальной список, так как ~node() там называется рекурсивно.

Это, вероятно, не то, что вы хотите сделать.

Answer 3

Так как это не было упомянуто ранее: при использовании

delete this->next;

обратите внимание, что деструктор вызывается рекурсивно, т. е. подход deleteследующий узел в деструкторе эквивалентен рекурсивному подходу deleteсоставление списка. Рекурсия просто не такая прямая и очевидная.